#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 55;
typedef pair<long long, int> T;
int n, m, k;
vector<vector<int> > p;
int x[N], y[N];
T tree[1 << 23];
long long push[1 << 23];
void Push(int V, int L, int R, int M)
{
tree[2 * V + 1].first += push[V];
push[2 * V + 1] += push[V];
tree[2 * V + 2].first += push[V];
push[2 * V + 2] += push[V];
push[V] = 0;
}
void add(int l, int r, long long val, int L = 0, int R = (n - 2) * (m - 2), int V = 0)
{
if (r <= L || R <= l)
return;
if (l <= L && R <= r)
{
tree[V].first += val;
push[V] += val;
return;
}
int M = (L + R) / 2;
Push(V, L, R, M);
add(l, r, val, L, M, 2 * V + 1);
add(l, r, val, M, R, 2 * V + 2);
tree[V].first = min(tree[2 * V + 1].first, tree[2 * V + 2].first);
tree[V].second = 0;
if (tree[2 * V + 1].first == tree[V].first) tree[V].second += tree[2 * V + 1].second;
if (tree[2 * V + 2].first == tree[V].first) tree[V].second += tree[2 * V + 2].second;
}
void change_tile(int i, int j, int t)
{
int x[4] = {p[i][j], p[i + 1][j], p[i + 1][j + 1], p[i][j + 1]};
sort(x, x + 4);
add(x[0], x[1], t);
add(x[2], x[3], t * n * m);
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c)
{
T kek = {0, 1};
fill(tree, tree + (1 << 23), kek);
k = h * w;
n = h + 2;
m = w + 2;
for (int i = 0; i < n; i++)
{
vector<int> e(m, k);
p.push_back(e);
}
int t = h * w;
for (int i = 0; i < t; i++)
{
p[r[i] + 1][c[i] + 1] = i;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
x[p[i][j]] = i;
y[p[i][j]] = j;
}
}
for (int i = 0; i + 1 < n; i++)
{
for (int j = 0; j + 1 < m; j++)
{
change_tile(i, j, 1);
}
}
}
void arc(int i, int j, int t)
{
change_tile(i - 1, j - 1, t);
change_tile(i - 1, j, t);
change_tile(i, j - 1, t);
change_tile(i, j, t);
}
int swap_seats(int a, int b)
{
int i1 = x[a], j1 = y[a];
int i2 = x[b], j2 = y[b];
arc(i1, j1, -1);
arc(i2, j2, -1);
swap(p[i1][j1], p[i2][j2]);
swap(x[a], x[b]);
swap(y[a], y[b]);
arc(i1, j1, 1);
arc(i2, j2, 1);
if (tree[0].first == 4) return tree[0].second;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
131832 KB |
Output is correct |
2 |
Correct |
81 ms |
131832 KB |
Output is correct |
3 |
Correct |
91 ms |
131832 KB |
Output is correct |
4 |
Correct |
78 ms |
131832 KB |
Output is correct |
5 |
Correct |
79 ms |
131832 KB |
Output is correct |
6 |
Correct |
88 ms |
131832 KB |
Output is correct |
7 |
Correct |
89 ms |
131832 KB |
Output is correct |
8 |
Correct |
86 ms |
131832 KB |
Output is correct |
9 |
Correct |
89 ms |
131832 KB |
Output is correct |
10 |
Correct |
95 ms |
131792 KB |
Output is correct |
11 |
Correct |
90 ms |
131832 KB |
Output is correct |
12 |
Correct |
77 ms |
131832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
131832 KB |
Output is correct |
2 |
Correct |
81 ms |
131832 KB |
Output is correct |
3 |
Correct |
91 ms |
131832 KB |
Output is correct |
4 |
Correct |
78 ms |
131832 KB |
Output is correct |
5 |
Correct |
79 ms |
131832 KB |
Output is correct |
6 |
Correct |
88 ms |
131832 KB |
Output is correct |
7 |
Correct |
89 ms |
131832 KB |
Output is correct |
8 |
Correct |
86 ms |
131832 KB |
Output is correct |
9 |
Correct |
89 ms |
131832 KB |
Output is correct |
10 |
Correct |
95 ms |
131792 KB |
Output is correct |
11 |
Correct |
90 ms |
131832 KB |
Output is correct |
12 |
Correct |
77 ms |
131832 KB |
Output is correct |
13 |
Correct |
131 ms |
132320 KB |
Output is correct |
14 |
Correct |
142 ms |
132216 KB |
Output is correct |
15 |
Correct |
113 ms |
132344 KB |
Output is correct |
16 |
Correct |
100 ms |
132788 KB |
Output is correct |
17 |
Correct |
124 ms |
132344 KB |
Output is correct |
18 |
Correct |
120 ms |
132216 KB |
Output is correct |
19 |
Correct |
118 ms |
132508 KB |
Output is correct |
20 |
Correct |
117 ms |
132600 KB |
Output is correct |
21 |
Correct |
103 ms |
132344 KB |
Output is correct |
22 |
Correct |
104 ms |
132792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2315 ms |
175864 KB |
Output is correct |
2 |
Correct |
1284 ms |
175552 KB |
Output is correct |
3 |
Correct |
1267 ms |
175608 KB |
Output is correct |
4 |
Correct |
1101 ms |
175736 KB |
Output is correct |
5 |
Correct |
1111 ms |
175604 KB |
Output is correct |
6 |
Correct |
1081 ms |
175608 KB |
Output is correct |
7 |
Correct |
1185 ms |
175632 KB |
Output is correct |
8 |
Correct |
1264 ms |
175608 KB |
Output is correct |
9 |
Correct |
1239 ms |
175736 KB |
Output is correct |
10 |
Correct |
1199 ms |
175608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
132344 KB |
Output is correct |
2 |
Correct |
232 ms |
136184 KB |
Output is correct |
3 |
Correct |
1139 ms |
175540 KB |
Output is correct |
4 |
Correct |
2317 ms |
175748 KB |
Output is correct |
5 |
Correct |
1093 ms |
187312 KB |
Output is correct |
6 |
Correct |
2324 ms |
226420 KB |
Output is correct |
7 |
Correct |
1146 ms |
179552 KB |
Output is correct |
8 |
Correct |
1339 ms |
175740 KB |
Output is correct |
9 |
Correct |
1277 ms |
176052 KB |
Output is correct |
10 |
Correct |
1203 ms |
180336 KB |
Output is correct |
11 |
Correct |
1177 ms |
199052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
127 ms |
132688 KB |
Output is correct |
2 |
Correct |
169 ms |
132840 KB |
Output is correct |
3 |
Correct |
222 ms |
132724 KB |
Output is correct |
4 |
Correct |
295 ms |
132724 KB |
Output is correct |
5 |
Correct |
439 ms |
133332 KB |
Output is correct |
6 |
Correct |
1678 ms |
187700 KB |
Output is correct |
7 |
Correct |
1942 ms |
188860 KB |
Output is correct |
8 |
Correct |
1575 ms |
189068 KB |
Output is correct |
9 |
Correct |
2971 ms |
188952 KB |
Output is correct |
10 |
Correct |
1497 ms |
188976 KB |
Output is correct |
11 |
Correct |
1500 ms |
188976 KB |
Output is correct |
12 |
Correct |
1417 ms |
188976 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
131832 KB |
Output is correct |
2 |
Correct |
81 ms |
131832 KB |
Output is correct |
3 |
Correct |
91 ms |
131832 KB |
Output is correct |
4 |
Correct |
78 ms |
131832 KB |
Output is correct |
5 |
Correct |
79 ms |
131832 KB |
Output is correct |
6 |
Correct |
88 ms |
131832 KB |
Output is correct |
7 |
Correct |
89 ms |
131832 KB |
Output is correct |
8 |
Correct |
86 ms |
131832 KB |
Output is correct |
9 |
Correct |
89 ms |
131832 KB |
Output is correct |
10 |
Correct |
95 ms |
131792 KB |
Output is correct |
11 |
Correct |
90 ms |
131832 KB |
Output is correct |
12 |
Correct |
77 ms |
131832 KB |
Output is correct |
13 |
Correct |
131 ms |
132320 KB |
Output is correct |
14 |
Correct |
142 ms |
132216 KB |
Output is correct |
15 |
Correct |
113 ms |
132344 KB |
Output is correct |
16 |
Correct |
100 ms |
132788 KB |
Output is correct |
17 |
Correct |
124 ms |
132344 KB |
Output is correct |
18 |
Correct |
120 ms |
132216 KB |
Output is correct |
19 |
Correct |
118 ms |
132508 KB |
Output is correct |
20 |
Correct |
117 ms |
132600 KB |
Output is correct |
21 |
Correct |
103 ms |
132344 KB |
Output is correct |
22 |
Correct |
104 ms |
132792 KB |
Output is correct |
23 |
Correct |
2315 ms |
175864 KB |
Output is correct |
24 |
Correct |
1284 ms |
175552 KB |
Output is correct |
25 |
Correct |
1267 ms |
175608 KB |
Output is correct |
26 |
Correct |
1101 ms |
175736 KB |
Output is correct |
27 |
Correct |
1111 ms |
175604 KB |
Output is correct |
28 |
Correct |
1081 ms |
175608 KB |
Output is correct |
29 |
Correct |
1185 ms |
175632 KB |
Output is correct |
30 |
Correct |
1264 ms |
175608 KB |
Output is correct |
31 |
Correct |
1239 ms |
175736 KB |
Output is correct |
32 |
Correct |
1199 ms |
175608 KB |
Output is correct |
33 |
Correct |
135 ms |
132344 KB |
Output is correct |
34 |
Correct |
232 ms |
136184 KB |
Output is correct |
35 |
Correct |
1139 ms |
175540 KB |
Output is correct |
36 |
Correct |
2317 ms |
175748 KB |
Output is correct |
37 |
Correct |
1093 ms |
187312 KB |
Output is correct |
38 |
Correct |
2324 ms |
226420 KB |
Output is correct |
39 |
Correct |
1146 ms |
179552 KB |
Output is correct |
40 |
Correct |
1339 ms |
175740 KB |
Output is correct |
41 |
Correct |
1277 ms |
176052 KB |
Output is correct |
42 |
Correct |
1203 ms |
180336 KB |
Output is correct |
43 |
Correct |
1177 ms |
199052 KB |
Output is correct |
44 |
Correct |
127 ms |
132688 KB |
Output is correct |
45 |
Correct |
169 ms |
132840 KB |
Output is correct |
46 |
Correct |
222 ms |
132724 KB |
Output is correct |
47 |
Correct |
295 ms |
132724 KB |
Output is correct |
48 |
Correct |
439 ms |
133332 KB |
Output is correct |
49 |
Correct |
1678 ms |
187700 KB |
Output is correct |
50 |
Correct |
1942 ms |
188860 KB |
Output is correct |
51 |
Correct |
1575 ms |
189068 KB |
Output is correct |
52 |
Correct |
2971 ms |
188952 KB |
Output is correct |
53 |
Correct |
1497 ms |
188976 KB |
Output is correct |
54 |
Correct |
1500 ms |
188976 KB |
Output is correct |
55 |
Correct |
1417 ms |
188976 KB |
Output is correct |
56 |
Correct |
194 ms |
133340 KB |
Output is correct |
57 |
Correct |
370 ms |
133364 KB |
Output is correct |
58 |
Correct |
604 ms |
134072 KB |
Output is correct |
59 |
Correct |
2013 ms |
177016 KB |
Output is correct |
60 |
Correct |
3546 ms |
177260 KB |
Output is correct |
61 |
Correct |
1885 ms |
177400 KB |
Output is correct |
62 |
Correct |
1605 ms |
183032 KB |
Output is correct |
63 |
Correct |
3355 ms |
181088 KB |
Output is correct |
64 |
Correct |
2166 ms |
178288 KB |
Output is correct |
65 |
Correct |
1997 ms |
177144 KB |
Output is correct |
66 |
Correct |
2224 ms |
177460 KB |
Output is correct |
67 |
Correct |
2116 ms |
181928 KB |
Output is correct |
68 |
Correct |
1745 ms |
191884 KB |
Output is correct |
69 |
Correct |
3145 ms |
201356 KB |
Output is correct |