IOI '13 P5 - Robots (Standard I/O)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    int A, B, T;
    cin >> A >> B >> T;
    vector<int> X(A), Y(B);
    for (int &x : X) cin >> x;
    for (int &y : Y) cin >> y;
    vector<int> W(T), S(T);
    for (int i = 0; i < T; ++i) cin >> W[i] >> S[i];

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());

    vector<pair<int, int>> byW(T);
    for (int i = 0; i < T; ++i) byW[i] = {W[i], i};
    sort(byW.begin(), byW.end());

    priority_queue<pair<int, int>> byS;

    int left = 0, right = T+1;
    while (left+1 < right) {
        int k = (left + right) / 2; // is it possible in at most k minutes

        // Get all "weak" robots to take toys as large as possible
        int nextToy = 0;
        for (int i = 0; i < A; ++i) {
            while (nextToy < T && byW[nextToy].first < X[i]) {
                byS.emplace(S[byW[nextToy].second], byW[nextToy].second);
                nextToy++;
            }
            for (int j = 0; j < k && !byS.empty(); ++j) byS.pop(); // take k largest
        }
        while (nextToy < T) {
            byS.emplace(S[byW[nextToy].second], byW[nextToy].second);
            nextToy++;
        }

        // Get all the "small" robots to take the rest
        for (int i = B-1; i >= 0 && !byS.empty(); --i) {
            if (byS.top().first >= Y[i]) continue;
            for (int j = 0; !byS.empty() && j < k; ++j) byS.pop();
        }

        if (byS.empty()) right = k;
        else left = k;

        while (!byS.empty()) byS.pop();
    }
    cout << (right > T ? -1 : right) << endl;
    return 0;
}