競プロ典型 90 問の014について(vector と priority

質問内容

C++で動作させています
014 - We Used to Sing a Song Together（★3）について、最初にpriority_queueを用いて計算を行ったのですが6つほどTLEになりました。
そのあとにvector配列を用いると普通にACになったのがどうしても腑に落ちず、見当がつかないため質問させていただきました。

vectorのsortもO(nlogn)なのでなぜこれだけ速度に変化が起きたのかをご教授願えると嬉しいです。

自分の考え

priority_queueのほうもA,Bに入れる段階でO(nlogn)、取り出す(pop())の段階でもO(nlogn)なので、最大値でもN＝100000から計算は事足りると思いました。

priority_queを使ったコード

C++
1#define _GLIBCXX_DEBUG
2#include <bits/stdc++.h>
3using namespace std;
4using namespace std;
5typedef long long ll;
6
7//イテレーション
8#define REP(i,n) for(ll i=0;i<ll(n);i++)
9
10int main() {
11    ll N;
12    ll a;
13    ll b;
14    priority_queue<ll> A;
15    priority_queue<ll> B;
16    cin >> N;
17    REP(i,N){
18        cin >> a;
19        A.push(a);
20    }
21    REP(i,N){
22        cin >> b;
23        B.push(b);
24    }
25    ll ans = 0;
26    REP(i,N){
27        ans += abs(A.top()-B.top());
28        A.pop();
29        B.pop();
30    }
31    cout << ans << endl;
32}
33
34

計算時間:TLE

vectorを使ったコード

C++
1#define _GLIBCXX_DEBUG
2#include <bits/stdc++.h>
3using namespace std;
4using namespace std;
5typedef long long ll;
6
7//イテレーション
8#define REP(i,n) for(ll i=0;i<ll(n);i++)
9
10int main() {
11    ll N;
12    ll a;
13    ll b;
14    vector<ll> A;
15    vector<ll> B;
16    cin >> N;
17    REP(i,N){
18        cin >> a;
19        A.push_back(a);
20    }
21    REP(i,N){
22        cin >> b;
23        B.push_back(b);
24    }
25    sort(A.begin(),A.end());
26    sort(B.begin(),B.end());
27    ll ans = 0;
28    REP(i,N){
29        ans += abs(A.at(i)-B.at(i));
30    }
31    cout << ans << endl;
32}
33
34