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

Jun 18th, 2022
999
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <queue>
4. #include <algorithm>
5.
6. using namespace std;
7.
8. int main() {
9.     int A, B, T;
10.     cin >> A >> B >> T;
11.     vector<int> X(A), Y(B);
12.     for (int &x : X) cin >> x;
13.     for (int &y : Y) cin >> y;
14.     vector<int> W(T), S(T);
15.     for (int i = 0; i < T; ++i) cin >> W[i] >> S[i];
16.
17.     sort(X.begin(), X.end());
18.     sort(Y.begin(), Y.end());
19.
20.     vector<pair<int, int>> byW(T);
21.     for (int i = 0; i < T; ++i) byW[i] = {W[i], i};
22.     sort(byW.begin(), byW.end());
23.
24.     priority_queue<pair<int, int>> byS;
25.
26.     int left = 0, right = T+1;
27.     while (left+1 < right) {
28.         int k = (left + right) / 2; // is it possible in at most k minutes
29.
30.         // Get all "weak" robots to take toys as large as possible
31.         int nextToy = 0;
32.         for (int i = 0; i < A; ++i) {
33.             while (nextToy < T && byW[nextToy].first < X[i]) {
34.                 byS.emplace(S[byW[nextToy].second], byW[nextToy].second);
35.                 nextToy++;
36.             }
37.             for (int j = 0; j < k && !byS.empty(); ++j) byS.pop(); // take k largest
38.         }
39.         while (nextToy < T) {
40.             byS.emplace(S[byW[nextToy].second], byW[nextToy].second);
41.             nextToy++;
42.         }
43.
44.         // Get all the "small" robots to take the rest
45.         for (int i = B-1; i >= 0 && !byS.empty(); --i) {
46.             if (byS.top().first >= Y[i]) continue;
47.             for (int j = 0; !byS.empty() && j < k; ++j) byS.pop();
48.         }
49.
50.         if (byS.empty()) right = k;
51.         else left = k;
52.
53.         while (!byS.empty()) byS.pop();
54.     }
55.     cout << (right > T ? -1 : right) << endl;
56.     return 0;
57. }