# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
75110 |
2018-09-08T11:36:41 Z |
Namnamseo |
Seats (IOI18_seats) |
C++17 |
|
2454 ms |
56848 KB |
#include <bits/stdc++.h>
using namespace std;
int n, h, w;
int z;
const int M = 1048576;
int tree[M<<1];
int lazy[M<<1];
int cmn[M<<1];
int iv[int(1e6)+10];
inline void pd(int p){
if(!lazy[p]) return;
for(int c=p*2; c<=p*2+1; ++c){
tree[c] += lazy[p];
lazy[c] += lazy[p];
}
lazy[p]=0;
}
inline void gather(int p){
if(tree[p*2] == tree[p*2+1]){
tree[p] = tree[p*2];
cmn[p] = cmn[p*2]+cmn[p*2+1];
} else if(tree[p*2] > tree[p*2+1]){
tree[p] = tree[p*2+1];
cmn[p] = cmn[p*2+1];
} else {
tree[p] = tree[p*2];
cmn[p] = cmn[p*2];
}
}
void init(int p=1, int l=1, int r=n){
if(l==r){
tree[p]=iv[l];
cmn[p]=1;
return;
}
int mid=(l+r)/2;
init(p*2, l, mid);
init(p*2+1, mid+1, r);
gather(p);
}
void upd(int l, int r, int v, int mp=1, int ml=1, int mr=n){
if(r<ml || mr<l) return;
if(ml!=mr) pd(mp);
if(l<=ml && mr<=r){
tree[mp] += v;
lazy[mp] += v;
return;
}
int mid=(ml+mr)/2;
upd(l,r,v, mp*2, ml, mid);
upd(l,r,v, mp*2+1, mid+1, mr);
gather(mp);
}
inline void addr(int x, int y){
if(x>=y) return;
upd(x, y-1, 1);
}
inline void delr(int x, int y){
if(x>=y) return;
upd(x, y-1, -1);
}
int Arr[3*int(1e6)+10];
int arr[4];
inline void add(int x, int y){
arr[0]=Arr[x*z+y]; if(!arr[0]) arr[0]=1e9;
arr[1]=Arr[x*z+y+1]; if(!arr[1]) arr[1]=1e9;
arr[2]=Arr[(x+1)*z+y]; if(!arr[2]) arr[2]=1e9;
arr[3]=Arr[(x+1)*z+y+1]; if(!arr[3]) arr[3]=1e9;
sort(arr, arr+4);
addr(arr[0], arr[1]);
addr(arr[2], arr[3]);
}
inline void del(int x, int y){
arr[0]=Arr[x*z+y]; if(!arr[0]) arr[0]=1e9;
arr[1]=Arr[x*z+y+1]; if(!arr[1]) arr[1]=1e9;
arr[2]=Arr[(x+1)*z+y]; if(!arr[2]) arr[2]=1e9;
arr[3]=Arr[(x+1)*z+y+1]; if(!arr[3]) arr[3]=1e9;
sort(arr, arr+4);
delr(arr[0], arr[1]);
delr(arr[2], arr[3]);
}
int mx[int(1e6)+1];
int my[int(1e6)+1];
inline void addr2(int x, int y){
if(x>=y) return;
y = min(y, n+1);
iv[x]+=1;
iv[y]-=1;
}
inline void add2(int x, int y){
arr[0]=Arr[x*z+y]; if(!arr[0]) arr[0]=1e9;
arr[1]=Arr[x*z+y+1]; if(!arr[1]) arr[1]=1e9;
arr[2]=Arr[(x+1)*z+y]; if(!arr[2]) arr[2]=1e9;
arr[3]=Arr[(x+1)*z+y+1]; if(!arr[3]) arr[3]=1e9;
sort(arr, arr+4);
addr2(arr[0], arr[1]);
addr2(arr[2], arr[3]);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h=H; w=W; n=h*w;
z=w+2;
for(int i=1; i<=n; ++i){
int x=R[i-1]+1, y=C[i-1]+1;
mx[i]=x; my[i]=y;
Arr[x*z+y] = i;
}
for(int i=0; i<=h; ++i){
for(int j=0; j<=w; ++j){
add2(i, j);
}
}
for(int i=1; i<=n; ++i) iv[i]+=iv[i-1];
init();
}
#define rep(i,n) for(int i=0; i<(n); ++i)
int swap_seats(int A, int B) {
++A; ++B;
int ax=mx[A], ay=my[A];
rep(dx,2) rep(dy,2) del(ax-dx, ay-dy);
Arr[ax*z+ay]=B;
rep(dx,2) rep(dy,2) add(ax-dx, ay-dy);
int bx=mx[B], by=my[B];
rep(dx,2) rep(dy,2) del(bx-dx, by-dy);
Arr[bx*z+by]=A;
rep(dx,2) rep(dy,2) add(bx-dx, by-dy);
mx[A]=bx; my[A]=by;
mx[B]=ax; my[B]=ay;
return (tree[1]==4) ? (cmn[1]) : 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
504 KB |
Output is correct |
2 |
Correct |
28 ms |
628 KB |
Output is correct |
3 |
Correct |
42 ms |
692 KB |
Output is correct |
4 |
Correct |
25 ms |
692 KB |
Output is correct |
5 |
Correct |
20 ms |
692 KB |
Output is correct |
6 |
Correct |
36 ms |
716 KB |
Output is correct |
7 |
Correct |
39 ms |
760 KB |
Output is correct |
8 |
Correct |
35 ms |
760 KB |
Output is correct |
9 |
Correct |
35 ms |
760 KB |
Output is correct |
10 |
Correct |
38 ms |
760 KB |
Output is correct |
11 |
Correct |
35 ms |
760 KB |
Output is correct |
12 |
Correct |
24 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
504 KB |
Output is correct |
2 |
Correct |
28 ms |
628 KB |
Output is correct |
3 |
Correct |
42 ms |
692 KB |
Output is correct |
4 |
Correct |
25 ms |
692 KB |
Output is correct |
5 |
Correct |
20 ms |
692 KB |
Output is correct |
6 |
Correct |
36 ms |
716 KB |
Output is correct |
7 |
Correct |
39 ms |
760 KB |
Output is correct |
8 |
Correct |
35 ms |
760 KB |
Output is correct |
9 |
Correct |
35 ms |
760 KB |
Output is correct |
10 |
Correct |
38 ms |
760 KB |
Output is correct |
11 |
Correct |
35 ms |
760 KB |
Output is correct |
12 |
Correct |
24 ms |
760 KB |
Output is correct |
13 |
Correct |
83 ms |
1400 KB |
Output is correct |
14 |
Correct |
97 ms |
1436 KB |
Output is correct |
15 |
Correct |
59 ms |
1436 KB |
Output is correct |
16 |
Correct |
38 ms |
1564 KB |
Output is correct |
17 |
Correct |
64 ms |
1564 KB |
Output is correct |
18 |
Correct |
65 ms |
1564 KB |
Output is correct |
19 |
Correct |
59 ms |
1724 KB |
Output is correct |
20 |
Correct |
50 ms |
1724 KB |
Output is correct |
21 |
Correct |
40 ms |
1724 KB |
Output is correct |
22 |
Correct |
37 ms |
1724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
638 ms |
48952 KB |
Output is correct |
2 |
Correct |
488 ms |
48952 KB |
Output is correct |
3 |
Correct |
503 ms |
49060 KB |
Output is correct |
4 |
Correct |
481 ms |
49060 KB |
Output is correct |
5 |
Correct |
527 ms |
49060 KB |
Output is correct |
6 |
Correct |
509 ms |
49060 KB |
Output is correct |
7 |
Correct |
501 ms |
49060 KB |
Output is correct |
8 |
Correct |
499 ms |
49060 KB |
Output is correct |
9 |
Correct |
494 ms |
49060 KB |
Output is correct |
10 |
Correct |
502 ms |
49060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
49060 KB |
Output is correct |
2 |
Correct |
134 ms |
49060 KB |
Output is correct |
3 |
Correct |
494 ms |
49060 KB |
Output is correct |
4 |
Correct |
686 ms |
49060 KB |
Output is correct |
5 |
Correct |
478 ms |
49060 KB |
Output is correct |
6 |
Correct |
711 ms |
56848 KB |
Output is correct |
7 |
Correct |
486 ms |
56848 KB |
Output is correct |
8 |
Correct |
502 ms |
56848 KB |
Output is correct |
9 |
Correct |
524 ms |
56848 KB |
Output is correct |
10 |
Correct |
504 ms |
56848 KB |
Output is correct |
11 |
Correct |
594 ms |
56848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
56848 KB |
Output is correct |
2 |
Correct |
123 ms |
56848 KB |
Output is correct |
3 |
Correct |
203 ms |
56848 KB |
Output is correct |
4 |
Correct |
290 ms |
56848 KB |
Output is correct |
5 |
Correct |
498 ms |
56848 KB |
Output is correct |
6 |
Correct |
1066 ms |
56848 KB |
Output is correct |
7 |
Correct |
1066 ms |
56848 KB |
Output is correct |
8 |
Correct |
1042 ms |
56848 KB |
Output is correct |
9 |
Correct |
1353 ms |
56848 KB |
Output is correct |
10 |
Correct |
890 ms |
56848 KB |
Output is correct |
11 |
Correct |
1085 ms |
56848 KB |
Output is correct |
12 |
Correct |
903 ms |
56848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
504 KB |
Output is correct |
2 |
Correct |
28 ms |
628 KB |
Output is correct |
3 |
Correct |
42 ms |
692 KB |
Output is correct |
4 |
Correct |
25 ms |
692 KB |
Output is correct |
5 |
Correct |
20 ms |
692 KB |
Output is correct |
6 |
Correct |
36 ms |
716 KB |
Output is correct |
7 |
Correct |
39 ms |
760 KB |
Output is correct |
8 |
Correct |
35 ms |
760 KB |
Output is correct |
9 |
Correct |
35 ms |
760 KB |
Output is correct |
10 |
Correct |
38 ms |
760 KB |
Output is correct |
11 |
Correct |
35 ms |
760 KB |
Output is correct |
12 |
Correct |
24 ms |
760 KB |
Output is correct |
13 |
Correct |
83 ms |
1400 KB |
Output is correct |
14 |
Correct |
97 ms |
1436 KB |
Output is correct |
15 |
Correct |
59 ms |
1436 KB |
Output is correct |
16 |
Correct |
38 ms |
1564 KB |
Output is correct |
17 |
Correct |
64 ms |
1564 KB |
Output is correct |
18 |
Correct |
65 ms |
1564 KB |
Output is correct |
19 |
Correct |
59 ms |
1724 KB |
Output is correct |
20 |
Correct |
50 ms |
1724 KB |
Output is correct |
21 |
Correct |
40 ms |
1724 KB |
Output is correct |
22 |
Correct |
37 ms |
1724 KB |
Output is correct |
23 |
Correct |
638 ms |
48952 KB |
Output is correct |
24 |
Correct |
488 ms |
48952 KB |
Output is correct |
25 |
Correct |
503 ms |
49060 KB |
Output is correct |
26 |
Correct |
481 ms |
49060 KB |
Output is correct |
27 |
Correct |
527 ms |
49060 KB |
Output is correct |
28 |
Correct |
509 ms |
49060 KB |
Output is correct |
29 |
Correct |
501 ms |
49060 KB |
Output is correct |
30 |
Correct |
499 ms |
49060 KB |
Output is correct |
31 |
Correct |
494 ms |
49060 KB |
Output is correct |
32 |
Correct |
502 ms |
49060 KB |
Output is correct |
33 |
Correct |
80 ms |
49060 KB |
Output is correct |
34 |
Correct |
134 ms |
49060 KB |
Output is correct |
35 |
Correct |
494 ms |
49060 KB |
Output is correct |
36 |
Correct |
686 ms |
49060 KB |
Output is correct |
37 |
Correct |
478 ms |
49060 KB |
Output is correct |
38 |
Correct |
711 ms |
56848 KB |
Output is correct |
39 |
Correct |
486 ms |
56848 KB |
Output is correct |
40 |
Correct |
502 ms |
56848 KB |
Output is correct |
41 |
Correct |
524 ms |
56848 KB |
Output is correct |
42 |
Correct |
504 ms |
56848 KB |
Output is correct |
43 |
Correct |
594 ms |
56848 KB |
Output is correct |
44 |
Correct |
60 ms |
56848 KB |
Output is correct |
45 |
Correct |
123 ms |
56848 KB |
Output is correct |
46 |
Correct |
203 ms |
56848 KB |
Output is correct |
47 |
Correct |
290 ms |
56848 KB |
Output is correct |
48 |
Correct |
498 ms |
56848 KB |
Output is correct |
49 |
Correct |
1066 ms |
56848 KB |
Output is correct |
50 |
Correct |
1066 ms |
56848 KB |
Output is correct |
51 |
Correct |
1042 ms |
56848 KB |
Output is correct |
52 |
Correct |
1353 ms |
56848 KB |
Output is correct |
53 |
Correct |
890 ms |
56848 KB |
Output is correct |
54 |
Correct |
1085 ms |
56848 KB |
Output is correct |
55 |
Correct |
903 ms |
56848 KB |
Output is correct |
56 |
Correct |
157 ms |
56848 KB |
Output is correct |
57 |
Correct |
415 ms |
56848 KB |
Output is correct |
58 |
Correct |
654 ms |
56848 KB |
Output is correct |
59 |
Correct |
1656 ms |
56848 KB |
Output is correct |
60 |
Correct |
2454 ms |
56848 KB |
Output is correct |
61 |
Correct |
1350 ms |
56848 KB |
Output is correct |
62 |
Correct |
1110 ms |
56848 KB |
Output is correct |
63 |
Correct |
2097 ms |
56848 KB |
Output is correct |
64 |
Correct |
1451 ms |
56848 KB |
Output is correct |
65 |
Correct |
1338 ms |
56848 KB |
Output is correct |
66 |
Correct |
1579 ms |
56848 KB |
Output is correct |
67 |
Correct |
1422 ms |
56848 KB |
Output is correct |
68 |
Correct |
1152 ms |
56848 KB |
Output is correct |
69 |
Correct |
1857 ms |
56848 KB |
Output is correct |