#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, m, t[N*4][4], id[4] = {N, 0, N, 0}, A = 0;
vector<vector<int>> grid;
vector<array<int, 2>> pos;
vector<bool> is;
void build(int l, int r, int k){
if(l == r){
t[k][0] = pos[l - 1][0];
t[k][1] = pos[l - 1][0];
t[k][2] = pos[l - 1][1];
t[k][3] = pos[l - 1][1];
return;
}
int mid = l+r>>1;
build(l, mid, k<<1);
build(mid+1, r, k<<1|1);
t[k][0] = min(t[k<<1][0], t[k<<1|1][0]);
t[k][1] = max(t[k<<1][1], t[k<<1|1][1]);
t[k][2] = min(t[k<<1][2], t[k<<1|1][2]);
t[k][3] = max(t[k<<1][3], t[k<<1|1][3]);
}
void update(int l, int r, int p, int k){
if(l == r){
t[k][0] = pos[p - 1][0];
t[k][1] = pos[p - 1][0];
t[k][2] = pos[p - 1][1];
t[k][3] = pos[p - 1][1];
return;
}
int mid = l+r>>1;
if(mid >= p)
update(l, mid, p, k<<1);
else
update(mid + 1, r, p, k<<1|1);
t[k][0] = min(t[k<<1][0], t[k<<1|1][0]);
t[k][1] = max(t[k<<1][1], t[k<<1|1][1]);
t[k][2] = min(t[k<<1][2], t[k<<1|1][2]);
t[k][3] = max(t[k<<1][3], t[k<<1|1][3]);
}
int get(int l, int r, int ql, int qr, int k, int s){
if(ql > r || qr < l) return id[s];
if(ql <= l && r <= qr) return t[k][s];
int mid = l+r>>1;
int al = get(l, mid, ql, qr, k<<1, s);
int ar = get(mid + 1, r, ql, qr, k<<1|1, s);
return (s % 2 ? max(al, ar) : min(al, ar));
}
int calc(){
int ans = 0;
int u = n, d = 0, l = m, r = 0;
for(int i = 0; i < n*m; ++i){
u = min(u, pos[i][0]);
d = max(d, pos[i][0]);
l = min(l, pos[i][1]);
r = max(r, pos[i][1]);
if((r - l + 1) * (d - u + 1) == i + 1){
ans++;
is[i] = 1;
}
}
return ans;
}
void calc2(int a, int b){
int u = get(1, n*m, 1, a, 1, 0);
int d = get(1, n*m, 1, a, 1, 1);
int l = get(1, n*m, 1, a, 1, 2);
int r = get(1, n*m, 1, a, 1, 3);
for(int i = a - 1; i <= b - 1; ++i){
u = min(u, pos[i][0]);
d = max(d, pos[i][0]);
l = min(l, pos[i][1]);
r = max(r, pos[i][1]);
if((r - l + 1) * (d - u + 1) == i + 1){
if(!is[i]) A++;
is[i] = 1;
}else{
if(is[i]) A--;
is[i] = 0;
}
}
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
n = H, m = W;
grid.resize(n, vector<int> (m, 0));
is.resize(n*m);
pos.resize(n*m);
for(int i = 0; i < n*m; ++i) grid[R[i]][C[i]] = i, pos[i] = {R[i], C[i]};
build(1, n*m, 1);
A = calc();
}
int swap_seats(int a, int b){
if(a > b) swap(a, b);
if(b-a <= 10000){
swap(pos[a], pos[b]);
update(1, n*m, a + 1, 1);
update(1, n*m, b + 1, 1);
calc2(a + 1, b + 1);
return A;
}
swap(pos[a], pos[b]);
grid[pos[a][0]][pos[a][1]] = a;
grid[pos[b][0]][pos[b][1]] = b;
return calc();
}
Compilation message
seats.cpp: In function 'void build(int, int, int)':
seats.cpp:18:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
18 | int mid = l+r>>1;
| ~^~
seats.cpp: In function 'void update(int, int, int, int)':
seats.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int mid = l+r>>1;
| ~^~
seats.cpp: In function 'int get(int, int, int, int, int, int)':
seats.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int mid = l+r>>1;
| ~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
4 ms |
340 KB |
Output is correct |
4 |
Correct |
4 ms |
340 KB |
Output is correct |
5 |
Correct |
4 ms |
340 KB |
Output is correct |
6 |
Correct |
6 ms |
340 KB |
Output is correct |
7 |
Correct |
5 ms |
340 KB |
Output is correct |
8 |
Correct |
4 ms |
340 KB |
Output is correct |
9 |
Correct |
4 ms |
340 KB |
Output is correct |
10 |
Correct |
4 ms |
404 KB |
Output is correct |
11 |
Correct |
5 ms |
340 KB |
Output is correct |
12 |
Correct |
5 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
4 ms |
340 KB |
Output is correct |
4 |
Correct |
4 ms |
340 KB |
Output is correct |
5 |
Correct |
4 ms |
340 KB |
Output is correct |
6 |
Correct |
6 ms |
340 KB |
Output is correct |
7 |
Correct |
5 ms |
340 KB |
Output is correct |
8 |
Correct |
4 ms |
340 KB |
Output is correct |
9 |
Correct |
4 ms |
340 KB |
Output is correct |
10 |
Correct |
4 ms |
404 KB |
Output is correct |
11 |
Correct |
5 ms |
340 KB |
Output is correct |
12 |
Correct |
5 ms |
340 KB |
Output is correct |
13 |
Correct |
69 ms |
1124 KB |
Output is correct |
14 |
Correct |
70 ms |
1116 KB |
Output is correct |
15 |
Correct |
65 ms |
1152 KB |
Output is correct |
16 |
Correct |
70 ms |
1648 KB |
Output is correct |
17 |
Correct |
67 ms |
1132 KB |
Output is correct |
18 |
Correct |
65 ms |
1124 KB |
Output is correct |
19 |
Correct |
69 ms |
1108 KB |
Output is correct |
20 |
Correct |
65 ms |
1364 KB |
Output is correct |
21 |
Correct |
70 ms |
1152 KB |
Output is correct |
22 |
Correct |
70 ms |
1636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4074 ms |
60860 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
100 ms |
1128 KB |
Output is correct |
2 |
Correct |
114 ms |
6908 KB |
Output is correct |
3 |
Correct |
328 ms |
60732 KB |
Output is correct |
4 |
Correct |
339 ms |
60748 KB |
Output is correct |
5 |
Correct |
366 ms |
60668 KB |
Output is correct |
6 |
Correct |
478 ms |
127636 KB |
Output is correct |
7 |
Correct |
357 ms |
76688 KB |
Output is correct |
8 |
Correct |
345 ms |
76740 KB |
Output is correct |
9 |
Correct |
345 ms |
77132 KB |
Output is correct |
10 |
Correct |
343 ms |
79800 KB |
Output is correct |
11 |
Correct |
381 ms |
100128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
1340 KB |
Output is correct |
2 |
Correct |
23 ms |
1332 KB |
Output is correct |
3 |
Correct |
36 ms |
1360 KB |
Output is correct |
4 |
Correct |
99 ms |
1312 KB |
Output is correct |
5 |
Correct |
635 ms |
2156 KB |
Output is correct |
6 |
Execution timed out |
4073 ms |
61048 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
4 ms |
340 KB |
Output is correct |
4 |
Correct |
4 ms |
340 KB |
Output is correct |
5 |
Correct |
4 ms |
340 KB |
Output is correct |
6 |
Correct |
6 ms |
340 KB |
Output is correct |
7 |
Correct |
5 ms |
340 KB |
Output is correct |
8 |
Correct |
4 ms |
340 KB |
Output is correct |
9 |
Correct |
4 ms |
340 KB |
Output is correct |
10 |
Correct |
4 ms |
404 KB |
Output is correct |
11 |
Correct |
5 ms |
340 KB |
Output is correct |
12 |
Correct |
5 ms |
340 KB |
Output is correct |
13 |
Correct |
69 ms |
1124 KB |
Output is correct |
14 |
Correct |
70 ms |
1116 KB |
Output is correct |
15 |
Correct |
65 ms |
1152 KB |
Output is correct |
16 |
Correct |
70 ms |
1648 KB |
Output is correct |
17 |
Correct |
67 ms |
1132 KB |
Output is correct |
18 |
Correct |
65 ms |
1124 KB |
Output is correct |
19 |
Correct |
69 ms |
1108 KB |
Output is correct |
20 |
Correct |
65 ms |
1364 KB |
Output is correct |
21 |
Correct |
70 ms |
1152 KB |
Output is correct |
22 |
Correct |
70 ms |
1636 KB |
Output is correct |
23 |
Execution timed out |
4074 ms |
60860 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |