#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
const int MAXN = 1000005;
const int MAXT = 2100000;
int n, m;
vector<vector<int>> G;
vector<vector<char>> is_valid;
vector<int> R, C;
pi val[MAXN];
void ADD(pi &a, pi b){
a.first += b.first;
a.second += b.second;
}
struct seg{
pi tree[MAXT];
pi lazy[MAXT];
int cnt_min[MAXT];
void lazydown(int p){
ADD(tree[2*p], lazy[p]);
ADD(tree[2*p+1], lazy[p]);
ADD(lazy[2*p], lazy[p]);
ADD(lazy[2*p+1], lazy[p]);
lazy[p] = pi(0, 0);
}
void eat(int p){
tree[p] = min(tree[2*p], tree[2*p+1]);
cnt_min[p] = 0;
if(tree[p] == tree[2*p]) cnt_min[p] += cnt_min[2*p];
if(tree[p] == tree[2*p+1]) cnt_min[p] += cnt_min[2*p+1];
}
void init(int s, int e, int p){
if(s == e){
cnt_min[p] = 1;
return;
}
int m = (s+e)/2;
init(s, m, 2*p);
init(m+1, e, 2*p+1);
eat(p);
}
void add(int s, int e, int ps, int pe, int p, pi v){
if(e < ps || pe < s) return;
if(s <= ps && pe <= e){
ADD(tree[p], v);
ADD(lazy[p], v);
return;
}
int pm = (ps+pe)/2;
lazydown(p);
add(s, e, ps, pm, 2*p, v);
add(s, e, pm+1, pe, 2*p+1, v);
eat(p);
}
int query(){
return tree[1] == pi(4, 0) ? cnt_min[1] : 0;
}
}seg;
pi mp[MAXN];
vector<int> updp;
void flush(){
sort(updp.begin(), updp.end());
updp.resize(unique(updp.begin(), updp.end()) - updp.begin());
auto v = pi(0, 0);
for(int i=0; i+1<updp.size(); i++){
ADD(v, mp[updp[i]]);
seg.add(updp[i], updp[i + 1] - 1, 0, n * m - 1, 1, v);
}
for(auto &i : updp) mp[i] = pi(0, 0);
updp.clear();
}
void update(int x, int y, int f){
if(is_valid[x][y] == 0 && f == -1) return;
if(is_valid[x][y] == 1 && f == 1) return;
is_valid[x][y] ^= 1;
vector<pi> times;
times.emplace_back(G[x][y], 0);
times.emplace_back(G[x + 1][y], 1);
times.emplace_back(G[x + 1][y + 1], 2);
times.emplace_back(G[x][y + 1], 3);
sort(times.begin(), times.end());
for(int i=0; i<3; i++){
int starting_time = times[i].first;
int ending_time = times[i + 1].first;
starting_time = max(starting_time, 0);
ending_time = min(ending_time, n * m);
if(starting_time >= ending_time) continue;
pi updates;
if(i == 0){
updates = pi(f, 0);
}
if(i == 1){
if((times[0].second ^ times[1].second) == 2){
updates = pi(2 * f, 0);
}
else continue;
}
if(i == 2){
updates = pi(0, f);
}
ADD(mp[starting_time], updates);
ADD(mp[ending_time], pi(-updates.first, -updates.second));
updp.push_back(starting_time);
updp.push_back(ending_time);
}
}
void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C) {
G.resize(H + 2);
for(auto &i : G) i.resize(W + 2);
for(auto &i : G) for(auto &j : i) j = 1e7;
is_valid.resize(H + 1);
for(auto &i : is_valid) i.resize(W + 1);
n = H, m = W, R = _R, C = _C;
for(int i=0; i<n*m; i++){
G[R[i] + 1][C[i] + 1] = i;
}
for(int i=0; i<n+1; i++){
for(int j=0; j<m+1; j++){
update(i, j, 1);
}
}
seg.init(0, n*m-1, 1);
}
int swap_seats(int a, int b) {
swap(R[a], R[b]);
swap(C[a], C[b]);
for(int i=0; i<2; i++){
for(int j=0; j<2; j++){
update(R[a] + i, C[a] + j, -1);
update(R[b] + i, C[b] + j, -1);
}
}
swap(G[R[a] + 1][C[a] + 1], G[R[b] + 1][C[b] + 1]);
for(int i=0; i<2; i++){
for(int j=0; j<2; j++){
update(R[a] + i, C[a] + j, 1);
update(R[b] + i, C[b] + j, 1);
}
}
flush();
return seg.query();
}
Compilation message
seats.cpp: In function 'void flush()':
seats.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i+1<updp.size(); i++){
~~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
33372 KB |
Output is correct |
2 |
Correct |
63 ms |
33324 KB |
Output is correct |
3 |
Correct |
81 ms |
33380 KB |
Output is correct |
4 |
Correct |
62 ms |
33416 KB |
Output is correct |
5 |
Correct |
54 ms |
33400 KB |
Output is correct |
6 |
Correct |
67 ms |
33528 KB |
Output is correct |
7 |
Correct |
70 ms |
33400 KB |
Output is correct |
8 |
Correct |
70 ms |
33400 KB |
Output is correct |
9 |
Correct |
69 ms |
33388 KB |
Output is correct |
10 |
Correct |
70 ms |
33400 KB |
Output is correct |
11 |
Correct |
67 ms |
33380 KB |
Output is correct |
12 |
Correct |
53 ms |
33356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
33372 KB |
Output is correct |
2 |
Correct |
63 ms |
33324 KB |
Output is correct |
3 |
Correct |
81 ms |
33380 KB |
Output is correct |
4 |
Correct |
62 ms |
33416 KB |
Output is correct |
5 |
Correct |
54 ms |
33400 KB |
Output is correct |
6 |
Correct |
67 ms |
33528 KB |
Output is correct |
7 |
Correct |
70 ms |
33400 KB |
Output is correct |
8 |
Correct |
70 ms |
33400 KB |
Output is correct |
9 |
Correct |
69 ms |
33388 KB |
Output is correct |
10 |
Correct |
70 ms |
33400 KB |
Output is correct |
11 |
Correct |
67 ms |
33380 KB |
Output is correct |
12 |
Correct |
53 ms |
33356 KB |
Output is correct |
13 |
Correct |
113 ms |
34284 KB |
Output is correct |
14 |
Correct |
121 ms |
34268 KB |
Output is correct |
15 |
Correct |
80 ms |
34368 KB |
Output is correct |
16 |
Correct |
74 ms |
35308 KB |
Output is correct |
17 |
Correct |
96 ms |
34328 KB |
Output is correct |
18 |
Correct |
101 ms |
34296 KB |
Output is correct |
19 |
Correct |
95 ms |
34268 KB |
Output is correct |
20 |
Correct |
85 ms |
34884 KB |
Output is correct |
21 |
Correct |
73 ms |
34356 KB |
Output is correct |
22 |
Correct |
78 ms |
35312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1894 ms |
113860 KB |
Output is correct |
2 |
Correct |
1429 ms |
104568 KB |
Output is correct |
3 |
Correct |
1444 ms |
103180 KB |
Output is correct |
4 |
Correct |
1338 ms |
103032 KB |
Output is correct |
5 |
Correct |
1346 ms |
104532 KB |
Output is correct |
6 |
Correct |
1324 ms |
104456 KB |
Output is correct |
7 |
Correct |
1408 ms |
104316 KB |
Output is correct |
8 |
Correct |
1443 ms |
104444 KB |
Output is correct |
9 |
Correct |
1409 ms |
104336 KB |
Output is correct |
10 |
Correct |
1377 ms |
104376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
110 ms |
34288 KB |
Output is correct |
2 |
Correct |
223 ms |
40424 KB |
Output is correct |
3 |
Correct |
1711 ms |
107536 KB |
Output is correct |
4 |
Correct |
1855 ms |
116412 KB |
Output is correct |
5 |
Correct |
1637 ms |
116192 KB |
Output is correct |
6 |
Correct |
2196 ms |
211856 KB |
Output is correct |
7 |
Correct |
1378 ms |
110212 KB |
Output is correct |
8 |
Correct |
1391 ms |
107428 KB |
Output is correct |
9 |
Correct |
1480 ms |
107900 KB |
Output is correct |
10 |
Correct |
1457 ms |
116416 KB |
Output is correct |
11 |
Correct |
1546 ms |
157096 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
197 ms |
35040 KB |
Output is correct |
2 |
Correct |
249 ms |
35112 KB |
Output is correct |
3 |
Correct |
272 ms |
35032 KB |
Output is correct |
4 |
Correct |
312 ms |
35060 KB |
Output is correct |
5 |
Correct |
412 ms |
36068 KB |
Output is correct |
6 |
Correct |
2154 ms |
115240 KB |
Output is correct |
7 |
Correct |
2037 ms |
114968 KB |
Output is correct |
8 |
Correct |
2141 ms |
114880 KB |
Output is correct |
9 |
Correct |
2547 ms |
114936 KB |
Output is correct |
10 |
Correct |
2090 ms |
114964 KB |
Output is correct |
11 |
Correct |
2116 ms |
115144 KB |
Output is correct |
12 |
Correct |
2051 ms |
118336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
33372 KB |
Output is correct |
2 |
Correct |
63 ms |
33324 KB |
Output is correct |
3 |
Correct |
81 ms |
33380 KB |
Output is correct |
4 |
Correct |
62 ms |
33416 KB |
Output is correct |
5 |
Correct |
54 ms |
33400 KB |
Output is correct |
6 |
Correct |
67 ms |
33528 KB |
Output is correct |
7 |
Correct |
70 ms |
33400 KB |
Output is correct |
8 |
Correct |
70 ms |
33400 KB |
Output is correct |
9 |
Correct |
69 ms |
33388 KB |
Output is correct |
10 |
Correct |
70 ms |
33400 KB |
Output is correct |
11 |
Correct |
67 ms |
33380 KB |
Output is correct |
12 |
Correct |
53 ms |
33356 KB |
Output is correct |
13 |
Correct |
113 ms |
34284 KB |
Output is correct |
14 |
Correct |
121 ms |
34268 KB |
Output is correct |
15 |
Correct |
80 ms |
34368 KB |
Output is correct |
16 |
Correct |
74 ms |
35308 KB |
Output is correct |
17 |
Correct |
96 ms |
34328 KB |
Output is correct |
18 |
Correct |
101 ms |
34296 KB |
Output is correct |
19 |
Correct |
95 ms |
34268 KB |
Output is correct |
20 |
Correct |
85 ms |
34884 KB |
Output is correct |
21 |
Correct |
73 ms |
34356 KB |
Output is correct |
22 |
Correct |
78 ms |
35312 KB |
Output is correct |
23 |
Correct |
1894 ms |
113860 KB |
Output is correct |
24 |
Correct |
1429 ms |
104568 KB |
Output is correct |
25 |
Correct |
1444 ms |
103180 KB |
Output is correct |
26 |
Correct |
1338 ms |
103032 KB |
Output is correct |
27 |
Correct |
1346 ms |
104532 KB |
Output is correct |
28 |
Correct |
1324 ms |
104456 KB |
Output is correct |
29 |
Correct |
1408 ms |
104316 KB |
Output is correct |
30 |
Correct |
1443 ms |
104444 KB |
Output is correct |
31 |
Correct |
1409 ms |
104336 KB |
Output is correct |
32 |
Correct |
1377 ms |
104376 KB |
Output is correct |
33 |
Correct |
110 ms |
34288 KB |
Output is correct |
34 |
Correct |
223 ms |
40424 KB |
Output is correct |
35 |
Correct |
1711 ms |
107536 KB |
Output is correct |
36 |
Correct |
1855 ms |
116412 KB |
Output is correct |
37 |
Correct |
1637 ms |
116192 KB |
Output is correct |
38 |
Correct |
2196 ms |
211856 KB |
Output is correct |
39 |
Correct |
1378 ms |
110212 KB |
Output is correct |
40 |
Correct |
1391 ms |
107428 KB |
Output is correct |
41 |
Correct |
1480 ms |
107900 KB |
Output is correct |
42 |
Correct |
1457 ms |
116416 KB |
Output is correct |
43 |
Correct |
1546 ms |
157096 KB |
Output is correct |
44 |
Correct |
197 ms |
35040 KB |
Output is correct |
45 |
Correct |
249 ms |
35112 KB |
Output is correct |
46 |
Correct |
272 ms |
35032 KB |
Output is correct |
47 |
Correct |
312 ms |
35060 KB |
Output is correct |
48 |
Correct |
412 ms |
36068 KB |
Output is correct |
49 |
Correct |
2154 ms |
115240 KB |
Output is correct |
50 |
Correct |
2037 ms |
114968 KB |
Output is correct |
51 |
Correct |
2141 ms |
114880 KB |
Output is correct |
52 |
Correct |
2547 ms |
114936 KB |
Output is correct |
53 |
Correct |
2090 ms |
114964 KB |
Output is correct |
54 |
Correct |
2116 ms |
115144 KB |
Output is correct |
55 |
Correct |
2051 ms |
118336 KB |
Output is correct |
56 |
Correct |
285 ms |
34884 KB |
Output is correct |
57 |
Correct |
481 ms |
35036 KB |
Output is correct |
58 |
Correct |
682 ms |
35636 KB |
Output is correct |
59 |
Correct |
2438 ms |
101860 KB |
Output is correct |
60 |
Correct |
3406 ms |
110912 KB |
Output is correct |
61 |
Correct |
2211 ms |
101956 KB |
Output is correct |
62 |
Correct |
2089 ms |
106324 KB |
Output is correct |
63 |
Correct |
3124 ms |
114004 KB |
Output is correct |
64 |
Correct |
2438 ms |
103196 KB |
Output is correct |
65 |
Correct |
2154 ms |
102068 KB |
Output is correct |
66 |
Correct |
2621 ms |
102680 KB |
Output is correct |
67 |
Correct |
2528 ms |
111512 KB |
Output is correct |
68 |
Correct |
2142 ms |
133484 KB |
Output is correct |
69 |
Correct |
3221 ms |
160660 KB |
Output is correct |