| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 355434 | rrrr10000 | 로봇 (IOI13_robots) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define dame(a) {cout<<a<<endl;return 0;}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vvvp=vector<vvp>;
using vb=vector<bool>;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
// #include"robots.h"
int putaway(int A,int B,int n,int X[],int Y[],int W[],int S[]){
vi x(A),y(B);rep(i,A)x[i]=X[i];rep(i,B)y[i]=Y[i];sort(all(x));rsort(y);
vp v(n);
rep(i,n)v[i]=P(W[i],S[i]);
sort(all(v));
ll ok=n+1,ng=0;
while(ok-ng>1){
ll md=(ok+ng)/2;
ll w=0;
priority_queue<ll> pq;
rep(i,A){
while(w<n&&v[w].fi<x[i])pq.push(v[w++].se);
rep(j,md){
if(pq.empty())break;
pq.pop();
}
}
while(w<n)pq.push(v[w++].se);
rep(i,B){
rep(j,md){
if(pq.empty()||pq.top()>=y[i])break;
pq.pop();
}
}
if(pq.empty())ok=md;
else ng=md;
}
if(ok==n+1)return -1;
return ok;
}
int main(){
int n,a,b;cin>>a>>b>>n;
int x[10],y[10],w[10],s[10];
rep(i,a)cin>>x[i];
rep(i,b)cin>>y[i];
rep(i,n)cin>>w[i]>>s[i];
out(putaway(a,b,n,x,y,w,s));
}