#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
int H, W;
vector<int> R, C;
struct seg {
int min, ans;
} tree[4 * 1000 * 1000];
int lazy[4 * 1000 * 1000];
vector<vector<int>> RC;
seg merge(seg a, seg b) {
if (a.min < b.min) {
return a;
} else if(b.min < a.min) {
return b;
} else {
return {a.min, a.ans + b.ans};
}
}
seg build(int cur, int lo, int hi) {
if (lo == hi) {
return tree[cur] = {0, 1};
}
int lmid = (lo + hi) / 2, rmid = lmid + 1;
return tree[cur] = merge(build(cur << 1 | 0, lo, lmid),
build(cur << 1 | 1, rmid, hi));
}
void update(int l, int r, int delta, int cur, int lo, int hi) {
if (lo == l && hi == r) {
lazy[cur] += delta;
tree[cur].min += delta;
} else {
lazy[cur << 1 | 0] += lazy[cur];
tree[cur << 1 | 0].min += lazy[cur];
lazy[cur << 1 | 1] += lazy[cur];
tree[cur << 1 | 1].min += lazy[cur];
lazy[cur] = 0;
int lmid = (lo + hi) / 2, rmid = lmid + 1;
if (l <= lmid) {
update(l, min(r, lmid), delta, cur << 1 | 0, lo, lmid);
}
if (r >= rmid) {
update(max(l, rmid), r, delta, cur << 1 | 1, rmid, hi);
}
tree[cur] = merge(tree[cur << 1 | 0],
tree[cur << 1 | 1]);
}
}
void update(int l, int r, int delta) {
if (l < r)
update(l + 1, r, delta, 1, 1, H * W);
}
void give_initial_chart(int HH, int WW, vector<int> RR, vector<int> CC) {
H = HH, W = WW, R = RR, C = CC;
RC = vector<vector<int>>(H + 2, vector<int>(W + 2, H * W));
for (int i = 0; i < H * W; i++) {
RC[R[i] + 1][C[i] + 1] = i;
}
build(1, 1, H * W);
for (int i = 0; i <= H; i++) {
for (int j = 0; j <= W; j++) {
int adj[4] = {RC[i][j], RC[i][j + 1], RC[i + 1][j], RC[i + 1][j + 1]};
sort(adj, adj + 4);
update(adj[0], adj[1], +1);
update(adj[2], adj[3], +1);
}
}
}
int swap_seats(int a, int b) {
int ax = R[a] + 1, ay = C[a] + 1;
int bx = R[b] + 1, by = C[b] + 1;
for (int i = -1; i < 1; i++) {
for (int j = -1; j < 1; j++) {
int adja[4] = {RC[ax + i][ay + j], RC[ax + i][ay + j + 1], RC[ax + i + 1][ay + j], RC[ax + i + 1][ay + j + 1]};
sort(adja, adja + 4);
update(adja[0], adja[1], -1);
update(adja[2], adja[3], -1);
int adjb[4] = {RC[bx + i][by + j], RC[bx + i][by + j + 1], RC[bx + i + 1][by + j], RC[bx + i + 1][by + j + 1]};
sort(adjb, adjb + 4);
update(adjb[0], adjb[1], -1);
update(adjb[2], adjb[3], -1);
}
}
swap(RC[ax][ay], RC[bx][by]);
swap(R[a], R[b]);
swap(C[a], C[b]);
for (int i = -1; i < 1; i++) {
for (int j = -1; j < 1; j++) {
int adja[4] = {RC[ax + i][ay + j], RC[ax + i][ay + j + 1], RC[ax + i + 1][ay + j], RC[ax + i + 1][ay + j + 1]};
sort(adja, adja + 4);
update(adja[0], adja[1], +1);
update(adja[2], adja[3], +1);
int adjb[4] = {RC[bx + i][by + j], RC[bx + i][by + j + 1], RC[bx + i + 1][by + j], RC[bx + i + 1][by + j + 1]};
sort(adjb, adjb + 4);
update(adjb[0], adjb[1], +1);
update(adjb[2], adjb[3], +1);
}
}
return tree[1].ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
376 KB |
Output is correct |
2 |
Correct |
24 ms |
500 KB |
Output is correct |
3 |
Correct |
39 ms |
656 KB |
Output is correct |
4 |
Correct |
22 ms |
656 KB |
Output is correct |
5 |
Correct |
19 ms |
700 KB |
Output is correct |
6 |
Correct |
31 ms |
720 KB |
Output is correct |
7 |
Correct |
36 ms |
808 KB |
Output is correct |
8 |
Correct |
30 ms |
808 KB |
Output is correct |
9 |
Correct |
31 ms |
808 KB |
Output is correct |
10 |
Correct |
33 ms |
828 KB |
Output is correct |
11 |
Correct |
35 ms |
828 KB |
Output is correct |
12 |
Correct |
19 ms |
828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
376 KB |
Output is correct |
2 |
Correct |
24 ms |
500 KB |
Output is correct |
3 |
Correct |
39 ms |
656 KB |
Output is correct |
4 |
Correct |
22 ms |
656 KB |
Output is correct |
5 |
Correct |
19 ms |
700 KB |
Output is correct |
6 |
Correct |
31 ms |
720 KB |
Output is correct |
7 |
Correct |
36 ms |
808 KB |
Output is correct |
8 |
Correct |
30 ms |
808 KB |
Output is correct |
9 |
Correct |
31 ms |
808 KB |
Output is correct |
10 |
Correct |
33 ms |
828 KB |
Output is correct |
11 |
Correct |
35 ms |
828 KB |
Output is correct |
12 |
Correct |
19 ms |
828 KB |
Output is correct |
13 |
Correct |
86 ms |
1468 KB |
Output is correct |
14 |
Correct |
90 ms |
1468 KB |
Output is correct |
15 |
Correct |
54 ms |
1520 KB |
Output is correct |
16 |
Correct |
44 ms |
1980 KB |
Output is correct |
17 |
Correct |
63 ms |
1980 KB |
Output is correct |
18 |
Correct |
62 ms |
1980 KB |
Output is correct |
19 |
Correct |
57 ms |
1980 KB |
Output is correct |
20 |
Correct |
51 ms |
1980 KB |
Output is correct |
21 |
Correct |
38 ms |
1980 KB |
Output is correct |
22 |
Correct |
41 ms |
1980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2374 ms |
52828 KB |
Output is correct |
2 |
Correct |
1246 ms |
53068 KB |
Output is correct |
3 |
Correct |
1195 ms |
53068 KB |
Output is correct |
4 |
Correct |
999 ms |
53068 KB |
Output is correct |
5 |
Correct |
1055 ms |
53068 KB |
Output is correct |
6 |
Correct |
960 ms |
53068 KB |
Output is correct |
7 |
Correct |
1068 ms |
53068 KB |
Output is correct |
8 |
Correct |
1203 ms |
53068 KB |
Output is correct |
9 |
Correct |
1195 ms |
53068 KB |
Output is correct |
10 |
Correct |
1169 ms |
53068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
77 ms |
53068 KB |
Output is correct |
2 |
Correct |
205 ms |
53068 KB |
Output is correct |
3 |
Correct |
1016 ms |
53068 KB |
Output is correct |
4 |
Correct |
2397 ms |
53068 KB |
Output is correct |
5 |
Correct |
978 ms |
60576 KB |
Output is correct |
6 |
Correct |
2397 ms |
103612 KB |
Output is correct |
7 |
Correct |
1047 ms |
103612 KB |
Output is correct |
8 |
Correct |
1232 ms |
103612 KB |
Output is correct |
9 |
Correct |
1138 ms |
103612 KB |
Output is correct |
10 |
Correct |
1134 ms |
103612 KB |
Output is correct |
11 |
Correct |
1047 ms |
103612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
103612 KB |
Output is correct |
2 |
Correct |
116 ms |
103612 KB |
Output is correct |
3 |
Correct |
210 ms |
103612 KB |
Output is correct |
4 |
Correct |
241 ms |
103612 KB |
Output is correct |
5 |
Correct |
400 ms |
103612 KB |
Output is correct |
6 |
Correct |
1505 ms |
103612 KB |
Output is correct |
7 |
Correct |
1774 ms |
103612 KB |
Output is correct |
8 |
Correct |
1491 ms |
103612 KB |
Output is correct |
9 |
Correct |
2888 ms |
103612 KB |
Output is correct |
10 |
Correct |
1447 ms |
103612 KB |
Output is correct |
11 |
Correct |
1413 ms |
103612 KB |
Output is correct |
12 |
Correct |
1318 ms |
103612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
376 KB |
Output is correct |
2 |
Correct |
24 ms |
500 KB |
Output is correct |
3 |
Correct |
39 ms |
656 KB |
Output is correct |
4 |
Correct |
22 ms |
656 KB |
Output is correct |
5 |
Correct |
19 ms |
700 KB |
Output is correct |
6 |
Correct |
31 ms |
720 KB |
Output is correct |
7 |
Correct |
36 ms |
808 KB |
Output is correct |
8 |
Correct |
30 ms |
808 KB |
Output is correct |
9 |
Correct |
31 ms |
808 KB |
Output is correct |
10 |
Correct |
33 ms |
828 KB |
Output is correct |
11 |
Correct |
35 ms |
828 KB |
Output is correct |
12 |
Correct |
19 ms |
828 KB |
Output is correct |
13 |
Correct |
86 ms |
1468 KB |
Output is correct |
14 |
Correct |
90 ms |
1468 KB |
Output is correct |
15 |
Correct |
54 ms |
1520 KB |
Output is correct |
16 |
Correct |
44 ms |
1980 KB |
Output is correct |
17 |
Correct |
63 ms |
1980 KB |
Output is correct |
18 |
Correct |
62 ms |
1980 KB |
Output is correct |
19 |
Correct |
57 ms |
1980 KB |
Output is correct |
20 |
Correct |
51 ms |
1980 KB |
Output is correct |
21 |
Correct |
38 ms |
1980 KB |
Output is correct |
22 |
Correct |
41 ms |
1980 KB |
Output is correct |
23 |
Correct |
2374 ms |
52828 KB |
Output is correct |
24 |
Correct |
1246 ms |
53068 KB |
Output is correct |
25 |
Correct |
1195 ms |
53068 KB |
Output is correct |
26 |
Correct |
999 ms |
53068 KB |
Output is correct |
27 |
Correct |
1055 ms |
53068 KB |
Output is correct |
28 |
Correct |
960 ms |
53068 KB |
Output is correct |
29 |
Correct |
1068 ms |
53068 KB |
Output is correct |
30 |
Correct |
1203 ms |
53068 KB |
Output is correct |
31 |
Correct |
1195 ms |
53068 KB |
Output is correct |
32 |
Correct |
1169 ms |
53068 KB |
Output is correct |
33 |
Correct |
77 ms |
53068 KB |
Output is correct |
34 |
Correct |
205 ms |
53068 KB |
Output is correct |
35 |
Correct |
1016 ms |
53068 KB |
Output is correct |
36 |
Correct |
2397 ms |
53068 KB |
Output is correct |
37 |
Correct |
978 ms |
60576 KB |
Output is correct |
38 |
Correct |
2397 ms |
103612 KB |
Output is correct |
39 |
Correct |
1047 ms |
103612 KB |
Output is correct |
40 |
Correct |
1232 ms |
103612 KB |
Output is correct |
41 |
Correct |
1138 ms |
103612 KB |
Output is correct |
42 |
Correct |
1134 ms |
103612 KB |
Output is correct |
43 |
Correct |
1047 ms |
103612 KB |
Output is correct |
44 |
Correct |
69 ms |
103612 KB |
Output is correct |
45 |
Correct |
116 ms |
103612 KB |
Output is correct |
46 |
Correct |
210 ms |
103612 KB |
Output is correct |
47 |
Correct |
241 ms |
103612 KB |
Output is correct |
48 |
Correct |
400 ms |
103612 KB |
Output is correct |
49 |
Correct |
1505 ms |
103612 KB |
Output is correct |
50 |
Correct |
1774 ms |
103612 KB |
Output is correct |
51 |
Correct |
1491 ms |
103612 KB |
Output is correct |
52 |
Correct |
2888 ms |
103612 KB |
Output is correct |
53 |
Correct |
1447 ms |
103612 KB |
Output is correct |
54 |
Correct |
1413 ms |
103612 KB |
Output is correct |
55 |
Correct |
1318 ms |
103612 KB |
Output is correct |
56 |
Correct |
140 ms |
103612 KB |
Output is correct |
57 |
Correct |
344 ms |
103612 KB |
Output is correct |
58 |
Correct |
577 ms |
103612 KB |
Output is correct |
59 |
Correct |
1995 ms |
103612 KB |
Output is correct |
60 |
Correct |
3633 ms |
103612 KB |
Output is correct |
61 |
Correct |
1935 ms |
103612 KB |
Output is correct |
62 |
Correct |
1508 ms |
103612 KB |
Output is correct |
63 |
Correct |
3498 ms |
103612 KB |
Output is correct |
64 |
Correct |
2168 ms |
103612 KB |
Output is correct |
65 |
Correct |
1841 ms |
103612 KB |
Output is correct |
66 |
Correct |
2104 ms |
103612 KB |
Output is correct |
67 |
Correct |
2108 ms |
103612 KB |
Output is correct |
68 |
Correct |
1657 ms |
103612 KB |
Output is correct |
69 |
Correct |
3473 ms |
103612 KB |
Output is correct |