#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e6;
int H, W, R[MAXN+10], C[MAXN+10];
vector<vector<int>> A;
int psum1[MAXN+10], psum2[MAXN+10];
pii val[4*MAXN+10], lazy[4*MAXN+10];
int cnt[4*MAXN+10];
void init(int node, int tl, int tr)
{
if(tl==tr)
{
val[node]={psum1[tl], psum2[tl]};
cnt[node]=1;
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
if(val[node*2]==val[node*2+1]) val[node]=val[node*2], cnt[node]=cnt[node*2]+cnt[node*2+1];
else if(val[node*2]<val[node*2+1]) val[node]=val[node*2], cnt[node]=cnt[node*2];
else val[node]=val[node*2+1], cnt[node]=cnt[node*2+1];
}
void busy(int node, int tl, int tr)
{
if(lazy[node]==pii(0, 0)) return;
val[node].first+=lazy[node].first;
val[node].second+=lazy[node].second;
if(tl!=tr)
{
lazy[node*2].first+=lazy[node].first; lazy[node*2].second+=lazy[node].second;
lazy[node*2+1].first+=lazy[node].first; lazy[node*2+1].second+=lazy[node].second;
}
lazy[node]=pii(0, 0);
}
void update(int node, int tl, int tr, int l, int r, int v, int t)
{
busy(node, tl, tr);
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
if(t==1) lazy[node].first+=v;
else lazy[node].second+=v;
busy(node, tl, tr);
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, v, t);
update(node*2+1, mid+1, tr, l, r, v, t);
if(val[node*2]==val[node*2+1]) val[node]=val[node*2], cnt[node]=cnt[node*2]+cnt[node*2+1];
else if(val[node*2]<val[node*2+1]) val[node]=val[node*2], cnt[node]=cnt[node*2];
else val[node]=val[node*2+1], cnt[node]=cnt[node*2+1];
}
int query()
{
busy(1, 1, H*W);
if(val[1]==pii(4, 0)) return cnt[1];
else return 0;
}
void give_initial_chart(int _H, int _W, vector<int> _R, vector<int> _C)
{
int i, j;
H=_H; W=_W; A=vector<vector<int>>(H+2, vector<int>(W+2, H*W+1));
for(i=0; i<H*W; i++) R[i+1]=_R[i]+1, C[i+1]=_C[i]+1;
for(i=1; i<=H*W; i++) A[R[i]][C[i]]=i;
for(i=0; i<=H; i++) for(j=0; j<=W; j++)
{
vector<int> V;
V.push_back(A[i][j]);
V.push_back(A[i+1][j]);
V.push_back(A[i][j+1]);
V.push_back(A[i+1][j+1]);
sort(V.begin(), V.end());
psum1[V[0]]++; psum1[V[1]]--;
psum2[V[2]]++; psum2[V[3]]--;
}
for(i=1; i<=H*W; i++) psum1[i]+=psum1[i-1], psum2[i]+=psum2[i-1];
init(1, 1, H*W);
}
void update(int y, int x, int val)
{
vector<int> V;
V.push_back(A[y][x]);
V.push_back(A[y+1][x]);
V.push_back(A[y][x+1]);
V.push_back(A[y+1][x+1]);
sort(V.begin(), V.end());
update(1, 1, H*W, V[0], V[1]-1, val, 1);
update(1, 1, H*W, V[2], V[3]-1, val, 2);
}
int swap_seats(int a, int b)
{
int i, j;
a++; b++;
update(R[a]-1, C[a]-1, -1);
update(R[a], C[a]-1, -1);
update(R[a]-1, C[a], -1);
update(R[a], C[a], -1);
update(R[b]-1, C[b]-1, -1);
update(R[b], C[b]-1, -1);
update(R[b]-1, C[b], -1);
update(R[b], C[b], -1);
swap(R[a], R[b]); swap(C[a], C[b]); swap(A[R[a]][C[a]], A[R[b]][C[b]]);
update(R[a]-1, C[a]-1, 1);
update(R[a], C[a]-1, 1);
update(R[a]-1, C[a], 1);
update(R[a], C[a], 1);
update(R[b]-1, C[b]-1, 1);
update(R[b], C[b]-1, 1);
update(R[b]-1, C[b], 1);
update(R[b], C[b], 1);
return query();
}
Compilation message
seats.cpp: In function 'void init(int, int, int)':
seats.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
seats.cpp: In function 'void update(int, int, int, int, int, int, int)':
seats.cpp:58:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:111:9: warning: unused variable 'i' [-Wunused-variable]
int i, j;
^
seats.cpp:111:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
632 KB |
Output is correct |
2 |
Correct |
43 ms |
504 KB |
Output is correct |
3 |
Correct |
62 ms |
632 KB |
Output is correct |
4 |
Correct |
46 ms |
632 KB |
Output is correct |
5 |
Correct |
37 ms |
632 KB |
Output is correct |
6 |
Correct |
54 ms |
504 KB |
Output is correct |
7 |
Correct |
58 ms |
504 KB |
Output is correct |
8 |
Correct |
52 ms |
604 KB |
Output is correct |
9 |
Correct |
52 ms |
632 KB |
Output is correct |
10 |
Correct |
59 ms |
632 KB |
Output is correct |
11 |
Correct |
55 ms |
632 KB |
Output is correct |
12 |
Correct |
39 ms |
608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
632 KB |
Output is correct |
2 |
Correct |
43 ms |
504 KB |
Output is correct |
3 |
Correct |
62 ms |
632 KB |
Output is correct |
4 |
Correct |
46 ms |
632 KB |
Output is correct |
5 |
Correct |
37 ms |
632 KB |
Output is correct |
6 |
Correct |
54 ms |
504 KB |
Output is correct |
7 |
Correct |
58 ms |
504 KB |
Output is correct |
8 |
Correct |
52 ms |
604 KB |
Output is correct |
9 |
Correct |
52 ms |
632 KB |
Output is correct |
10 |
Correct |
59 ms |
632 KB |
Output is correct |
11 |
Correct |
55 ms |
632 KB |
Output is correct |
12 |
Correct |
39 ms |
608 KB |
Output is correct |
13 |
Correct |
121 ms |
1636 KB |
Output is correct |
14 |
Correct |
132 ms |
1624 KB |
Output is correct |
15 |
Correct |
77 ms |
1656 KB |
Output is correct |
16 |
Correct |
64 ms |
2168 KB |
Output is correct |
17 |
Correct |
100 ms |
1656 KB |
Output is correct |
18 |
Correct |
94 ms |
1636 KB |
Output is correct |
19 |
Correct |
90 ms |
1664 KB |
Output is correct |
20 |
Correct |
77 ms |
1812 KB |
Output is correct |
21 |
Correct |
62 ms |
1656 KB |
Output is correct |
22 |
Correct |
63 ms |
2304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
924 ms |
84856 KB |
Output is correct |
2 |
Correct |
721 ms |
85028 KB |
Output is correct |
3 |
Correct |
730 ms |
85000 KB |
Output is correct |
4 |
Correct |
679 ms |
84976 KB |
Output is correct |
5 |
Correct |
690 ms |
84900 KB |
Output is correct |
6 |
Correct |
692 ms |
85000 KB |
Output is correct |
7 |
Correct |
716 ms |
84924 KB |
Output is correct |
8 |
Correct |
732 ms |
85012 KB |
Output is correct |
9 |
Correct |
709 ms |
84880 KB |
Output is correct |
10 |
Correct |
683 ms |
84836 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
113 ms |
1656 KB |
Output is correct |
2 |
Correct |
180 ms |
9372 KB |
Output is correct |
3 |
Correct |
672 ms |
84808 KB |
Output is correct |
4 |
Correct |
937 ms |
85240 KB |
Output is correct |
5 |
Correct |
787 ms |
92072 KB |
Output is correct |
6 |
Correct |
1295 ms |
135944 KB |
Output is correct |
7 |
Correct |
735 ms |
87552 KB |
Output is correct |
8 |
Correct |
712 ms |
84960 KB |
Output is correct |
9 |
Correct |
698 ms |
85476 KB |
Output is correct |
10 |
Correct |
720 ms |
89624 KB |
Output is correct |
11 |
Correct |
800 ms |
107604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
225 ms |
2056 KB |
Output is correct |
2 |
Correct |
281 ms |
2156 KB |
Output is correct |
3 |
Correct |
358 ms |
2252 KB |
Output is correct |
4 |
Correct |
433 ms |
2164 KB |
Output is correct |
5 |
Correct |
699 ms |
3328 KB |
Output is correct |
6 |
Correct |
1668 ms |
94648 KB |
Output is correct |
7 |
Correct |
1729 ms |
94516 KB |
Output is correct |
8 |
Correct |
1632 ms |
94588 KB |
Output is correct |
9 |
Correct |
2119 ms |
94624 KB |
Output is correct |
10 |
Correct |
1576 ms |
94640 KB |
Output is correct |
11 |
Correct |
1505 ms |
94476 KB |
Output is correct |
12 |
Correct |
1499 ms |
94524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
632 KB |
Output is correct |
2 |
Correct |
43 ms |
504 KB |
Output is correct |
3 |
Correct |
62 ms |
632 KB |
Output is correct |
4 |
Correct |
46 ms |
632 KB |
Output is correct |
5 |
Correct |
37 ms |
632 KB |
Output is correct |
6 |
Correct |
54 ms |
504 KB |
Output is correct |
7 |
Correct |
58 ms |
504 KB |
Output is correct |
8 |
Correct |
52 ms |
604 KB |
Output is correct |
9 |
Correct |
52 ms |
632 KB |
Output is correct |
10 |
Correct |
59 ms |
632 KB |
Output is correct |
11 |
Correct |
55 ms |
632 KB |
Output is correct |
12 |
Correct |
39 ms |
608 KB |
Output is correct |
13 |
Correct |
121 ms |
1636 KB |
Output is correct |
14 |
Correct |
132 ms |
1624 KB |
Output is correct |
15 |
Correct |
77 ms |
1656 KB |
Output is correct |
16 |
Correct |
64 ms |
2168 KB |
Output is correct |
17 |
Correct |
100 ms |
1656 KB |
Output is correct |
18 |
Correct |
94 ms |
1636 KB |
Output is correct |
19 |
Correct |
90 ms |
1664 KB |
Output is correct |
20 |
Correct |
77 ms |
1812 KB |
Output is correct |
21 |
Correct |
62 ms |
1656 KB |
Output is correct |
22 |
Correct |
63 ms |
2304 KB |
Output is correct |
23 |
Correct |
924 ms |
84856 KB |
Output is correct |
24 |
Correct |
721 ms |
85028 KB |
Output is correct |
25 |
Correct |
730 ms |
85000 KB |
Output is correct |
26 |
Correct |
679 ms |
84976 KB |
Output is correct |
27 |
Correct |
690 ms |
84900 KB |
Output is correct |
28 |
Correct |
692 ms |
85000 KB |
Output is correct |
29 |
Correct |
716 ms |
84924 KB |
Output is correct |
30 |
Correct |
732 ms |
85012 KB |
Output is correct |
31 |
Correct |
709 ms |
84880 KB |
Output is correct |
32 |
Correct |
683 ms |
84836 KB |
Output is correct |
33 |
Correct |
113 ms |
1656 KB |
Output is correct |
34 |
Correct |
180 ms |
9372 KB |
Output is correct |
35 |
Correct |
672 ms |
84808 KB |
Output is correct |
36 |
Correct |
937 ms |
85240 KB |
Output is correct |
37 |
Correct |
787 ms |
92072 KB |
Output is correct |
38 |
Correct |
1295 ms |
135944 KB |
Output is correct |
39 |
Correct |
735 ms |
87552 KB |
Output is correct |
40 |
Correct |
712 ms |
84960 KB |
Output is correct |
41 |
Correct |
698 ms |
85476 KB |
Output is correct |
42 |
Correct |
720 ms |
89624 KB |
Output is correct |
43 |
Correct |
800 ms |
107604 KB |
Output is correct |
44 |
Correct |
225 ms |
2056 KB |
Output is correct |
45 |
Correct |
281 ms |
2156 KB |
Output is correct |
46 |
Correct |
358 ms |
2252 KB |
Output is correct |
47 |
Correct |
433 ms |
2164 KB |
Output is correct |
48 |
Correct |
699 ms |
3328 KB |
Output is correct |
49 |
Correct |
1668 ms |
94648 KB |
Output is correct |
50 |
Correct |
1729 ms |
94516 KB |
Output is correct |
51 |
Correct |
1632 ms |
94588 KB |
Output is correct |
52 |
Correct |
2119 ms |
94624 KB |
Output is correct |
53 |
Correct |
1576 ms |
94640 KB |
Output is correct |
54 |
Correct |
1505 ms |
94476 KB |
Output is correct |
55 |
Correct |
1499 ms |
94524 KB |
Output is correct |
56 |
Correct |
313 ms |
2136 KB |
Output is correct |
57 |
Correct |
639 ms |
2168 KB |
Output is correct |
58 |
Correct |
910 ms |
3360 KB |
Output is correct |
59 |
Correct |
2209 ms |
86756 KB |
Output is correct |
60 |
Correct |
3346 ms |
86876 KB |
Output is correct |
61 |
Correct |
1870 ms |
86608 KB |
Output is correct |
62 |
Correct |
1681 ms |
90548 KB |
Output is correct |
63 |
Correct |
2983 ms |
89336 KB |
Output is correct |
64 |
Correct |
2142 ms |
87528 KB |
Output is correct |
65 |
Correct |
1851 ms |
86416 KB |
Output is correct |
66 |
Correct |
2318 ms |
86972 KB |
Output is correct |
67 |
Correct |
2221 ms |
91400 KB |
Output is correct |
68 |
Correct |
1745 ms |
100828 KB |
Output is correct |
69 |
Correct |
2938 ms |
110180 KB |
Output is correct |