| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 639228 | classic | 로봇 (IOI13_robots) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}