# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
639228 | classic | Robots (IOI13_robots) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int a, b, t;
cin >> a >> b >> t;
vector<int> x(a), y(b);
for (int i = 0; i < a; i++) {
cin >> x[i];
}
for (int i = 0; i < b; i++) {
cin >> y[i];
}
vector<pair<int, int>> c(t);
for (int i = 0; i < t; i++) {
cin >> c[i].first >> c[i].second;
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
sort(c.begin(), c.end());
int low = 1, hig = t;
int res = -1;
while (low <= hig) {
int mid = (low + hig) >> 1;
priority_queue<int> pq;
int idx = 0;
for (int i = 0; i < a; i++) {
while (idx < t && c[idx].first < x[i]) {
pq.emplace(c[idx].second);
idx += 1;
}
int cnt = 0;
while (!pq.empty() && cnt < mid) {
pq.pop();
cnt += 1;
}
}
while (idx < t) {
pq.emplace(c[idx].second);
idx += 1;
}
bool ok = true;
for (int i = b - 1; i >= 0; i--) {
int cnt = 0;
while (!pq.empty() && cnt < mid) {
if (pq.top() >= y[i]) {
ok = false;
}
pq.pop();
cnt += 1;
}
}
ok &= pq.empty();
if (ok) {
res = mid;
hig = mid - 1;
} else {
low = mid + 1;
}
}
cout << res;
return 0;
}