#include<bits/stdc++.h>
#define breturn return
#define f first
#define s second
using namespace std;
int h, w, lol, xd, q, arr[1100101], n, bn, sus;
int dx[] = {-1, -1, 0, 0};
int dy[] = {0, -1, -1, 0};
pair<int, int> tour[2201000];
int laz[2200100];
vector<vector<int> > mat;
vector<int> r, c, cum, ab, bb;
pair<pair<int, int>, pair<int, int> > get_interval(int x, int y) {
int val[] = {mat[x][y], mat[x + 1][y], mat[x][y + 1], mat[x + 1][y + 1]};
sort(val, val + 4);
breturn {{val[0], val[1]}, {val[2], val[3]}};
}
void acom(int x) {
if(tour[x * 2].f == tour[x * 2 + 1].f) tour[x] = {tour[x * 2].f, tour[x * 2].s + tour[x * 2 + 1].s};
else if(tour[x * 2].f < tour[x * 2 + 1].f) tour[x] = tour[x * 2];
else tour[x] = tour[x * 2 + 1];
}
void upd(int ax, int bx, int val, int x = 1, int l = 0, int r = bn - 1) {
if(ax > bx) breturn;
if(l >= ax and r <= bx) laz[x] += val;
tour[x].f += laz[x];
if(x < bn) laz[x * 2] += laz[x], laz[x * 2 + 1] += laz[x];
laz[x] = 0;
if((l >= ax and r <= bx) or l > bx or r < ax) breturn;
int mid = (l + r)/2;
upd(ax, bx, val, x * 2, l, mid);
upd(ax, bx, val, x * 2 + 1, mid + 1, r);
acom(x);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h = H;
w = W;
for(int i = 0; i < h * w; i++) c.push_back(C[i] + 1), r.push_back(R[i] + 1);
n = h * w;
for(int i = 0; i < w + 2; i++) cum.push_back(h * w);
for(int i = 0; i < h + 2; i++) mat.push_back(cum);
for(int i = 0; i < h * w; i++) mat[r[i]][c[i]] = i;
for(int i = 0; i < h + 1; i++) for(int j = 0; j < w + 1; j++) {
auto p = get_interval(i, j);
arr[p.f.f]++;
arr[p.f.s]--;
arr[p.s.f]++;
arr[p.s.s]--;
}
for(bn = 1; bn < n; bn *= 2);
for(int i = 0; i < bn; i++) tour[i + bn] = {1e9, 0};
for(int i = 0; i < n; i++) {
sus += arr[i];
tour[i + bn] = {sus, 1};
}
for(int i = bn - 1; i; i--) acom(i);
}
int swap_seats(int a, int b) {
for(int j = 0; j < 4; j++) {
auto p = get_interval(r[a] + dx[j], c[a] + dy[j]);
upd(p.f.f, p.f.s - 1, -1);
upd(p.s.f, p.s.s - 1, -1);
p = get_interval(r[b] + dx[j], c[b] + dy[j]);
upd(p.f.f, p.f.s - 1, -1);
upd(p.s.f, p.s.s - 1, -1);
}
swap(mat[r[a]][c[a]], mat[r[b]][c[b]]);
swap(r[a], r[b]);
swap(c[a], c[b]);
for(int j = 0; j < 4; j++) {
auto p = get_interval(r[a] + dx[j], c[a] + dy[j]);
upd(p.f.f, p.f.s - 1, 1);
upd(p.s.f, p.s.s - 1, 1);
p = get_interval(r[b] + dx[j], c[b] + dy[j]);
upd(p.f.f, p.f.s - 1, 1);
upd(p.s.f, p.s.s - 1, 1);
}
if(tour[1].f == 4) breturn tour[1].s;
breturn 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
452 KB |
Output is correct |
2 |
Correct |
21 ms |
376 KB |
Output is correct |
3 |
Correct |
31 ms |
440 KB |
Output is correct |
4 |
Correct |
18 ms |
460 KB |
Output is correct |
5 |
Correct |
16 ms |
456 KB |
Output is correct |
6 |
Correct |
26 ms |
472 KB |
Output is correct |
7 |
Correct |
27 ms |
452 KB |
Output is correct |
8 |
Correct |
26 ms |
432 KB |
Output is correct |
9 |
Correct |
26 ms |
440 KB |
Output is correct |
10 |
Correct |
28 ms |
452 KB |
Output is correct |
11 |
Correct |
26 ms |
444 KB |
Output is correct |
12 |
Correct |
15 ms |
464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
452 KB |
Output is correct |
2 |
Correct |
21 ms |
376 KB |
Output is correct |
3 |
Correct |
31 ms |
440 KB |
Output is correct |
4 |
Correct |
18 ms |
460 KB |
Output is correct |
5 |
Correct |
16 ms |
456 KB |
Output is correct |
6 |
Correct |
26 ms |
472 KB |
Output is correct |
7 |
Correct |
27 ms |
452 KB |
Output is correct |
8 |
Correct |
26 ms |
432 KB |
Output is correct |
9 |
Correct |
26 ms |
440 KB |
Output is correct |
10 |
Correct |
28 ms |
452 KB |
Output is correct |
11 |
Correct |
26 ms |
444 KB |
Output is correct |
12 |
Correct |
15 ms |
464 KB |
Output is correct |
13 |
Correct |
68 ms |
1240 KB |
Output is correct |
14 |
Correct |
71 ms |
1236 KB |
Output is correct |
15 |
Correct |
38 ms |
1332 KB |
Output is correct |
16 |
Correct |
30 ms |
1724 KB |
Output is correct |
17 |
Correct |
49 ms |
1276 KB |
Output is correct |
18 |
Correct |
50 ms |
1228 KB |
Output is correct |
19 |
Correct |
54 ms |
1252 KB |
Output is correct |
20 |
Correct |
40 ms |
1604 KB |
Output is correct |
21 |
Correct |
30 ms |
1396 KB |
Output is correct |
22 |
Correct |
31 ms |
1716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
431 ms |
54372 KB |
Output is correct |
2 |
Correct |
364 ms |
64284 KB |
Output is correct |
3 |
Correct |
367 ms |
64164 KB |
Output is correct |
4 |
Correct |
363 ms |
64164 KB |
Output is correct |
5 |
Correct |
357 ms |
64180 KB |
Output is correct |
6 |
Correct |
360 ms |
64188 KB |
Output is correct |
7 |
Correct |
371 ms |
64156 KB |
Output is correct |
8 |
Correct |
362 ms |
64304 KB |
Output is correct |
9 |
Correct |
365 ms |
64428 KB |
Output is correct |
10 |
Correct |
357 ms |
64432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
1244 KB |
Output is correct |
2 |
Correct |
93 ms |
6620 KB |
Output is correct |
3 |
Correct |
354 ms |
54840 KB |
Output is correct |
4 |
Correct |
429 ms |
64328 KB |
Output is correct |
5 |
Correct |
359 ms |
75980 KB |
Output is correct |
6 |
Correct |
547 ms |
115044 KB |
Output is correct |
7 |
Correct |
358 ms |
68760 KB |
Output is correct |
8 |
Correct |
381 ms |
64320 KB |
Output is correct |
9 |
Correct |
359 ms |
64532 KB |
Output is correct |
10 |
Correct |
369 ms |
68776 KB |
Output is correct |
11 |
Correct |
371 ms |
87560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
1940 KB |
Output is correct |
2 |
Correct |
99 ms |
1984 KB |
Output is correct |
3 |
Correct |
150 ms |
1960 KB |
Output is correct |
4 |
Correct |
219 ms |
2008 KB |
Output is correct |
5 |
Correct |
343 ms |
2868 KB |
Output is correct |
6 |
Correct |
777 ms |
65516 KB |
Output is correct |
7 |
Correct |
795 ms |
77700 KB |
Output is correct |
8 |
Correct |
764 ms |
77580 KB |
Output is correct |
9 |
Correct |
912 ms |
77512 KB |
Output is correct |
10 |
Correct |
705 ms |
77512 KB |
Output is correct |
11 |
Correct |
714 ms |
77488 KB |
Output is correct |
12 |
Correct |
698 ms |
77600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
452 KB |
Output is correct |
2 |
Correct |
21 ms |
376 KB |
Output is correct |
3 |
Correct |
31 ms |
440 KB |
Output is correct |
4 |
Correct |
18 ms |
460 KB |
Output is correct |
5 |
Correct |
16 ms |
456 KB |
Output is correct |
6 |
Correct |
26 ms |
472 KB |
Output is correct |
7 |
Correct |
27 ms |
452 KB |
Output is correct |
8 |
Correct |
26 ms |
432 KB |
Output is correct |
9 |
Correct |
26 ms |
440 KB |
Output is correct |
10 |
Correct |
28 ms |
452 KB |
Output is correct |
11 |
Correct |
26 ms |
444 KB |
Output is correct |
12 |
Correct |
15 ms |
464 KB |
Output is correct |
13 |
Correct |
68 ms |
1240 KB |
Output is correct |
14 |
Correct |
71 ms |
1236 KB |
Output is correct |
15 |
Correct |
38 ms |
1332 KB |
Output is correct |
16 |
Correct |
30 ms |
1724 KB |
Output is correct |
17 |
Correct |
49 ms |
1276 KB |
Output is correct |
18 |
Correct |
50 ms |
1228 KB |
Output is correct |
19 |
Correct |
54 ms |
1252 KB |
Output is correct |
20 |
Correct |
40 ms |
1604 KB |
Output is correct |
21 |
Correct |
30 ms |
1396 KB |
Output is correct |
22 |
Correct |
31 ms |
1716 KB |
Output is correct |
23 |
Correct |
431 ms |
54372 KB |
Output is correct |
24 |
Correct |
364 ms |
64284 KB |
Output is correct |
25 |
Correct |
367 ms |
64164 KB |
Output is correct |
26 |
Correct |
363 ms |
64164 KB |
Output is correct |
27 |
Correct |
357 ms |
64180 KB |
Output is correct |
28 |
Correct |
360 ms |
64188 KB |
Output is correct |
29 |
Correct |
371 ms |
64156 KB |
Output is correct |
30 |
Correct |
362 ms |
64304 KB |
Output is correct |
31 |
Correct |
365 ms |
64428 KB |
Output is correct |
32 |
Correct |
357 ms |
64432 KB |
Output is correct |
33 |
Correct |
60 ms |
1244 KB |
Output is correct |
34 |
Correct |
93 ms |
6620 KB |
Output is correct |
35 |
Correct |
354 ms |
54840 KB |
Output is correct |
36 |
Correct |
429 ms |
64328 KB |
Output is correct |
37 |
Correct |
359 ms |
75980 KB |
Output is correct |
38 |
Correct |
547 ms |
115044 KB |
Output is correct |
39 |
Correct |
358 ms |
68760 KB |
Output is correct |
40 |
Correct |
381 ms |
64320 KB |
Output is correct |
41 |
Correct |
359 ms |
64532 KB |
Output is correct |
42 |
Correct |
369 ms |
68776 KB |
Output is correct |
43 |
Correct |
371 ms |
87560 KB |
Output is correct |
44 |
Correct |
62 ms |
1940 KB |
Output is correct |
45 |
Correct |
99 ms |
1984 KB |
Output is correct |
46 |
Correct |
150 ms |
1960 KB |
Output is correct |
47 |
Correct |
219 ms |
2008 KB |
Output is correct |
48 |
Correct |
343 ms |
2868 KB |
Output is correct |
49 |
Correct |
777 ms |
65516 KB |
Output is correct |
50 |
Correct |
795 ms |
77700 KB |
Output is correct |
51 |
Correct |
764 ms |
77580 KB |
Output is correct |
52 |
Correct |
912 ms |
77512 KB |
Output is correct |
53 |
Correct |
705 ms |
77512 KB |
Output is correct |
54 |
Correct |
714 ms |
77488 KB |
Output is correct |
55 |
Correct |
698 ms |
77600 KB |
Output is correct |
56 |
Correct |
127 ms |
1988 KB |
Output is correct |
57 |
Correct |
312 ms |
1948 KB |
Output is correct |
58 |
Correct |
497 ms |
2704 KB |
Output is correct |
59 |
Correct |
1101 ms |
65908 KB |
Output is correct |
60 |
Correct |
1482 ms |
66096 KB |
Output is correct |
61 |
Correct |
964 ms |
65888 KB |
Output is correct |
62 |
Correct |
837 ms |
71716 KB |
Output is correct |
63 |
Correct |
1266 ms |
70028 KB |
Output is correct |
64 |
Correct |
1083 ms |
67080 KB |
Output is correct |
65 |
Correct |
976 ms |
66020 KB |
Output is correct |
66 |
Correct |
1130 ms |
66256 KB |
Output is correct |
67 |
Correct |
1052 ms |
70544 KB |
Output is correct |
68 |
Correct |
883 ms |
80264 KB |
Output is correct |
69 |
Correct |
1279 ms |
89448 KB |
Output is correct |