| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 639240 | 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>
#include "robots.h"
using namespace std;
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
sort(x, x + a);
sort(y, y + b);
vector<pair<int, int>> c;
for (int i = 0; i < t; i++) {
c.emplace_back(w[i], s[i]);
}
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;
}
}
return res;
}
const int N = 1e6 + 1;
int x_[N], y_[N], w_[N], s_[N];
int main() {
freopen("robots.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int a, b, t;
cin >> a >> b >> t;
for (int i = 0; i < a; i++) {
cin >> x_[i];
}
for (int i = 0; i < b; i++) {
cin >> y_[i];
}
for (int i = 0; i < t; i++) {
cin >> w_[i] >> s_[i];
}
cout << putaway(a, b, t, x_, y_, w_, s_);
return 0;
}