#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pf printf
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
#define maxn 4000005
int h,w,n;
vector<int> r,c;
vector<vector<int>> a;
int lz[maxn];
ii v[maxn];//{min element,#min}
void init(int i,int s,int e){
v[i]={0,e-s+1};
if(s!=e){
int m=(s+e)>>1;
init(2*i+1,s,m);
init(2*i+2,m+1,e);
}
}
void ppo(int i,int s,int e){
v[i].fi+=lz[i];
if(s!=e){
int m=(s+e)>>1;
lz[2*i+1]+=lz[i];
lz[2*i+2]+=lz[i];
}
lz[i]=0;
}
void up(int i,int s,int e,int x,int y,int nv){
if(s==x&&e==y){lz[i]+=nv;return;}
int m=(s+e)>>1;
if(y<=m)up(2*i+1,s,m,x,y,nv);
else if(x>m)up(2*i+2,m+1,e,x,y,nv);
else up(2*i+1,s,m,x,m,nv),up(2*i+2,m+1,e,m+1,y,nv);
ppo(2*i+1,s,m);ppo(2*i+2,m+1,e);
if(v[2*i+1].fi==v[2*i+2].fi)v[i]={v[2*i+1].fi,v[2*i+1].se+v[2*i+2].se};
else v[i]=min(v[2*i+1],v[2*i+2]);
}
inline void up(int x,int y,int nv){
if(x>y)return;
up(0,0,n-1,x,y,nv);
}
inline int qry(){
if(v[0].fi+lz[0]==4)return v[0].se;
return 0;
}
inline void upd(int r,int c,int m){//update 2x2 with (r,c) as top left
vector<int> v={a[r][c],a[r][c+1],a[r+1][c],a[r+1][c+1]};
sort(all(v));
up(v[0],v[1]-1,m*1);//3 white 1 black, +-1
up(v[2],v[3]-1,m*5);//3 black 1 white, +-inf(=5 since max is 4)
}
inline void upd2(int r,int c,int m){//update all squares containing (r,c)
upd(r,c,m);
upd(r-1,c,m);
upd(r,c-1,m);
upd(r-1,c-1,m);
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C){
h=H;w=W;n=h*w;
for(int i:R)r.pb(i+1);
for(int i:C)c.pb(i+1);
a.resize(h+2);
for(int i=0;i<h+2;++i){
a[i].resize(w+2,h*w);
}
for(int i=0;i<h*w;++i){
a[r[i]][c[i]]=i;
}
init(0,0,n-1);
for(int i=0;i<=h;++i){
for(int j=0;j<=w;++j){
upd(i,j,1);
}
}
}
int swap_seats(int x,int y){
upd2(r[x],c[x],-1);
upd2(r[y],c[y],-1);
swap(a[r[x]][c[x]],a[r[y]][c[y]]);
swap(r[x],r[y]);
swap(c[x],c[y]);
upd2(r[x],c[x],1);
upd2(r[y],c[y],1);
return qry();
}
Compilation message
seats.cpp: In function 'void ppo(int, int, int)':
seats.cpp:33:7: warning: unused variable 'm' [-Wunused-variable]
33 | int m=(s+e)>>1;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
468 KB |
Output is correct |
2 |
Correct |
18 ms |
444 KB |
Output is correct |
3 |
Correct |
29 ms |
464 KB |
Output is correct |
4 |
Correct |
17 ms |
440 KB |
Output is correct |
5 |
Correct |
15 ms |
476 KB |
Output is correct |
6 |
Correct |
24 ms |
468 KB |
Output is correct |
7 |
Correct |
26 ms |
448 KB |
Output is correct |
8 |
Correct |
24 ms |
460 KB |
Output is correct |
9 |
Correct |
24 ms |
448 KB |
Output is correct |
10 |
Correct |
26 ms |
464 KB |
Output is correct |
11 |
Correct |
24 ms |
468 KB |
Output is correct |
12 |
Correct |
16 ms |
448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
468 KB |
Output is correct |
2 |
Correct |
18 ms |
444 KB |
Output is correct |
3 |
Correct |
29 ms |
464 KB |
Output is correct |
4 |
Correct |
17 ms |
440 KB |
Output is correct |
5 |
Correct |
15 ms |
476 KB |
Output is correct |
6 |
Correct |
24 ms |
468 KB |
Output is correct |
7 |
Correct |
26 ms |
448 KB |
Output is correct |
8 |
Correct |
24 ms |
460 KB |
Output is correct |
9 |
Correct |
24 ms |
448 KB |
Output is correct |
10 |
Correct |
26 ms |
464 KB |
Output is correct |
11 |
Correct |
24 ms |
468 KB |
Output is correct |
12 |
Correct |
16 ms |
448 KB |
Output is correct |
13 |
Correct |
68 ms |
1240 KB |
Output is correct |
14 |
Correct |
80 ms |
1224 KB |
Output is correct |
15 |
Correct |
47 ms |
1308 KB |
Output is correct |
16 |
Correct |
33 ms |
1716 KB |
Output is correct |
17 |
Correct |
56 ms |
1244 KB |
Output is correct |
18 |
Correct |
55 ms |
1220 KB |
Output is correct |
19 |
Correct |
49 ms |
1244 KB |
Output is correct |
20 |
Correct |
43 ms |
1364 KB |
Output is correct |
21 |
Correct |
34 ms |
1220 KB |
Output is correct |
22 |
Correct |
36 ms |
1740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1776 ms |
68392 KB |
Output is correct |
2 |
Correct |
1028 ms |
68416 KB |
Output is correct |
3 |
Correct |
1037 ms |
68508 KB |
Output is correct |
4 |
Correct |
849 ms |
68400 KB |
Output is correct |
5 |
Correct |
918 ms |
68392 KB |
Output is correct |
6 |
Correct |
867 ms |
68364 KB |
Output is correct |
7 |
Correct |
944 ms |
68396 KB |
Output is correct |
8 |
Correct |
962 ms |
68652 KB |
Output is correct |
9 |
Correct |
1034 ms |
68436 KB |
Output is correct |
10 |
Correct |
942 ms |
68380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
62 ms |
1216 KB |
Output is correct |
2 |
Correct |
141 ms |
7224 KB |
Output is correct |
3 |
Correct |
873 ms |
68452 KB |
Output is correct |
4 |
Correct |
1733 ms |
68460 KB |
Output is correct |
5 |
Correct |
844 ms |
76368 KB |
Output is correct |
6 |
Correct |
1829 ms |
119340 KB |
Output is correct |
7 |
Correct |
868 ms |
70936 KB |
Output is correct |
8 |
Correct |
1065 ms |
68416 KB |
Output is correct |
9 |
Correct |
953 ms |
68884 KB |
Output is correct |
10 |
Correct |
957 ms |
73064 KB |
Output is correct |
11 |
Correct |
920 ms |
91852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
1904 KB |
Output is correct |
2 |
Correct |
91 ms |
2004 KB |
Output is correct |
3 |
Correct |
144 ms |
1948 KB |
Output is correct |
4 |
Correct |
202 ms |
2088 KB |
Output is correct |
5 |
Correct |
336 ms |
2852 KB |
Output is correct |
6 |
Correct |
1292 ms |
77244 KB |
Output is correct |
7 |
Correct |
1475 ms |
77336 KB |
Output is correct |
8 |
Correct |
1276 ms |
77284 KB |
Output is correct |
9 |
Correct |
2365 ms |
77292 KB |
Output is correct |
10 |
Correct |
1207 ms |
77308 KB |
Output is correct |
11 |
Correct |
1237 ms |
77336 KB |
Output is correct |
12 |
Correct |
1193 ms |
77352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
468 KB |
Output is correct |
2 |
Correct |
18 ms |
444 KB |
Output is correct |
3 |
Correct |
29 ms |
464 KB |
Output is correct |
4 |
Correct |
17 ms |
440 KB |
Output is correct |
5 |
Correct |
15 ms |
476 KB |
Output is correct |
6 |
Correct |
24 ms |
468 KB |
Output is correct |
7 |
Correct |
26 ms |
448 KB |
Output is correct |
8 |
Correct |
24 ms |
460 KB |
Output is correct |
9 |
Correct |
24 ms |
448 KB |
Output is correct |
10 |
Correct |
26 ms |
464 KB |
Output is correct |
11 |
Correct |
24 ms |
468 KB |
Output is correct |
12 |
Correct |
16 ms |
448 KB |
Output is correct |
13 |
Correct |
68 ms |
1240 KB |
Output is correct |
14 |
Correct |
80 ms |
1224 KB |
Output is correct |
15 |
Correct |
47 ms |
1308 KB |
Output is correct |
16 |
Correct |
33 ms |
1716 KB |
Output is correct |
17 |
Correct |
56 ms |
1244 KB |
Output is correct |
18 |
Correct |
55 ms |
1220 KB |
Output is correct |
19 |
Correct |
49 ms |
1244 KB |
Output is correct |
20 |
Correct |
43 ms |
1364 KB |
Output is correct |
21 |
Correct |
34 ms |
1220 KB |
Output is correct |
22 |
Correct |
36 ms |
1740 KB |
Output is correct |
23 |
Correct |
1776 ms |
68392 KB |
Output is correct |
24 |
Correct |
1028 ms |
68416 KB |
Output is correct |
25 |
Correct |
1037 ms |
68508 KB |
Output is correct |
26 |
Correct |
849 ms |
68400 KB |
Output is correct |
27 |
Correct |
918 ms |
68392 KB |
Output is correct |
28 |
Correct |
867 ms |
68364 KB |
Output is correct |
29 |
Correct |
944 ms |
68396 KB |
Output is correct |
30 |
Correct |
962 ms |
68652 KB |
Output is correct |
31 |
Correct |
1034 ms |
68436 KB |
Output is correct |
32 |
Correct |
942 ms |
68380 KB |
Output is correct |
33 |
Correct |
62 ms |
1216 KB |
Output is correct |
34 |
Correct |
141 ms |
7224 KB |
Output is correct |
35 |
Correct |
873 ms |
68452 KB |
Output is correct |
36 |
Correct |
1733 ms |
68460 KB |
Output is correct |
37 |
Correct |
844 ms |
76368 KB |
Output is correct |
38 |
Correct |
1829 ms |
119340 KB |
Output is correct |
39 |
Correct |
868 ms |
70936 KB |
Output is correct |
40 |
Correct |
1065 ms |
68416 KB |
Output is correct |
41 |
Correct |
953 ms |
68884 KB |
Output is correct |
42 |
Correct |
957 ms |
73064 KB |
Output is correct |
43 |
Correct |
920 ms |
91852 KB |
Output is correct |
44 |
Correct |
63 ms |
1904 KB |
Output is correct |
45 |
Correct |
91 ms |
2004 KB |
Output is correct |
46 |
Correct |
144 ms |
1948 KB |
Output is correct |
47 |
Correct |
202 ms |
2088 KB |
Output is correct |
48 |
Correct |
336 ms |
2852 KB |
Output is correct |
49 |
Correct |
1292 ms |
77244 KB |
Output is correct |
50 |
Correct |
1475 ms |
77336 KB |
Output is correct |
51 |
Correct |
1276 ms |
77284 KB |
Output is correct |
52 |
Correct |
2365 ms |
77292 KB |
Output is correct |
53 |
Correct |
1207 ms |
77308 KB |
Output is correct |
54 |
Correct |
1237 ms |
77336 KB |
Output is correct |
55 |
Correct |
1193 ms |
77352 KB |
Output is correct |
56 |
Correct |
112 ms |
1924 KB |
Output is correct |
57 |
Correct |
280 ms |
1980 KB |
Output is correct |
58 |
Correct |
472 ms |
2832 KB |
Output is correct |
59 |
Correct |
1727 ms |
69316 KB |
Output is correct |
60 |
Correct |
2769 ms |
69500 KB |
Output is correct |
61 |
Correct |
1600 ms |
69424 KB |
Output is correct |
62 |
Correct |
1317 ms |
73244 KB |
Output is correct |
63 |
Correct |
2655 ms |
71984 KB |
Output is correct |
64 |
Correct |
1777 ms |
70164 KB |
Output is correct |
65 |
Correct |
1662 ms |
69416 KB |
Output is correct |
66 |
Correct |
1771 ms |
69928 KB |
Output is correct |
67 |
Correct |
1799 ms |
74144 KB |
Output is correct |
68 |
Correct |
1429 ms |
83620 KB |
Output is correct |
69 |
Correct |
2594 ms |
92724 KB |
Output is correct |