| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 444302 | qwerasdfzxcl | 로봇 (IOI13_robots) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[100100], b[100100], cnt[100100], n, x, y;
pair<int, int> c[1001000];
bool col[1001000];
struct DSU{
int path[100100], e[100100], h[100100], sz;
void init(int n){
sz = n;
for (int i=0;i<n;i++) path[i] = e[i] = i, h[i] = 0;
}
int find(int s){
if (s==path[s]) return s;
return path[s] = find(path[s]);
}
void update(int s){e[s] = s+1;}
void merge(int s, int v){
int x = find(s), y = find(v);
if (x==y) return;
if (h[x]>h[y]) swap(x, y);
path[x] = y;
e[y] = max(e[x], e[y]);
if (h[x]==h[y]) h[y]++;
}
int _end(int s){
if (s==sz) return s;
return e[find(s)];
}
}dsu;
bool solve(int m){
///init
for (int i=0;i<x;i++) cnt[i] = 0;
for (int i=0;i<n;i++) col[i] = 0;
dsu.init(n);
///
for (int i=0;i<n;i++){
int tmp = dsu._end(c[i].second);
//if (m==2) printf("%d\n", tmp);
if (tmp==y) continue;
cnt[tmp]++;
col[i] = 1;
if (cnt[tmp]==m){
dsu.update(tmp);
if (tmp>0 && cnt[tmp-1]==m) dsu.merge(tmp-1, tmp);
if (tmp<x-1 && cnt[tmp+1]==m) dsu.merge(tmp, tmp+1);
}
}
int pt = x-1;
for (int i=0;i<y;i++) cnt[i] = 0;
for (int i=0;i<n;i++) if (!col[i]){
if (pt<c[i].first) return 0;
cnt[pt]++;
if (cnt[pt]==m) pt--;
}
return 1;
}
int main(){
scanf("%d %d %d", &x, &y, &n);
for (int i=0;i<x;i++) scanf("%d", a+i);
for (int i=0;i<y;i++) scanf("%d", b+i);
sort(a, a+x); sort(b, b+y);
for (int i=0;i<n;i++){
scanf("%d %d", &c[i].first, &c[i].second);
c[i].first = upper_bound(a, a+x, c[i].first) - a;
c[i].second = upper_bound(b, b+y, c[i].second) - b;
if (c[i].first==x && c[i].second==y){
printf("-1\n"); return 0;
}
}
sort(c, c+n, greater<pair<int, int>>());
//for (int i=0;i<n;i++) printf(" %d %d\n", c[i].first, c[i].second);
int l = 1, r = 1001000, ans = 1001000;
while(l<r){
int m = (l+r)>>1;
if (solve(m)) r = m, ans = m;
else l = m+1;
}
assert(ans!=1001000);
printf("%d\n", ans);
return 0;
}