#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int big = 1010;
const int mxn = 1e6+10;
struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
struct node{
int mn,tag,cnt;
node(){}
};
node seg[mxn*4];
void build(int now,int l,int r){
if(l == r){
seg[now].cnt = 1;
return;
}
build(ls,l,mid);build(rs,mid+1,r);
seg[now].cnt = seg[ls].cnt+seg[rs].cnt;
}
void modify(int now,int l,int r,int s,int e,int v){
if(s>e)return;
if(l>=s&&e>=r){
seg[now].tag += v;
return;
}
if(mid>=s)modify(ls,l,mid,s,e,v);
if(mid<e)modify(rs,mid+1,r,s,e,v);
seg[now].mn = min(seg[ls].tag+seg[ls].mn,seg[rs].tag+seg[rs].mn);
seg[now].cnt = 0;
if(seg[ls].tag+seg[ls].mn == seg[now].mn)seg[now].cnt += seg[ls].cnt;
if(seg[rs].tag+seg[rs].mn == seg[now].mn)seg[now].cnt += seg[rs].cnt;
return;
}
#undef ls
#undef rs
#undef mid
};
SEG seg;
vector<vector<int>> grid;
pii pos[mxn];
int N,M;
void add(int r,int c,int coef = 1){
vector<int> v = {grid[r][c],grid[r][c+1],grid[r+1][c],grid[r+1][c+1]};
sort(v.begin(),v.end());
seg.modify(0,0,N*M-1,v[0],v[1]-1,coef);
seg.modify(0,0,N*M-1,v[2],v[3]-1,big*coef);
return;
}
int getans(){
int cnt = seg.seg[0].cnt,val = seg.seg[0].mn+seg.seg[0].tag;
if(val != 4)return 0;
else return cnt;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
N = H,M = W;
grid = vector<vector<int>>(N+2,vector<int>(M+2,N*M));
seg.build(0,0,N*M-1);
for(int i = 0;i<N*M;i++){
pos[i] = pii(R[i],C[i]);
pos[i].fs++;
pos[i].sc++;
grid[pos[i].fs][pos[i].sc] = i;
}
for(int i = 0;i<=N;i++){
for(int j = 0;j<=M;j++){
add(i,j,1);
}
}
return;
}
int swap_seats(int a, int b) {
pii pa = pos[a],pb = pos[b];
for(int i = -1;i<1;i++){
for(int j = -1;j<1;j++){
add(pa.fs+i,pa.sc+j,-1);
add(pb.fs+i,pb.sc+j,-1);
}
}
swap(pos[a],pos[b]);
swap(grid[pa.fs][pa.sc],grid[pb.fs][pb.sc]);
for(int i = -1;i<1;i++){
for(int j = -1;j<1;j++){
add(pa.fs+i,pa.sc+j,1);
add(pb.fs+i,pb.sc+j,1);
}
}
return getans();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
2504 KB |
Output is correct |
2 |
Correct |
14 ms |
2648 KB |
Output is correct |
3 |
Correct |
21 ms |
2652 KB |
Output is correct |
4 |
Correct |
14 ms |
2620 KB |
Output is correct |
5 |
Correct |
13 ms |
2648 KB |
Output is correct |
6 |
Correct |
19 ms |
2652 KB |
Output is correct |
7 |
Correct |
20 ms |
2624 KB |
Output is correct |
8 |
Correct |
18 ms |
2604 KB |
Output is correct |
9 |
Correct |
18 ms |
2652 KB |
Output is correct |
10 |
Correct |
20 ms |
2652 KB |
Output is correct |
11 |
Correct |
19 ms |
2612 KB |
Output is correct |
12 |
Correct |
13 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
2504 KB |
Output is correct |
2 |
Correct |
14 ms |
2648 KB |
Output is correct |
3 |
Correct |
21 ms |
2652 KB |
Output is correct |
4 |
Correct |
14 ms |
2620 KB |
Output is correct |
5 |
Correct |
13 ms |
2648 KB |
Output is correct |
6 |
Correct |
19 ms |
2652 KB |
Output is correct |
7 |
Correct |
20 ms |
2624 KB |
Output is correct |
8 |
Correct |
18 ms |
2604 KB |
Output is correct |
9 |
Correct |
18 ms |
2652 KB |
Output is correct |
10 |
Correct |
20 ms |
2652 KB |
Output is correct |
11 |
Correct |
19 ms |
2612 KB |
Output is correct |
12 |
Correct |
13 ms |
2652 KB |
Output is correct |
13 |
Correct |
47 ms |
2908 KB |
Output is correct |
14 |
Correct |
54 ms |
2976 KB |
Output is correct |
15 |
Correct |
36 ms |
3156 KB |
Output is correct |
16 |
Correct |
25 ms |
3420 KB |
Output is correct |
17 |
Correct |
41 ms |
3032 KB |
Output is correct |
18 |
Correct |
39 ms |
2904 KB |
Output is correct |
19 |
Correct |
37 ms |
2904 KB |
Output is correct |
20 |
Correct |
32 ms |
3164 KB |
Output is correct |
21 |
Correct |
25 ms |
3096 KB |
Output is correct |
22 |
Correct |
26 ms |
3420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1269 ms |
68700 KB |
Output is correct |
2 |
Correct |
729 ms |
68560 KB |
Output is correct |
3 |
Correct |
710 ms |
68688 KB |
Output is correct |
4 |
Correct |
582 ms |
68692 KB |
Output is correct |
5 |
Correct |
598 ms |
68444 KB |
Output is correct |
6 |
Correct |
540 ms |
68532 KB |
Output is correct |
7 |
Correct |
624 ms |
68572 KB |
Output is correct |
8 |
Correct |
665 ms |
68552 KB |
Output is correct |
9 |
Correct |
697 ms |
68536 KB |
Output is correct |
10 |
Correct |
641 ms |
68620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
46 ms |
2988 KB |
Output is correct |
2 |
Correct |
104 ms |
11864 KB |
Output is correct |
3 |
Correct |
619 ms |
68688 KB |
Output is correct |
4 |
Correct |
1265 ms |
68528 KB |
Output is correct |
5 |
Correct |
554 ms |
76376 KB |
Output is correct |
6 |
Correct |
1270 ms |
119368 KB |
Output is correct |
7 |
Correct |
589 ms |
70960 KB |
Output is correct |
8 |
Correct |
690 ms |
68612 KB |
Output is correct |
9 |
Correct |
608 ms |
68880 KB |
Output is correct |
10 |
Correct |
626 ms |
73172 KB |
Output is correct |
11 |
Correct |
605 ms |
91984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
43 ms |
4120 KB |
Output is correct |
2 |
Correct |
81 ms |
4080 KB |
Output is correct |
3 |
Correct |
124 ms |
4048 KB |
Output is correct |
4 |
Correct |
166 ms |
4048 KB |
Output is correct |
5 |
Correct |
259 ms |
5024 KB |
Output is correct |
6 |
Correct |
890 ms |
77344 KB |
Output is correct |
7 |
Correct |
1094 ms |
77316 KB |
Output is correct |
8 |
Correct |
871 ms |
77524 KB |
Output is correct |
9 |
Correct |
1795 ms |
77328 KB |
Output is correct |
10 |
Correct |
855 ms |
77520 KB |
Output is correct |
11 |
Correct |
856 ms |
77460 KB |
Output is correct |
12 |
Correct |
842 ms |
77288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
2504 KB |
Output is correct |
2 |
Correct |
14 ms |
2648 KB |
Output is correct |
3 |
Correct |
21 ms |
2652 KB |
Output is correct |
4 |
Correct |
14 ms |
2620 KB |
Output is correct |
5 |
Correct |
13 ms |
2648 KB |
Output is correct |
6 |
Correct |
19 ms |
2652 KB |
Output is correct |
7 |
Correct |
20 ms |
2624 KB |
Output is correct |
8 |
Correct |
18 ms |
2604 KB |
Output is correct |
9 |
Correct |
18 ms |
2652 KB |
Output is correct |
10 |
Correct |
20 ms |
2652 KB |
Output is correct |
11 |
Correct |
19 ms |
2612 KB |
Output is correct |
12 |
Correct |
13 ms |
2652 KB |
Output is correct |
13 |
Correct |
47 ms |
2908 KB |
Output is correct |
14 |
Correct |
54 ms |
2976 KB |
Output is correct |
15 |
Correct |
36 ms |
3156 KB |
Output is correct |
16 |
Correct |
25 ms |
3420 KB |
Output is correct |
17 |
Correct |
41 ms |
3032 KB |
Output is correct |
18 |
Correct |
39 ms |
2904 KB |
Output is correct |
19 |
Correct |
37 ms |
2904 KB |
Output is correct |
20 |
Correct |
32 ms |
3164 KB |
Output is correct |
21 |
Correct |
25 ms |
3096 KB |
Output is correct |
22 |
Correct |
26 ms |
3420 KB |
Output is correct |
23 |
Correct |
1269 ms |
68700 KB |
Output is correct |
24 |
Correct |
729 ms |
68560 KB |
Output is correct |
25 |
Correct |
710 ms |
68688 KB |
Output is correct |
26 |
Correct |
582 ms |
68692 KB |
Output is correct |
27 |
Correct |
598 ms |
68444 KB |
Output is correct |
28 |
Correct |
540 ms |
68532 KB |
Output is correct |
29 |
Correct |
624 ms |
68572 KB |
Output is correct |
30 |
Correct |
665 ms |
68552 KB |
Output is correct |
31 |
Correct |
697 ms |
68536 KB |
Output is correct |
32 |
Correct |
641 ms |
68620 KB |
Output is correct |
33 |
Correct |
46 ms |
2988 KB |
Output is correct |
34 |
Correct |
104 ms |
11864 KB |
Output is correct |
35 |
Correct |
619 ms |
68688 KB |
Output is correct |
36 |
Correct |
1265 ms |
68528 KB |
Output is correct |
37 |
Correct |
554 ms |
76376 KB |
Output is correct |
38 |
Correct |
1270 ms |
119368 KB |
Output is correct |
39 |
Correct |
589 ms |
70960 KB |
Output is correct |
40 |
Correct |
690 ms |
68612 KB |
Output is correct |
41 |
Correct |
608 ms |
68880 KB |
Output is correct |
42 |
Correct |
626 ms |
73172 KB |
Output is correct |
43 |
Correct |
605 ms |
91984 KB |
Output is correct |
44 |
Correct |
43 ms |
4120 KB |
Output is correct |
45 |
Correct |
81 ms |
4080 KB |
Output is correct |
46 |
Correct |
124 ms |
4048 KB |
Output is correct |
47 |
Correct |
166 ms |
4048 KB |
Output is correct |
48 |
Correct |
259 ms |
5024 KB |
Output is correct |
49 |
Correct |
890 ms |
77344 KB |
Output is correct |
50 |
Correct |
1094 ms |
77316 KB |
Output is correct |
51 |
Correct |
871 ms |
77524 KB |
Output is correct |
52 |
Correct |
1795 ms |
77328 KB |
Output is correct |
53 |
Correct |
855 ms |
77520 KB |
Output is correct |
54 |
Correct |
856 ms |
77460 KB |
Output is correct |
55 |
Correct |
842 ms |
77288 KB |
Output is correct |
56 |
Correct |
99 ms |
4200 KB |
Output is correct |
57 |
Correct |
206 ms |
4120 KB |
Output is correct |
58 |
Correct |
353 ms |
4396 KB |
Output is correct |
59 |
Correct |
1188 ms |
69500 KB |
Output is correct |
60 |
Correct |
1977 ms |
69456 KB |
Output is correct |
61 |
Correct |
1122 ms |
69500 KB |
Output is correct |
62 |
Correct |
889 ms |
73616 KB |
Output is correct |
63 |
Correct |
1986 ms |
72068 KB |
Output is correct |
64 |
Correct |
1248 ms |
70280 KB |
Output is correct |
65 |
Correct |
1082 ms |
69568 KB |
Output is correct |
66 |
Correct |
1174 ms |
69844 KB |
Output is correct |
67 |
Correct |
1249 ms |
74120 KB |
Output is correct |
68 |
Correct |
1006 ms |
83808 KB |
Output is correct |
69 |
Correct |
1851 ms |
93004 KB |
Output is correct |