#include "seats.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef long long ll;
typedef int32_t ii;
//~ #define int ll
const int N = 1e6 + 5;
struct ST{
int tree[N << 2], cnt[N << 2], f[N << 2], a[N];
void build(int l, int r, int x){
if(l == r) { tree[x] = 0, cnt[x] = 1; return; }
int m = (l + r) >> 1;
build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
cnt[x] = cnt[x << 1] + cnt[x << 1 | 1];
}
ST(){
build(0, N, 1);
}
void push(int x, int lx, int rx){
if(lx == rx) return;
tree[x << 1] += f[x], f[x << 1] += f[x];
tree[x << 1 | 1] += f[x], f[x << 1 | 1] += f[x];
f[x] = 0;
}
void rec(int x){
tree[x] = tree[x << 1], cnt[x] = cnt[x << 1];
if(tree[x << 1] > tree[x << 1 | 1]){
tree[x] = tree[x << 1 | 1], cnt[x] = cnt[x << 1 | 1];
} else if(tree[x << 1] == tree[x << 1 | 1]){
cnt[x] += cnt[x << 1 | 1];
}
}
void add(int l, int r, int v, int lx, int rx, int x){
if(lx > r || rx < l){
return;
}
if(lx >= l && rx <= r){
tree[x] += v, f[x] += v;
return;
}
push(x, lx, rx);
int m = (lx + rx) >> 1;
add(l, r, v, lx, m, x << 1);
add(l, r, v, m + 1, rx, x << 1 | 1);
rec(x);
}
void set(int i, int v){
add(i, N, -a[i] + v, 0, N, 1);
a[i] = v;
}
ar<int, 2> get(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return {N, N};
if(lx >= l && rx <= r) return {tree[x], cnt[x]};
push(x, lx, rx);
int m = (lx + rx) >> 1;
auto L = get(l, r, lx, m, x << 1);
auto R = get(l, r, m + 1, rx, x << 1 | 1);
if(L > R) swap(L, R);
if(L[0] == R[0]) L[1] += R[1];
return L;
}
ar<int, 2> get(int l, int r){
return get(l, r, 0, N, 1);
}
}tree;
int n, m, sz;
vector<int> x, y;
vector<vector<int>> a;
int get(int i, int j, int v){
int mask = 0;
if(a[i][j] <= v) mask |= 1;
if(a[i][j + 1] <= v) mask |= 2;
if(a[i + 1][j] <= v) mask |= 4;
if(a[i + 1][j + 1] <= v) mask |= 8;
return mask;
}
int trans(int old, int nw){
if(old == 0){
return 1;
} else if(__builtin_popcount(old) == 1){
if(nw == 6 || nw == 9) return 0;
else return -1;
} else if(__builtin_popcount(old) == 2){
if(old == 6 || old == 9) return 0;
else return 1;
} else {
return -1;
}
}
void rec(int i, int j){
tree.set(a[i][j], trans(get(i - 1, j - 1, a[i][j] - 1), get(i - 1, j - 1, a[i][j])) +
trans(get(i, j - 1, a[i][j] - 1), get(i, j - 1, a[i][j])) +
trans(get(i - 1, j, a[i][j] - 1), get(i - 1, j, a[i][j])) +
trans(get(i, j, a[i][j] - 1), get(i, j, a[i][j])));
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
n = h, m = w;
sz = n * m;
swap(x, r);
swap(y, c);
a.resize(n + 2, vector<int>(m + 2, N));
for(int i=0;i<sz;i++){
x[i]++, y[i]++;
a[x[i]][y[i]] = i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
rec(i, j);
}
}
auto ans = tree.get(0, sz - 1);
assert(ans[0] == 4);
}
int swap_seats(int i, int j){
swap(x[i], x[j]), swap(y[i], y[j]);
a[x[i]][y[i]] = i, a[x[j]][y[j]] = j;
auto check = [&](int x, int y){
return (1 <= x && x <= n && 1 <= y && y <= m);
};
for(int x_ = x[i] - 1; x_ <= x[i] + 1; x_++){
for(int y_ = y[i] - 1; y_ <= y[i] + 1; y_++){
if(check(x_, y_)){
rec(x_, y_);
}
}
}
for(int x_ = x[j] - 1; x_ <= x[j] + 1; x_++){
for(int y_ = y[j] - 1; y_ <= y[j] + 1; y_++){
if(check(x_, y_)){
rec(x_, y_);
}
}
}
auto ans = tree.get(0, sz - 1);
assert(ans[0] == 4);
return ans[1];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
14804 KB |
Output is correct |
2 |
Correct |
27 ms |
14856 KB |
Output is correct |
3 |
Correct |
31 ms |
14892 KB |
Output is correct |
4 |
Correct |
22 ms |
14932 KB |
Output is correct |
5 |
Correct |
17 ms |
14860 KB |
Output is correct |
6 |
Correct |
26 ms |
14868 KB |
Output is correct |
7 |
Correct |
29 ms |
14864 KB |
Output is correct |
8 |
Correct |
29 ms |
14844 KB |
Output is correct |
9 |
Correct |
30 ms |
14856 KB |
Output is correct |
10 |
Correct |
30 ms |
14840 KB |
Output is correct |
11 |
Correct |
25 ms |
14856 KB |
Output is correct |
12 |
Correct |
17 ms |
14868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
14804 KB |
Output is correct |
2 |
Correct |
27 ms |
14856 KB |
Output is correct |
3 |
Correct |
31 ms |
14892 KB |
Output is correct |
4 |
Correct |
22 ms |
14932 KB |
Output is correct |
5 |
Correct |
17 ms |
14860 KB |
Output is correct |
6 |
Correct |
26 ms |
14868 KB |
Output is correct |
7 |
Correct |
29 ms |
14864 KB |
Output is correct |
8 |
Correct |
29 ms |
14844 KB |
Output is correct |
9 |
Correct |
30 ms |
14856 KB |
Output is correct |
10 |
Correct |
30 ms |
14840 KB |
Output is correct |
11 |
Correct |
25 ms |
14856 KB |
Output is correct |
12 |
Correct |
17 ms |
14868 KB |
Output is correct |
13 |
Correct |
40 ms |
15188 KB |
Output is correct |
14 |
Correct |
45 ms |
15324 KB |
Output is correct |
15 |
Correct |
22 ms |
15316 KB |
Output is correct |
16 |
Correct |
21 ms |
15780 KB |
Output is correct |
17 |
Correct |
32 ms |
15248 KB |
Output is correct |
18 |
Correct |
38 ms |
15204 KB |
Output is correct |
19 |
Correct |
36 ms |
15272 KB |
Output is correct |
20 |
Correct |
29 ms |
15412 KB |
Output is correct |
21 |
Correct |
21 ms |
15316 KB |
Output is correct |
22 |
Correct |
22 ms |
15700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
908 ms |
48520 KB |
Output is correct |
2 |
Correct |
636 ms |
48628 KB |
Output is correct |
3 |
Correct |
658 ms |
48488 KB |
Output is correct |
4 |
Correct |
471 ms |
48508 KB |
Output is correct |
5 |
Correct |
489 ms |
48496 KB |
Output is correct |
6 |
Correct |
472 ms |
48728 KB |
Output is correct |
7 |
Correct |
535 ms |
48508 KB |
Output is correct |
8 |
Correct |
580 ms |
48552 KB |
Output is correct |
9 |
Correct |
605 ms |
48516 KB |
Output is correct |
10 |
Correct |
545 ms |
48552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
15188 KB |
Output is correct |
2 |
Correct |
85 ms |
17880 KB |
Output is correct |
3 |
Correct |
488 ms |
48508 KB |
Output is correct |
4 |
Correct |
927 ms |
48536 KB |
Output is correct |
5 |
Correct |
486 ms |
56292 KB |
Output is correct |
6 |
Correct |
1244 ms |
115336 KB |
Output is correct |
7 |
Correct |
529 ms |
67072 KB |
Output is correct |
8 |
Correct |
631 ms |
64576 KB |
Output is correct |
9 |
Correct |
575 ms |
64912 KB |
Output is correct |
10 |
Correct |
598 ms |
69180 KB |
Output is correct |
11 |
Correct |
532 ms |
87932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
65 ms |
16164 KB |
Output is correct |
2 |
Correct |
92 ms |
16172 KB |
Output is correct |
3 |
Correct |
132 ms |
16124 KB |
Output is correct |
4 |
Correct |
108 ms |
16168 KB |
Output is correct |
5 |
Correct |
116 ms |
16632 KB |
Output is correct |
6 |
Correct |
672 ms |
57848 KB |
Output is correct |
7 |
Correct |
751 ms |
57864 KB |
Output is correct |
8 |
Correct |
638 ms |
58012 KB |
Output is correct |
9 |
Correct |
1012 ms |
57916 KB |
Output is correct |
10 |
Correct |
597 ms |
58040 KB |
Output is correct |
11 |
Correct |
657 ms |
74020 KB |
Output is correct |
12 |
Correct |
603 ms |
73988 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
14804 KB |
Output is correct |
2 |
Correct |
27 ms |
14856 KB |
Output is correct |
3 |
Correct |
31 ms |
14892 KB |
Output is correct |
4 |
Correct |
22 ms |
14932 KB |
Output is correct |
5 |
Correct |
17 ms |
14860 KB |
Output is correct |
6 |
Correct |
26 ms |
14868 KB |
Output is correct |
7 |
Correct |
29 ms |
14864 KB |
Output is correct |
8 |
Correct |
29 ms |
14844 KB |
Output is correct |
9 |
Correct |
30 ms |
14856 KB |
Output is correct |
10 |
Correct |
30 ms |
14840 KB |
Output is correct |
11 |
Correct |
25 ms |
14856 KB |
Output is correct |
12 |
Correct |
17 ms |
14868 KB |
Output is correct |
13 |
Correct |
40 ms |
15188 KB |
Output is correct |
14 |
Correct |
45 ms |
15324 KB |
Output is correct |
15 |
Correct |
22 ms |
15316 KB |
Output is correct |
16 |
Correct |
21 ms |
15780 KB |
Output is correct |
17 |
Correct |
32 ms |
15248 KB |
Output is correct |
18 |
Correct |
38 ms |
15204 KB |
Output is correct |
19 |
Correct |
36 ms |
15272 KB |
Output is correct |
20 |
Correct |
29 ms |
15412 KB |
Output is correct |
21 |
Correct |
21 ms |
15316 KB |
Output is correct |
22 |
Correct |
22 ms |
15700 KB |
Output is correct |
23 |
Correct |
908 ms |
48520 KB |
Output is correct |
24 |
Correct |
636 ms |
48628 KB |
Output is correct |
25 |
Correct |
658 ms |
48488 KB |
Output is correct |
26 |
Correct |
471 ms |
48508 KB |
Output is correct |
27 |
Correct |
489 ms |
48496 KB |
Output is correct |
28 |
Correct |
472 ms |
48728 KB |
Output is correct |
29 |
Correct |
535 ms |
48508 KB |
Output is correct |
30 |
Correct |
580 ms |
48552 KB |
Output is correct |
31 |
Correct |
605 ms |
48516 KB |
Output is correct |
32 |
Correct |
545 ms |
48552 KB |
Output is correct |
33 |
Correct |
39 ms |
15188 KB |
Output is correct |
34 |
Correct |
85 ms |
17880 KB |
Output is correct |
35 |
Correct |
488 ms |
48508 KB |
Output is correct |
36 |
Correct |
927 ms |
48536 KB |
Output is correct |
37 |
Correct |
486 ms |
56292 KB |
Output is correct |
38 |
Correct |
1244 ms |
115336 KB |
Output is correct |
39 |
Correct |
529 ms |
67072 KB |
Output is correct |
40 |
Correct |
631 ms |
64576 KB |
Output is correct |
41 |
Correct |
575 ms |
64912 KB |
Output is correct |
42 |
Correct |
598 ms |
69180 KB |
Output is correct |
43 |
Correct |
532 ms |
87932 KB |
Output is correct |
44 |
Correct |
65 ms |
16164 KB |
Output is correct |
45 |
Correct |
92 ms |
16172 KB |
Output is correct |
46 |
Correct |
132 ms |
16124 KB |
Output is correct |
47 |
Correct |
108 ms |
16168 KB |
Output is correct |
48 |
Correct |
116 ms |
16632 KB |
Output is correct |
49 |
Correct |
672 ms |
57848 KB |
Output is correct |
50 |
Correct |
751 ms |
57864 KB |
Output is correct |
51 |
Correct |
638 ms |
58012 KB |
Output is correct |
52 |
Correct |
1012 ms |
57916 KB |
Output is correct |
53 |
Correct |
597 ms |
58040 KB |
Output is correct |
54 |
Correct |
657 ms |
74020 KB |
Output is correct |
55 |
Correct |
603 ms |
73988 KB |
Output is correct |
56 |
Correct |
169 ms |
16508 KB |
Output is correct |
57 |
Correct |
260 ms |
16572 KB |
Output is correct |
58 |
Correct |
298 ms |
16964 KB |
Output is correct |
59 |
Correct |
1006 ms |
66120 KB |
Output is correct |
60 |
Correct |
1445 ms |
66100 KB |
Output is correct |
61 |
Correct |
900 ms |
66012 KB |
Output is correct |
62 |
Correct |
689 ms |
70112 KB |
Output is correct |
63 |
Correct |
1302 ms |
68812 KB |
Output is correct |
64 |
Correct |
953 ms |
66992 KB |
Output is correct |
65 |
Correct |
967 ms |
66196 KB |
Output is correct |
66 |
Correct |
1012 ms |
66360 KB |
Output is correct |
67 |
Correct |
955 ms |
70752 KB |
Output is correct |
68 |
Correct |
803 ms |
80316 KB |
Output is correct |
69 |
Correct |
1468 ms |
89512 KB |
Output is correct |