| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 254785 | erd1 | 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;
#define pb push_back
typedef pair<int, int> pii;
typedef int64_t lld;
typedef long double ld;
//#define int lld
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
/*
pii operator+(pii a, pii b){
return {a.ff+b.ff, a.ss+b.ss};
}
pii& operator+=(pii& a, pii b){
return a.ff+=b.ff, a.ss+=b.ss, a;
}
*/
template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
for(Iter i = b; i != e; i++)out << *i << " ";
return out;
}
template<typename T>
ostream& operator<<(ostream& out, vector<T> v){
return outIt(out << '[', all(v)) << ']';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
return out << '(' << p.ff << ", " << p.ss << ')';
}
vector<int> A, B;
vector<pii> h;
priority_queue<int, vector<int>, less<int>> mxh;
priority_queue<int, vector<int>, greater<int>> mnh;
signed main(){
cin.tie(0);ios_base::sync_with_stdio(0);
int a, b, n;
cin >> a >> b >> n;
A.resize(a), B.resize(b);
for(auto& i: A)cin >> i;
for(auto& i: B)cin >> i;
h.resize(n);
for(auto& i: h)cin >> i.ff >> i.ss;
sort(all(h));
sort(all(A));
sort(all(B));
int l = 0, r = n+1;
while(r-l > 1){
int j = 0;
//cout << (l+r>>1) << endl;
for(int i = 0; i < a; i++){
while(j < n && h[j].ff <= A[i])mxh.push(h[j].ss), j++;
for(int k = 0; k < (l+r>>1) && mxh.size(); k++)
mxh.pop();
}
while(j < n)mnh.push(h[j].ss), j++;
while(mxh.size())mnh.push(mxh.top()), mxh.pop();
//for(auto i: mts)cout << i << " ";cout << endl;
for(int i = 0; i < b; i++)
for(int k = 0; k < (l+r>>1) && mnh.size() && mnh.top() <= B[i]; k++)
mnh.pop();
(mnh.size()?l:r) = l+r>>1;
while(mnh.size())mnh.pop();
}
cout << (r==n+1?-1:r) << endl;
}