#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define pb push_back
#define F first
#define S second
#define lc v<<1
#define rc v<<1|1
const int N = 1e6 + 10, inf = 1.05e9;
int n,m,lz[N*4],dx[]={0,0,1,1},dy[]={0,1,1,0},s;
pii f[N*4];
vector<int> A[N],r,c;
void build(int v, int l, int r){
f[v].S=r-l;
if(r-l==1) return;
int m=(l+r)>>1;
build(lc,l,m);
build(rc,m,r);
}
void shift(int v, int l, int r){
f[v].F+=lz[v];
if(r-l>1){
lz[lc]+=lz[v];
lz[rc]+=lz[v];
}
lz[v]=0;
}
void upd(int v, int l, int r, int tl, int tr, int x){
shift(v,l,r);
if(l>=tr || tl>=r || tl>=tr) return;
if(l>=tl && r<=tr){
lz[v]=x;
return shift(v,l,r);
}
int m=(l+r)>>1;
upd(lc,l,m,tl,tr,x);
upd(rc,m,r,tl,tr,x);
f[v].F=min(f[lc].F,f[rc].F);
f[v].S=0;
if(f[v].F==f[lc].F) f[v].S+=f[lc].S;
if(f[v].F==f[rc].F) f[v].S+=f[rc].S;
}
void calc(int x, int y, int k){
vector<int> vec;
for(int i=0; i<4; i++){
vec.pb(A[x+dx[i]][y+dy[i]]);
}
sort(vec.begin(),vec.end());
upd(1,0,s,vec[0],vec[1],k);
upd(1,0,s,vec[2],vec[3],k);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n=H;
m=W;
r=R;
c=C;
s=n*m;
build(1,0,s);
for(int i=0; i<=n+1; i++) A[i].resize(m+2,inf);
for(int i=0; i<s; i++){
r[i]++;
c[i]++;
A[r[i]][c[i]]=i;
}
for(int i=0; i<=n; i++) for(int j=0; j<=m; j++) calc(i,j,1);
}
int swap_seats(int a, int b) {
for(int i=0; i<4; i++){
calc(r[a]-dx[i],c[a]-dy[i],-1);
calc(r[b]-dx[i],c[b]-dy[i],-1);
}
swap(A[r[a]][c[a]],A[r[b]][c[b]]);
swap(r[a],r[b]);
swap(c[a],c[b]);
for(int i=0; i<4; i++){
calc(r[a]-dx[i],c[a]-dy[i],1);
calc(r[b]-dx[i],c[b]-dy[i],1);
}
return f[1].S;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
23892 KB |
Output is correct |
2 |
Correct |
38 ms |
23892 KB |
Output is correct |
3 |
Correct |
54 ms |
23944 KB |
Output is correct |
4 |
Correct |
40 ms |
23916 KB |
Output is correct |
5 |
Correct |
36 ms |
24064 KB |
Output is correct |
6 |
Correct |
48 ms |
23924 KB |
Output is correct |
7 |
Correct |
51 ms |
23904 KB |
Output is correct |
8 |
Correct |
44 ms |
23916 KB |
Output is correct |
9 |
Correct |
46 ms |
23920 KB |
Output is correct |
10 |
Correct |
50 ms |
23916 KB |
Output is correct |
11 |
Correct |
46 ms |
24044 KB |
Output is correct |
12 |
Correct |
43 ms |
23976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
23892 KB |
Output is correct |
2 |
Correct |
38 ms |
23892 KB |
Output is correct |
3 |
Correct |
54 ms |
23944 KB |
Output is correct |
4 |
Correct |
40 ms |
23916 KB |
Output is correct |
5 |
Correct |
36 ms |
24064 KB |
Output is correct |
6 |
Correct |
48 ms |
23924 KB |
Output is correct |
7 |
Correct |
51 ms |
23904 KB |
Output is correct |
8 |
Correct |
44 ms |
23916 KB |
Output is correct |
9 |
Correct |
46 ms |
23920 KB |
Output is correct |
10 |
Correct |
50 ms |
23916 KB |
Output is correct |
11 |
Correct |
46 ms |
24044 KB |
Output is correct |
12 |
Correct |
43 ms |
23976 KB |
Output is correct |
13 |
Correct |
105 ms |
24664 KB |
Output is correct |
14 |
Correct |
112 ms |
24576 KB |
Output is correct |
15 |
Correct |
73 ms |
24788 KB |
Output is correct |
16 |
Correct |
57 ms |
24892 KB |
Output is correct |
17 |
Correct |
79 ms |
24660 KB |
Output is correct |
18 |
Correct |
79 ms |
24660 KB |
Output is correct |
19 |
Correct |
70 ms |
24692 KB |
Output is correct |
20 |
Correct |
64 ms |
24804 KB |
Output is correct |
21 |
Correct |
63 ms |
24660 KB |
Output is correct |
22 |
Correct |
56 ms |
24952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2194 ms |
78344 KB |
Output is correct |
2 |
Correct |
1186 ms |
78020 KB |
Output is correct |
3 |
Correct |
1076 ms |
77900 KB |
Output is correct |
4 |
Correct |
1072 ms |
77832 KB |
Output is correct |
5 |
Correct |
1078 ms |
77976 KB |
Output is correct |
6 |
Correct |
1016 ms |
77792 KB |
Output is correct |
7 |
Correct |
1108 ms |
77972 KB |
Output is correct |
8 |
Correct |
1169 ms |
78116 KB |
Output is correct |
9 |
Correct |
1107 ms |
77916 KB |
Output is correct |
10 |
Correct |
1122 ms |
77948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
24664 KB |
Output is correct |
2 |
Correct |
197 ms |
30688 KB |
Output is correct |
3 |
Correct |
1124 ms |
78476 KB |
Output is correct |
4 |
Correct |
2190 ms |
78520 KB |
Output is correct |
5 |
Correct |
1122 ms |
86296 KB |
Output is correct |
6 |
Correct |
2491 ms |
110736 KB |
Output is correct |
7 |
Correct |
1100 ms |
85956 KB |
Output is correct |
8 |
Correct |
1178 ms |
83412 KB |
Output is correct |
9 |
Correct |
1182 ms |
83488 KB |
Output is correct |
10 |
Correct |
1175 ms |
85612 KB |
Output is correct |
11 |
Correct |
1120 ms |
95268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
141 ms |
25416 KB |
Output is correct |
2 |
Correct |
175 ms |
25616 KB |
Output is correct |
3 |
Correct |
228 ms |
25532 KB |
Output is correct |
4 |
Correct |
327 ms |
25528 KB |
Output is correct |
5 |
Correct |
457 ms |
26324 KB |
Output is correct |
6 |
Correct |
1730 ms |
90036 KB |
Output is correct |
7 |
Correct |
1926 ms |
87756 KB |
Output is correct |
8 |
Correct |
1602 ms |
87744 KB |
Output is correct |
9 |
Correct |
2940 ms |
87676 KB |
Output is correct |
10 |
Correct |
1602 ms |
87676 KB |
Output is correct |
11 |
Correct |
1499 ms |
100724 KB |
Output is correct |
12 |
Correct |
1508 ms |
100684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
23892 KB |
Output is correct |
2 |
Correct |
38 ms |
23892 KB |
Output is correct |
3 |
Correct |
54 ms |
23944 KB |
Output is correct |
4 |
Correct |
40 ms |
23916 KB |
Output is correct |
5 |
Correct |
36 ms |
24064 KB |
Output is correct |
6 |
Correct |
48 ms |
23924 KB |
Output is correct |
7 |
Correct |
51 ms |
23904 KB |
Output is correct |
8 |
Correct |
44 ms |
23916 KB |
Output is correct |
9 |
Correct |
46 ms |
23920 KB |
Output is correct |
10 |
Correct |
50 ms |
23916 KB |
Output is correct |
11 |
Correct |
46 ms |
24044 KB |
Output is correct |
12 |
Correct |
43 ms |
23976 KB |
Output is correct |
13 |
Correct |
105 ms |
24664 KB |
Output is correct |
14 |
Correct |
112 ms |
24576 KB |
Output is correct |
15 |
Correct |
73 ms |
24788 KB |
Output is correct |
16 |
Correct |
57 ms |
24892 KB |
Output is correct |
17 |
Correct |
79 ms |
24660 KB |
Output is correct |
18 |
Correct |
79 ms |
24660 KB |
Output is correct |
19 |
Correct |
70 ms |
24692 KB |
Output is correct |
20 |
Correct |
64 ms |
24804 KB |
Output is correct |
21 |
Correct |
63 ms |
24660 KB |
Output is correct |
22 |
Correct |
56 ms |
24952 KB |
Output is correct |
23 |
Correct |
2194 ms |
78344 KB |
Output is correct |
24 |
Correct |
1186 ms |
78020 KB |
Output is correct |
25 |
Correct |
1076 ms |
77900 KB |
Output is correct |
26 |
Correct |
1072 ms |
77832 KB |
Output is correct |
27 |
Correct |
1078 ms |
77976 KB |
Output is correct |
28 |
Correct |
1016 ms |
77792 KB |
Output is correct |
29 |
Correct |
1108 ms |
77972 KB |
Output is correct |
30 |
Correct |
1169 ms |
78116 KB |
Output is correct |
31 |
Correct |
1107 ms |
77916 KB |
Output is correct |
32 |
Correct |
1122 ms |
77948 KB |
Output is correct |
33 |
Correct |
101 ms |
24664 KB |
Output is correct |
34 |
Correct |
197 ms |
30688 KB |
Output is correct |
35 |
Correct |
1124 ms |
78476 KB |
Output is correct |
36 |
Correct |
2190 ms |
78520 KB |
Output is correct |
37 |
Correct |
1122 ms |
86296 KB |
Output is correct |
38 |
Correct |
2491 ms |
110736 KB |
Output is correct |
39 |
Correct |
1100 ms |
85956 KB |
Output is correct |
40 |
Correct |
1178 ms |
83412 KB |
Output is correct |
41 |
Correct |
1182 ms |
83488 KB |
Output is correct |
42 |
Correct |
1175 ms |
85612 KB |
Output is correct |
43 |
Correct |
1120 ms |
95268 KB |
Output is correct |
44 |
Correct |
141 ms |
25416 KB |
Output is correct |
45 |
Correct |
175 ms |
25616 KB |
Output is correct |
46 |
Correct |
228 ms |
25532 KB |
Output is correct |
47 |
Correct |
327 ms |
25528 KB |
Output is correct |
48 |
Correct |
457 ms |
26324 KB |
Output is correct |
49 |
Correct |
1730 ms |
90036 KB |
Output is correct |
50 |
Correct |
1926 ms |
87756 KB |
Output is correct |
51 |
Correct |
1602 ms |
87744 KB |
Output is correct |
52 |
Correct |
2940 ms |
87676 KB |
Output is correct |
53 |
Correct |
1602 ms |
87676 KB |
Output is correct |
54 |
Correct |
1499 ms |
100724 KB |
Output is correct |
55 |
Correct |
1508 ms |
100684 KB |
Output is correct |
56 |
Correct |
210 ms |
25404 KB |
Output is correct |
57 |
Correct |
462 ms |
25436 KB |
Output is correct |
58 |
Correct |
638 ms |
26128 KB |
Output is correct |
59 |
Correct |
1981 ms |
89876 KB |
Output is correct |
60 |
Correct |
3311 ms |
86288 KB |
Output is correct |
61 |
Correct |
1852 ms |
91152 KB |
Output is correct |
62 |
Correct |
1574 ms |
90896 KB |
Output is correct |
63 |
Correct |
3248 ms |
92544 KB |
Output is correct |
64 |
Correct |
2305 ms |
93644 KB |
Output is correct |
65 |
Correct |
1890 ms |
92852 KB |
Output is correct |
66 |
Correct |
2126 ms |
92836 KB |
Output is correct |
67 |
Correct |
2068 ms |
95232 KB |
Output is correct |
68 |
Correct |
1793 ms |
99308 KB |
Output is correct |
69 |
Correct |
3639 ms |
104520 KB |
Output is correct |