#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define x first
#define y second
const int mxn = 1e6 + 10, inf = 1e9;
int n, m, x[mxn], y[mxn], val[mxn];
vector<vector<int>> g;
// segtree
int d[mxn * 4], cnt[mxn * 4], lz[mxn * 4];
void pro(int i, int l, int r) {
// if(lz[i] == 0) return;
d[i] += lz[i];
if(l < r) {
lz[i * 2] += lz[i];
lz[i * 2 + 1] += lz[i];
}
lz[i] = 0;
}
void build(int l, int r, int i) {
if(l == r) {
cnt[i] = 1;
return;
}
int mid = (l + r) / 2;
build(l, mid, i * 2);
build(mid + 1, r, i * 2 + 1);
cnt[i] = cnt[i * 2] + cnt[i * 2 + 1];
}
void update(int x, int y, int val, int l = 1, int r = n * m, int i = 1) {
pro(i, l, r);
if(l > y || r < x) return;
if(x <= l && r <= y) {
lz[i] += val;
pro(i, l, r);
return;
}
int mid = (l + r) / 2;
update(x, y, val, mid + 1, r, i * 2 + 1);
update(x, y, val, l, mid, i * 2);
d[i] = d[i * 2]; cnt[i] = cnt[i * 2];
if(d[i * 2 + 1] < d[i]) d[i] = d[i * 2 + 1], cnt[i] = cnt[i * 2 + 1];
else if(d[i * 2 + 1] == d[i]) cnt[i] += cnt[i * 2 + 1];
}
int getAns() {
return cnt[1];
}
int get(int i) {
int ret = 0;
for(int dx = -1; dx <= 0; dx++) {
for(int dy = -1; dy <= 0; dy++) {
int cnt = 0;
for(int xx = 0; xx <= 1; xx++) {
for(int yy = 0; yy <= 1; yy++) {
int fx = x[i] + dx + xx;
int fy = y[i] + dy + yy;
if(g[fx][fy] > i) cnt++;
}
}
if(cnt == 0) ret--;
else if(cnt == 1) ret++;
else if(cnt == 2) ret--;
else ret++;
}
}
return ret;
}
void printSegTree(int l = 1, int r = n * m, int i = 1) {
pro(i, l, r);
cout << l << ' ' << r << ' ' << d[i] << ' ' << cnt[i] << '\n';
if(l == r) return;
int mid = (l + r) / 2;
printSegTree(l, mid, i * 2);
printSegTree(mid + 1, r, i * 2 + 1);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H;
m = W;
build(1, n * m, 1);
g = vector<vector<int>>(n + 10, vector<int>(m + 10, inf));
for(int i = 1; i <= n * m; i++) {
x[i] = R[i - 1] + 1;
y[i] = C[i - 1] + 1;
g[x[i]][y[i]] = i;
}
for(int i = 1; i <= n * m; i++) {
val[i] = get(i);
update(i, n * m, val[i]);
}
// printSegTree();
}
int swap_seats(int a, int b) {
a++; b++;
// return 1;
swap(g[x[a]][y[a]], g[x[b]][y[b]]);
swap(x[a], x[b]); swap(y[a], y[b]);
for(int dx = -1; dx <= 1; dx++) {
for(int dy = -1; dy <= 1; dy++) {
int fx = x[a] + dx;
int fy = y[a] + dy;
int id = g[fx][fy];
if(id == inf) continue;
int tmp = get(id);
update(id, n * m, -val[id] + tmp);
val[id] = tmp;
}
for(int dy = -1; dy <= 1; dy++) {
int fx = x[b] + dx;
int fy = y[b] + dy;
int id = g[fx][fy];
if(id == inf) continue;
int tmp = get(id);
update(id, n * m, -val[id] + tmp);
val[id] = tmp;
}
}
return getAns();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
468 KB |
Output is correct |
2 |
Correct |
11 ms |
468 KB |
Output is correct |
3 |
Correct |
14 ms |
468 KB |
Output is correct |
4 |
Correct |
5 ms |
476 KB |
Output is correct |
5 |
Correct |
5 ms |
468 KB |
Output is correct |
6 |
Correct |
10 ms |
468 KB |
Output is correct |
7 |
Correct |
11 ms |
468 KB |
Output is correct |
8 |
Correct |
13 ms |
468 KB |
Output is correct |
9 |
Correct |
12 ms |
424 KB |
Output is correct |
10 |
Correct |
11 ms |
468 KB |
Output is correct |
11 |
Correct |
10 ms |
468 KB |
Output is correct |
12 |
Correct |
7 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
468 KB |
Output is correct |
2 |
Correct |
11 ms |
468 KB |
Output is correct |
3 |
Correct |
14 ms |
468 KB |
Output is correct |
4 |
Correct |
5 ms |
476 KB |
Output is correct |
5 |
Correct |
5 ms |
468 KB |
Output is correct |
6 |
Correct |
10 ms |
468 KB |
Output is correct |
7 |
Correct |
11 ms |
468 KB |
Output is correct |
8 |
Correct |
13 ms |
468 KB |
Output is correct |
9 |
Correct |
12 ms |
424 KB |
Output is correct |
10 |
Correct |
11 ms |
468 KB |
Output is correct |
11 |
Correct |
10 ms |
468 KB |
Output is correct |
12 |
Correct |
7 ms |
468 KB |
Output is correct |
13 |
Correct |
28 ms |
1048 KB |
Output is correct |
14 |
Correct |
30 ms |
1100 KB |
Output is correct |
15 |
Correct |
12 ms |
1512 KB |
Output is correct |
16 |
Correct |
12 ms |
1892 KB |
Output is correct |
17 |
Correct |
26 ms |
1472 KB |
Output is correct |
18 |
Correct |
27 ms |
1304 KB |
Output is correct |
19 |
Correct |
24 ms |
1340 KB |
Output is correct |
20 |
Correct |
19 ms |
1656 KB |
Output is correct |
21 |
Correct |
12 ms |
1704 KB |
Output is correct |
22 |
Correct |
12 ms |
2100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
572 ms |
56388 KB |
Output is correct |
2 |
Correct |
514 ms |
56392 KB |
Output is correct |
3 |
Correct |
483 ms |
56388 KB |
Output is correct |
4 |
Correct |
494 ms |
56344 KB |
Output is correct |
5 |
Correct |
500 ms |
56360 KB |
Output is correct |
6 |
Correct |
489 ms |
56380 KB |
Output is correct |
7 |
Correct |
484 ms |
56396 KB |
Output is correct |
8 |
Correct |
497 ms |
56368 KB |
Output is correct |
9 |
Correct |
496 ms |
56352 KB |
Output is correct |
10 |
Correct |
491 ms |
56396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
1072 KB |
Output is correct |
2 |
Correct |
77 ms |
6264 KB |
Output is correct |
3 |
Correct |
491 ms |
56296 KB |
Output is correct |
4 |
Correct |
556 ms |
56432 KB |
Output is correct |
5 |
Correct |
473 ms |
95416 KB |
Output is correct |
6 |
Correct |
855 ms |
151832 KB |
Output is correct |
7 |
Correct |
517 ms |
82844 KB |
Output is correct |
8 |
Correct |
503 ms |
70092 KB |
Output is correct |
9 |
Correct |
546 ms |
70272 KB |
Output is correct |
10 |
Correct |
519 ms |
77544 KB |
Output is correct |
11 |
Correct |
502 ms |
108876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
1360 KB |
Output is correct |
2 |
Correct |
32 ms |
1352 KB |
Output is correct |
3 |
Correct |
49 ms |
1288 KB |
Output is correct |
4 |
Correct |
64 ms |
1460 KB |
Output is correct |
5 |
Correct |
91 ms |
2468 KB |
Output is correct |
6 |
Correct |
651 ms |
104420 KB |
Output is correct |
7 |
Correct |
661 ms |
96476 KB |
Output is correct |
8 |
Correct |
642 ms |
96148 KB |
Output is correct |
9 |
Correct |
747 ms |
96488 KB |
Output is correct |
10 |
Correct |
599 ms |
96488 KB |
Output is correct |
11 |
Correct |
618 ms |
96388 KB |
Output is correct |
12 |
Correct |
614 ms |
96424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
468 KB |
Output is correct |
2 |
Correct |
11 ms |
468 KB |
Output is correct |
3 |
Correct |
14 ms |
468 KB |
Output is correct |
4 |
Correct |
5 ms |
476 KB |
Output is correct |
5 |
Correct |
5 ms |
468 KB |
Output is correct |
6 |
Correct |
10 ms |
468 KB |
Output is correct |
7 |
Correct |
11 ms |
468 KB |
Output is correct |
8 |
Correct |
13 ms |
468 KB |
Output is correct |
9 |
Correct |
12 ms |
424 KB |
Output is correct |
10 |
Correct |
11 ms |
468 KB |
Output is correct |
11 |
Correct |
10 ms |
468 KB |
Output is correct |
12 |
Correct |
7 ms |
468 KB |
Output is correct |
13 |
Correct |
28 ms |
1048 KB |
Output is correct |
14 |
Correct |
30 ms |
1100 KB |
Output is correct |
15 |
Correct |
12 ms |
1512 KB |
Output is correct |
16 |
Correct |
12 ms |
1892 KB |
Output is correct |
17 |
Correct |
26 ms |
1472 KB |
Output is correct |
18 |
Correct |
27 ms |
1304 KB |
Output is correct |
19 |
Correct |
24 ms |
1340 KB |
Output is correct |
20 |
Correct |
19 ms |
1656 KB |
Output is correct |
21 |
Correct |
12 ms |
1704 KB |
Output is correct |
22 |
Correct |
12 ms |
2100 KB |
Output is correct |
23 |
Correct |
572 ms |
56388 KB |
Output is correct |
24 |
Correct |
514 ms |
56392 KB |
Output is correct |
25 |
Correct |
483 ms |
56388 KB |
Output is correct |
26 |
Correct |
494 ms |
56344 KB |
Output is correct |
27 |
Correct |
500 ms |
56360 KB |
Output is correct |
28 |
Correct |
489 ms |
56380 KB |
Output is correct |
29 |
Correct |
484 ms |
56396 KB |
Output is correct |
30 |
Correct |
497 ms |
56368 KB |
Output is correct |
31 |
Correct |
496 ms |
56352 KB |
Output is correct |
32 |
Correct |
491 ms |
56396 KB |
Output is correct |
33 |
Correct |
35 ms |
1072 KB |
Output is correct |
34 |
Correct |
77 ms |
6264 KB |
Output is correct |
35 |
Correct |
491 ms |
56296 KB |
Output is correct |
36 |
Correct |
556 ms |
56432 KB |
Output is correct |
37 |
Correct |
473 ms |
95416 KB |
Output is correct |
38 |
Correct |
855 ms |
151832 KB |
Output is correct |
39 |
Correct |
517 ms |
82844 KB |
Output is correct |
40 |
Correct |
503 ms |
70092 KB |
Output is correct |
41 |
Correct |
546 ms |
70272 KB |
Output is correct |
42 |
Correct |
519 ms |
77544 KB |
Output is correct |
43 |
Correct |
502 ms |
108876 KB |
Output is correct |
44 |
Correct |
23 ms |
1360 KB |
Output is correct |
45 |
Correct |
32 ms |
1352 KB |
Output is correct |
46 |
Correct |
49 ms |
1288 KB |
Output is correct |
47 |
Correct |
64 ms |
1460 KB |
Output is correct |
48 |
Correct |
91 ms |
2468 KB |
Output is correct |
49 |
Correct |
651 ms |
104420 KB |
Output is correct |
50 |
Correct |
661 ms |
96476 KB |
Output is correct |
51 |
Correct |
642 ms |
96148 KB |
Output is correct |
52 |
Correct |
747 ms |
96488 KB |
Output is correct |
53 |
Correct |
599 ms |
96488 KB |
Output is correct |
54 |
Correct |
618 ms |
96388 KB |
Output is correct |
55 |
Correct |
614 ms |
96424 KB |
Output is correct |
56 |
Correct |
62 ms |
2184 KB |
Output is correct |
57 |
Correct |
127 ms |
2000 KB |
Output is correct |
58 |
Correct |
239 ms |
2788 KB |
Output is correct |
59 |
Correct |
1022 ms |
66196 KB |
Output is correct |
60 |
Correct |
1240 ms |
67372 KB |
Output is correct |
61 |
Correct |
823 ms |
67316 KB |
Output is correct |
62 |
Correct |
697 ms |
86892 KB |
Output is correct |
63 |
Correct |
1101 ms |
80216 KB |
Output is correct |
64 |
Correct |
944 ms |
71088 KB |
Output is correct |
65 |
Correct |
844 ms |
64876 KB |
Output is correct |
66 |
Correct |
1022 ms |
67844 KB |
Output is correct |
67 |
Correct |
995 ms |
75080 KB |
Output is correct |
68 |
Correct |
768 ms |
92452 KB |
Output is correct |
69 |
Correct |
1295 ms |
106724 KB |
Output is correct |