| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 82020 | zoooma13 | 로봇 (IOI13_robots) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define MAX_T 1000006
#define MAX_A 50004
#define We first
#define Si second
int A ,B ,T;
int Weak[MAX_A];
int Small[MAX_A];
pair <int ,int> Toy[MAX_T];
pair <int ,int> WeTs[MAX_T];
pair <int ,int> SiTs[MAX_T];
bool can(int X)
{
int Weak_ptr = 0;
priority_queue <int> pq;
for(int i=0; i<A; i++)
{
while(Weak_ptr < T && WeTs[Weak_ptr].We < Weak[i])
pq.push(WeTs[Weak_ptr++].Si);
int CanHave = X;
while(!pq.empty() && CanHave--)
pq.pop();
}
while(Weak_ptr < T)
pq.push(WeTs[Weak_ptr++].Si);
for(int i=B-1; ~i; i--)
{
int CanHave = X;
while(CanHave-- && !pq.empty() && pq.top() < Small[i])
pq.pop();
}
return pq.empty();
}
int main()
{
scanf("%d%d%d",&A,&B,&T);
for(int i=0; i<A; i++)
scanf("%d",&Weak[i]);
for(int i=0; i<B; i++)
scanf("%d",&Small[i]);
for(int i=0; i<T; i++)
{
scanf("%d%d",&Toy[i].We,&Toy[i].Si);
SiTs[i] = WeTs[i] = Toy[i];
}
sort(Weak ,Weak+A);
sort(Small ,Small+B);
sort(SiTs ,SiTs+T ,[](auto i ,auto j){return i.Si < j.Si;});
sort(WeTs ,WeTs+T ,[](auto i ,auto j){return i.We < j.We;});
int st = 1 ,en = T ,mid;
while(st <= en)
{
mid = (st+en)>>1;
if(can(mid))
en = mid-1;
else
st = mid+1;
}
cout << (en == T ? -1 : en+1) << endl;
}