| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 712060 | sharaelong | 로봇 (IOI13_robots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#ifdef SHARAELONG
#include "../../cpp-header/debug.hpp"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct FenwickTree {
vector<int> tree;
FenwickTree(int size) {
tree.resize(size+1, 0);
}
int sum(int pos) {
int ret = 0;
for (int i=pos+1; i>0; i &= (i-1)) ret += tree[i];
return ret;
}
void add(int pos, int val) {
for (int i=pos+1; i<tree.size(); i+=(i & -i)) tree[i] += val;
}
};
void solve() {
int a, b, t;
cin >> a >> b >> t;
vector<int> A(a), B(b);
for (int& x: A) cin >> x;
for (int& x: B) cin >> x;
A.push_back(0);
B.push_back(0);
sort(A.begin(), A.end());
sort(B.begin(), B.end());
vector<pii> toys(t);
for (int i=0; i<t; ++i) {
int w, s;
cin >> w >> s;
w = upper_bound(A.begin(), A.end(), w) - A.begin() - 1;
s = upper_bound(B.begin(), B.end(), s) - B.begin() - 1;
toys[i] = {w,s};
}
sort(toys.begin(), toys.end(), [](const pii& p, const pii& q) {
if (p.second == q.second) return p.first > q.first;
return p.second > q.second;
});
if (toys[0] == make_pair(a, b)) {
cout << -1;
return;
}
int ans = 1;
FenwickTree fen(a+1);
for (auto[x, y]: toys) {
fen.add(x, 1);
ans = max(ans, (fen.sum(a) - fen.sum(x-1) - 1) / (a+b-x-y) + 1);
}
cout << ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}