#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,seg[4000009],segmn[4000009],seg2[4000009],n,l,r,z,zz,za,jm[4000009];
pair <int, int> p[1000009];
vector <vector <int> > f;
void pushdown(int q, int w, int rr){
if(q!=w){
seg2[rr*2]+=seg2[rr];
seg2[rr*2+1]+=seg2[rr];
}
segmn[rr]+=seg2[rr];
seg2[rr]=0;
}
void upd(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
seg2[rr]=z;
pushdown(q,w,rr);
return;
}
upd(q,(q+w)/2,rr*2);
upd((q+w)/2+1,w,rr*2+1);
if(segmn[rr*2]<segmn[rr*2+1]){
seg[rr]=seg[rr*2];
segmn[rr]=segmn[rr*2];
}
if(segmn[rr*2+1]<segmn[rr*2]){
seg[rr]=seg[rr*2+1];
segmn[rr]=segmn[rr*2+1];
}
if(segmn[rr*2]==segmn[rr*2+1]){
seg[rr]=seg[rr*2]+seg[rr*2+1];
segmn[rr]=segmn[rr*2];
}
}
void read(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
if(z>segmn[rr]){
zz=seg[rr];
z=segmn[rr];
}else{
if(z==segmn[rr]){
zz+=seg[rr];
}
}
return;
}
read(q,(q+w)/2,rr*2);
read((q+w)/2+1,w,rr*2+1);
}
void update(int q, int w, int rr){
int X[6];
X[1]=f[q][w];
X[2]=f[q+1][w];
X[3]=f[q][w+1];
X[4]=f[q+1][w+1];
sort(X+1,X+5);
l=X[1];r=X[2]-1;z=rr;
if(l<=r) upd(1,za,1);
l=X[3];r=X[4]-1;z=rr*6;
if(l<=r) upd(1,za,1);
}
void update2(int q, int w, int rr){
int X[6];
X[1]=f[q][w];
X[2]=f[q+1][w];
X[3]=f[q][w+1];
X[4]=f[q+1][w+1];
sort(X+1,X+5);
l=X[1];r=X[2]-1;z=rr;
if(l<=r){
jm[l]+=z;
jm[r+1]-=z;
}
l=X[3];r=X[4]-1;z=rr*6;
if(l<=r){
jm[l]+=z;
jm[r+1]-=z;
}
}
void bld(int q, int w, int rr){
segmn[rr]=0;seg[rr]=w-q+1;
if(q==w) return;
bld(q,(q+w)/2,rr*2);
bld((q+w)/2+1,w,rr*2+1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
a=H;b=W;
n=a*b;
f.resize(H+6);
za=1;
while(za<n+6) za*=2;
bld(1,za,1);
for(i=0; i<=H+4; i++){
f[i].resize(W+6);
}
for(i=1; i<=H*W; i++){
R[i-1]++;C[i-1]++;
p[i].first=R[i-1];
p[i].second=C[i-1];
f[R[i-1]][C[i-1]]=i;
}
for(i=0; i<=H+1; i++){
f[i][0]=f[i][W+1]=n+4;
}
for(i=0; i<=W+1; i++){
f[0][i]=f[H+1][i]=n+4;
}
for(i=0; i<=H; i++){
for(j=0; j<=W; j++){
update2(i,j,1);
}
}
for(i=1; i<=za; i++){
jm[i]+=jm[i-1];
seg[za+i-1]=1;
segmn[za+i-1]=jm[i];
}
for(int rr=za-1; rr>=1; rr--){
if(segmn[rr*2]<segmn[rr*2+1]){
seg[rr]=seg[rr*2];
segmn[rr]=segmn[rr*2];
}
if(segmn[rr*2+1]<segmn[rr*2]){
seg[rr]=seg[rr*2+1];
segmn[rr]=segmn[rr*2+1];
}
if(segmn[rr*2]==segmn[rr*2+1]){
seg[rr]=seg[rr*2]+seg[rr*2+1];
segmn[rr]=segmn[rr*2];
}
}
}
void UPD(int q, int w, int rr){
update(q-1,w-1,rr);
update(q-1,w,rr);
update(q,w-1,rr);
update(q,w,rr);
}
int swap_seats(int C, int D) {
C++;D++;
c=C;d=D;
UPD(p[c].first,p[c].second,-1);
f[p[c].first][p[c].second]=d;
UPD(p[c].first,p[c].second,1);
UPD(p[d].first,p[d].second,-1);
f[p[d].first][p[d].second]=c;
UPD(p[d].first,p[d].second,1);
swap(p[c],p[d]);
z=n+2;zz=0;
l=1;r=n;
read(1,za,1);
if(z!=4){
return 0;
}else{
return zz;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
404 KB |
Output is correct |
2 |
Correct |
26 ms |
400 KB |
Output is correct |
3 |
Correct |
38 ms |
392 KB |
Output is correct |
4 |
Correct |
23 ms |
412 KB |
Output is correct |
5 |
Correct |
21 ms |
392 KB |
Output is correct |
6 |
Correct |
36 ms |
524 KB |
Output is correct |
7 |
Correct |
36 ms |
332 KB |
Output is correct |
8 |
Correct |
33 ms |
392 KB |
Output is correct |
9 |
Correct |
33 ms |
408 KB |
Output is correct |
10 |
Correct |
36 ms |
396 KB |
Output is correct |
11 |
Correct |
32 ms |
408 KB |
Output is correct |
12 |
Correct |
21 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
404 KB |
Output is correct |
2 |
Correct |
26 ms |
400 KB |
Output is correct |
3 |
Correct |
38 ms |
392 KB |
Output is correct |
4 |
Correct |
23 ms |
412 KB |
Output is correct |
5 |
Correct |
21 ms |
392 KB |
Output is correct |
6 |
Correct |
36 ms |
524 KB |
Output is correct |
7 |
Correct |
36 ms |
332 KB |
Output is correct |
8 |
Correct |
33 ms |
392 KB |
Output is correct |
9 |
Correct |
33 ms |
408 KB |
Output is correct |
10 |
Correct |
36 ms |
396 KB |
Output is correct |
11 |
Correct |
32 ms |
408 KB |
Output is correct |
12 |
Correct |
21 ms |
460 KB |
Output is correct |
13 |
Correct |
90 ms |
1064 KB |
Output is correct |
14 |
Correct |
100 ms |
972 KB |
Output is correct |
15 |
Correct |
54 ms |
1228 KB |
Output is correct |
16 |
Correct |
44 ms |
1716 KB |
Output is correct |
17 |
Correct |
69 ms |
1144 KB |
Output is correct |
18 |
Correct |
73 ms |
1064 KB |
Output is correct |
19 |
Correct |
68 ms |
1100 KB |
Output is correct |
20 |
Correct |
57 ms |
1368 KB |
Output is correct |
21 |
Correct |
44 ms |
1252 KB |
Output is correct |
22 |
Correct |
45 ms |
1740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
631 ms |
48400 KB |
Output is correct |
2 |
Correct |
490 ms |
48944 KB |
Output is correct |
3 |
Correct |
493 ms |
48996 KB |
Output is correct |
4 |
Correct |
492 ms |
49008 KB |
Output is correct |
5 |
Correct |
488 ms |
48988 KB |
Output is correct |
6 |
Correct |
498 ms |
49068 KB |
Output is correct |
7 |
Correct |
491 ms |
48944 KB |
Output is correct |
8 |
Correct |
490 ms |
48992 KB |
Output is correct |
9 |
Correct |
483 ms |
48944 KB |
Output is correct |
10 |
Correct |
481 ms |
48940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
89 ms |
1068 KB |
Output is correct |
2 |
Correct |
130 ms |
5428 KB |
Output is correct |
3 |
Correct |
472 ms |
48420 KB |
Output is correct |
4 |
Correct |
599 ms |
49012 KB |
Output is correct |
5 |
Correct |
477 ms |
68484 KB |
Output is correct |
6 |
Correct |
819 ms |
115364 KB |
Output is correct |
7 |
Correct |
471 ms |
55344 KB |
Output is correct |
8 |
Correct |
496 ms |
49068 KB |
Output is correct |
9 |
Correct |
490 ms |
49336 KB |
Output is correct |
10 |
Correct |
496 ms |
55152 KB |
Output is correct |
11 |
Correct |
507 ms |
79972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
96 ms |
1344 KB |
Output is correct |
2 |
Correct |
123 ms |
1296 KB |
Output is correct |
3 |
Correct |
206 ms |
1500 KB |
Output is correct |
4 |
Correct |
292 ms |
1328 KB |
Output is correct |
5 |
Correct |
499 ms |
2156 KB |
Output is correct |
6 |
Correct |
1103 ms |
68936 KB |
Output is correct |
7 |
Correct |
1169 ms |
69044 KB |
Output is correct |
8 |
Correct |
1112 ms |
69184 KB |
Output is correct |
9 |
Correct |
1348 ms |
69028 KB |
Output is correct |
10 |
Correct |
1024 ms |
69040 KB |
Output is correct |
11 |
Correct |
1038 ms |
69072 KB |
Output is correct |
12 |
Correct |
1010 ms |
68952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
404 KB |
Output is correct |
2 |
Correct |
26 ms |
400 KB |
Output is correct |
3 |
Correct |
38 ms |
392 KB |
Output is correct |
4 |
Correct |
23 ms |
412 KB |
Output is correct |
5 |
Correct |
21 ms |
392 KB |
Output is correct |
6 |
Correct |
36 ms |
524 KB |
Output is correct |
7 |
Correct |
36 ms |
332 KB |
Output is correct |
8 |
Correct |
33 ms |
392 KB |
Output is correct |
9 |
Correct |
33 ms |
408 KB |
Output is correct |
10 |
Correct |
36 ms |
396 KB |
Output is correct |
11 |
Correct |
32 ms |
408 KB |
Output is correct |
12 |
Correct |
21 ms |
460 KB |
Output is correct |
13 |
Correct |
90 ms |
1064 KB |
Output is correct |
14 |
Correct |
100 ms |
972 KB |
Output is correct |
15 |
Correct |
54 ms |
1228 KB |
Output is correct |
16 |
Correct |
44 ms |
1716 KB |
Output is correct |
17 |
Correct |
69 ms |
1144 KB |
Output is correct |
18 |
Correct |
73 ms |
1064 KB |
Output is correct |
19 |
Correct |
68 ms |
1100 KB |
Output is correct |
20 |
Correct |
57 ms |
1368 KB |
Output is correct |
21 |
Correct |
44 ms |
1252 KB |
Output is correct |
22 |
Correct |
45 ms |
1740 KB |
Output is correct |
23 |
Correct |
631 ms |
48400 KB |
Output is correct |
24 |
Correct |
490 ms |
48944 KB |
Output is correct |
25 |
Correct |
493 ms |
48996 KB |
Output is correct |
26 |
Correct |
492 ms |
49008 KB |
Output is correct |
27 |
Correct |
488 ms |
48988 KB |
Output is correct |
28 |
Correct |
498 ms |
49068 KB |
Output is correct |
29 |
Correct |
491 ms |
48944 KB |
Output is correct |
30 |
Correct |
490 ms |
48992 KB |
Output is correct |
31 |
Correct |
483 ms |
48944 KB |
Output is correct |
32 |
Correct |
481 ms |
48940 KB |
Output is correct |
33 |
Correct |
89 ms |
1068 KB |
Output is correct |
34 |
Correct |
130 ms |
5428 KB |
Output is correct |
35 |
Correct |
472 ms |
48420 KB |
Output is correct |
36 |
Correct |
599 ms |
49012 KB |
Output is correct |
37 |
Correct |
477 ms |
68484 KB |
Output is correct |
38 |
Correct |
819 ms |
115364 KB |
Output is correct |
39 |
Correct |
471 ms |
55344 KB |
Output is correct |
40 |
Correct |
496 ms |
49068 KB |
Output is correct |
41 |
Correct |
490 ms |
49336 KB |
Output is correct |
42 |
Correct |
496 ms |
55152 KB |
Output is correct |
43 |
Correct |
507 ms |
79972 KB |
Output is correct |
44 |
Correct |
96 ms |
1344 KB |
Output is correct |
45 |
Correct |
123 ms |
1296 KB |
Output is correct |
46 |
Correct |
206 ms |
1500 KB |
Output is correct |
47 |
Correct |
292 ms |
1328 KB |
Output is correct |
48 |
Correct |
499 ms |
2156 KB |
Output is correct |
49 |
Correct |
1103 ms |
68936 KB |
Output is correct |
50 |
Correct |
1169 ms |
69044 KB |
Output is correct |
51 |
Correct |
1112 ms |
69184 KB |
Output is correct |
52 |
Correct |
1348 ms |
69028 KB |
Output is correct |
53 |
Correct |
1024 ms |
69040 KB |
Output is correct |
54 |
Correct |
1038 ms |
69072 KB |
Output is correct |
55 |
Correct |
1010 ms |
68952 KB |
Output is correct |
56 |
Correct |
161 ms |
1640 KB |
Output is correct |
57 |
Correct |
369 ms |
1740 KB |
Output is correct |
58 |
Correct |
711 ms |
2436 KB |
Output is correct |
59 |
Correct |
1657 ms |
49508 KB |
Output is correct |
60 |
Correct |
2385 ms |
49516 KB |
Output is correct |
61 |
Correct |
1502 ms |
66052 KB |
Output is correct |
62 |
Correct |
1327 ms |
75852 KB |
Output is correct |
63 |
Correct |
2081 ms |
72532 KB |
Output is correct |
64 |
Correct |
1631 ms |
68020 KB |
Output is correct |
65 |
Correct |
1492 ms |
66212 KB |
Output is correct |
66 |
Correct |
1804 ms |
66552 KB |
Output is correct |
67 |
Correct |
1689 ms |
72232 KB |
Output is correct |
68 |
Correct |
1403 ms |
85540 KB |
Output is correct |
69 |
Correct |
2182 ms |
97332 KB |
Output is correct |