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