ECOO '19 R1 P4 - Bus Route

#include <bits/stdc++.h>

using namespace std;
int testcasenum = 10;
int N, M;
int stop[500005], t[500005];
vector<int> v[500005];
struct query{
    int val, bus;
    bool operator < (query q) const {
        if(q.val == val){
            return bus > q.bus;
        }
        else{
            return val > q.val;
        }
    }
};
int main(){
//    freopen("DATA41.txt", "r", stdin);
//    freopen("DATA42.txt", "r", stdin);
    while(testcasenum--){
        priority_queue <query> dropoff, pickup;
        cin.sync_with_stdio(0);
        cin.tie(0);
        cin >> N >> M;
        int K = M/40+5;
        for(int i = 1; i<=N; i++){
            t[i] = i*10;
            v[i].clear();
            stop[i] = 0;
            if(i <= K){
                for(int k = 1; k<=40; k++){
                    pickup.push({t[i], i});
                }
            }
        }
        for(int i = 1; i<=M; i++){
            int a, b;
            cin >> a >> b;
            v[a].push_back(b);
        }
        for(int i= 1; i<=N; i++){
            vector<int> vec;
            while(dropoff.size() && dropoff.top().val == i){
                query q = dropoff.top();
                dropoff.pop();
                vec.push_back(q.bus);
                pickup.push({t[q.bus], q.bus});
            }
            for(int n : v[i]){
                while(pickup.top().val != t[pickup.top().bus]){
                    pickup.push({t[pickup.top().bus], pickup.top().bus});
                    pickup.pop();
                }
                query q = pickup.top();
                pickup.pop();
                vec.push_back(q.bus);
                dropoff.push({n, q.bus});
            }
            for(int n : vec){
                if(stop[n] != i){
                    stop[n] = i;
                    t[n]++;
                }
            }
        }
        int ans = 1;
        for(int i =1; i<=N; i++){
            ans = t[i] < t[ans] ? i : ans;
        }
        cout<< "Bus #"<< ans << endl;
    }
}
/*
5 3
1 2
2 3
4 5

16 20
11 13
14 15
4 16
2 7
14 16
7 13
1 3
11 13
13 14
2 4
2 8
5 8
10 11
9 14
2 10
13 16
11 14
6 8
15 16
3 8

13 6
1 7
2 8
3 9
4 10
5 11
6 12
*/