#include "seats.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
const int N = 1<<20;
namespace seg {
struct {
int mn, cnt, val;
} t[N*4];
int sz;
void merge(int i) {
t[i].mn = min(t[2*i+1].mn, t[2*i+2].mn);
t[i].cnt = (t[2*i+1].mn == t[i].mn? t[2*i+1].cnt: 0)
+ (t[2*i+2].mn == t[i].mn? t[2*i+2].cnt: 0);
t[i].mn += t[i].val;
}
void add(int l, int r, int x, int i, int b, int e) {
if (l <= b && e <= r) {
t[i].mn += x;
t[i].val += x;
return;
}
if (r <= b || e <= l)
return;
add(l, r, x, 2*i+1, b, (b+e)/2);
add(l, r, x, 2*i+2, (b+e)/2, e);
merge(i);
}
void add(int l, int r, int x) { if (l < r) add(l, r, x, 0, 0, sz); }
void init(int i, int b, int e) {
t[i].mn = t[i].val = 0;
t[i].cnt = e-b;
if (e-b > 1) {
init(2*i+1, b, (b+e)/2);
init(2*i+2, (b+e)/2, e);
}
}
void init(int n) { sz = n; init(0, 0, sz); }
}
vector<vector<int>> a;
pii pos[N];
int n, m;
bool in(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; }
void add_sq(int i, int j, int mul)
{
vector<int> vec;
Loop (x,i,i+2) Loop (y,j,j+2)
vec.push_back(in(x, y)? a[x][y]: n*m);
sort(vec.begin(), vec.end());
seg::add(vec[0], vec[1], mul);
seg::add(vec[2], vec[3], mul);
}
void add_adj(int i, int j, int mul)
{
Loop (x,i-1,i+1) Loop (y,j-1,j+1)
add_sq(x, y, mul);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H;
m = W;
a.assign(n, vector<int>(m));
Loop (i,0,n*m) {
pos[i] = {R[i], C[i]};
a[R[i]][C[i]] = i;
}
seg::init(n*m);
Loop (i,-1,n+1) Loop (j,-1,m+1)
add_sq(i, j, 1);
}
int swap_seats(int a, int b) {
auto [x1, y1] = pos[a];
auto [x2, y2] = pos[b];
add_adj(x1, y1, -1);
::a[x1][y1] = b;
add_adj(x1, y1, 1);
add_adj(x2, y2, -1);
::a[x2][y2] = a;
add_adj(x2, y2, 1);
swap(pos[a], pos[b]);
return seg::t[0].cnt;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
340 KB |
Output is correct |
2 |
Correct |
23 ms |
444 KB |
Output is correct |
3 |
Correct |
32 ms |
424 KB |
Output is correct |
4 |
Correct |
21 ms |
432 KB |
Output is correct |
5 |
Correct |
19 ms |
456 KB |
Output is correct |
6 |
Correct |
31 ms |
440 KB |
Output is correct |
7 |
Correct |
30 ms |
428 KB |
Output is correct |
8 |
Correct |
28 ms |
468 KB |
Output is correct |
9 |
Correct |
27 ms |
424 KB |
Output is correct |
10 |
Correct |
33 ms |
464 KB |
Output is correct |
11 |
Correct |
29 ms |
444 KB |
Output is correct |
12 |
Correct |
20 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
340 KB |
Output is correct |
2 |
Correct |
23 ms |
444 KB |
Output is correct |
3 |
Correct |
32 ms |
424 KB |
Output is correct |
4 |
Correct |
21 ms |
432 KB |
Output is correct |
5 |
Correct |
19 ms |
456 KB |
Output is correct |
6 |
Correct |
31 ms |
440 KB |
Output is correct |
7 |
Correct |
30 ms |
428 KB |
Output is correct |
8 |
Correct |
28 ms |
468 KB |
Output is correct |
9 |
Correct |
27 ms |
424 KB |
Output is correct |
10 |
Correct |
33 ms |
464 KB |
Output is correct |
11 |
Correct |
29 ms |
444 KB |
Output is correct |
12 |
Correct |
20 ms |
468 KB |
Output is correct |
13 |
Correct |
65 ms |
1176 KB |
Output is correct |
14 |
Correct |
72 ms |
1180 KB |
Output is correct |
15 |
Correct |
44 ms |
1208 KB |
Output is correct |
16 |
Correct |
38 ms |
1692 KB |
Output is correct |
17 |
Correct |
66 ms |
1200 KB |
Output is correct |
18 |
Correct |
52 ms |
1188 KB |
Output is correct |
19 |
Correct |
51 ms |
1196 KB |
Output is correct |
20 |
Correct |
45 ms |
1344 KB |
Output is correct |
21 |
Correct |
37 ms |
1228 KB |
Output is correct |
22 |
Correct |
46 ms |
1704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1633 ms |
52412 KB |
Output is correct |
2 |
Correct |
1041 ms |
68364 KB |
Output is correct |
3 |
Correct |
952 ms |
68364 KB |
Output is correct |
4 |
Correct |
877 ms |
68364 KB |
Output is correct |
5 |
Correct |
913 ms |
68360 KB |
Output is correct |
6 |
Correct |
786 ms |
68364 KB |
Output is correct |
7 |
Correct |
921 ms |
68368 KB |
Output is correct |
8 |
Correct |
886 ms |
68360 KB |
Output is correct |
9 |
Correct |
902 ms |
68360 KB |
Output is correct |
10 |
Correct |
861 ms |
68364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
1012 KB |
Output is correct |
2 |
Correct |
146 ms |
5904 KB |
Output is correct |
3 |
Correct |
883 ms |
52408 KB |
Output is correct |
4 |
Correct |
1645 ms |
68356 KB |
Output is correct |
5 |
Correct |
927 ms |
68376 KB |
Output is correct |
6 |
Correct |
1782 ms |
119120 KB |
Output is correct |
7 |
Correct |
908 ms |
68324 KB |
Output is correct |
8 |
Correct |
925 ms |
68364 KB |
Output is correct |
9 |
Correct |
811 ms |
68796 KB |
Output is correct |
10 |
Correct |
886 ms |
71448 KB |
Output is correct |
11 |
Correct |
949 ms |
91808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
107 ms |
1280 KB |
Output is correct |
2 |
Correct |
136 ms |
1356 KB |
Output is correct |
3 |
Correct |
212 ms |
1344 KB |
Output is correct |
4 |
Correct |
260 ms |
1296 KB |
Output is correct |
5 |
Correct |
340 ms |
1904 KB |
Output is correct |
6 |
Correct |
1418 ms |
52728 KB |
Output is correct |
7 |
Correct |
1559 ms |
52736 KB |
Output is correct |
8 |
Correct |
1297 ms |
52728 KB |
Output is correct |
9 |
Correct |
2261 ms |
52732 KB |
Output is correct |
10 |
Correct |
1318 ms |
52628 KB |
Output is correct |
11 |
Correct |
1291 ms |
52724 KB |
Output is correct |
12 |
Correct |
1285 ms |
52732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
340 KB |
Output is correct |
2 |
Correct |
23 ms |
444 KB |
Output is correct |
3 |
Correct |
32 ms |
424 KB |
Output is correct |
4 |
Correct |
21 ms |
432 KB |
Output is correct |
5 |
Correct |
19 ms |
456 KB |
Output is correct |
6 |
Correct |
31 ms |
440 KB |
Output is correct |
7 |
Correct |
30 ms |
428 KB |
Output is correct |
8 |
Correct |
28 ms |
468 KB |
Output is correct |
9 |
Correct |
27 ms |
424 KB |
Output is correct |
10 |
Correct |
33 ms |
464 KB |
Output is correct |
11 |
Correct |
29 ms |
444 KB |
Output is correct |
12 |
Correct |
20 ms |
468 KB |
Output is correct |
13 |
Correct |
65 ms |
1176 KB |
Output is correct |
14 |
Correct |
72 ms |
1180 KB |
Output is correct |
15 |
Correct |
44 ms |
1208 KB |
Output is correct |
16 |
Correct |
38 ms |
1692 KB |
Output is correct |
17 |
Correct |
66 ms |
1200 KB |
Output is correct |
18 |
Correct |
52 ms |
1188 KB |
Output is correct |
19 |
Correct |
51 ms |
1196 KB |
Output is correct |
20 |
Correct |
45 ms |
1344 KB |
Output is correct |
21 |
Correct |
37 ms |
1228 KB |
Output is correct |
22 |
Correct |
46 ms |
1704 KB |
Output is correct |
23 |
Correct |
1633 ms |
52412 KB |
Output is correct |
24 |
Correct |
1041 ms |
68364 KB |
Output is correct |
25 |
Correct |
952 ms |
68364 KB |
Output is correct |
26 |
Correct |
877 ms |
68364 KB |
Output is correct |
27 |
Correct |
913 ms |
68360 KB |
Output is correct |
28 |
Correct |
786 ms |
68364 KB |
Output is correct |
29 |
Correct |
921 ms |
68368 KB |
Output is correct |
30 |
Correct |
886 ms |
68360 KB |
Output is correct |
31 |
Correct |
902 ms |
68360 KB |
Output is correct |
32 |
Correct |
861 ms |
68364 KB |
Output is correct |
33 |
Correct |
69 ms |
1012 KB |
Output is correct |
34 |
Correct |
146 ms |
5904 KB |
Output is correct |
35 |
Correct |
883 ms |
52408 KB |
Output is correct |
36 |
Correct |
1645 ms |
68356 KB |
Output is correct |
37 |
Correct |
927 ms |
68376 KB |
Output is correct |
38 |
Correct |
1782 ms |
119120 KB |
Output is correct |
39 |
Correct |
908 ms |
68324 KB |
Output is correct |
40 |
Correct |
925 ms |
68364 KB |
Output is correct |
41 |
Correct |
811 ms |
68796 KB |
Output is correct |
42 |
Correct |
886 ms |
71448 KB |
Output is correct |
43 |
Correct |
949 ms |
91808 KB |
Output is correct |
44 |
Correct |
107 ms |
1280 KB |
Output is correct |
45 |
Correct |
136 ms |
1356 KB |
Output is correct |
46 |
Correct |
212 ms |
1344 KB |
Output is correct |
47 |
Correct |
260 ms |
1296 KB |
Output is correct |
48 |
Correct |
340 ms |
1904 KB |
Output is correct |
49 |
Correct |
1418 ms |
52728 KB |
Output is correct |
50 |
Correct |
1559 ms |
52736 KB |
Output is correct |
51 |
Correct |
1297 ms |
52728 KB |
Output is correct |
52 |
Correct |
2261 ms |
52732 KB |
Output is correct |
53 |
Correct |
1318 ms |
52628 KB |
Output is correct |
54 |
Correct |
1291 ms |
52724 KB |
Output is correct |
55 |
Correct |
1285 ms |
52732 KB |
Output is correct |
56 |
Correct |
175 ms |
1960 KB |
Output is correct |
57 |
Correct |
315 ms |
2120 KB |
Output is correct |
58 |
Correct |
501 ms |
2764 KB |
Output is correct |
59 |
Correct |
1531 ms |
69196 KB |
Output is correct |
60 |
Correct |
2614 ms |
69320 KB |
Output is correct |
61 |
Correct |
1480 ms |
69440 KB |
Output is correct |
62 |
Correct |
1307 ms |
69276 KB |
Output is correct |
63 |
Correct |
2494 ms |
69292 KB |
Output is correct |
64 |
Correct |
1724 ms |
69316 KB |
Output is correct |
65 |
Correct |
1573 ms |
69320 KB |
Output is correct |
66 |
Correct |
1635 ms |
69692 KB |
Output is correct |
67 |
Correct |
1718 ms |
72416 KB |
Output is correct |
68 |
Correct |
1508 ms |
83632 KB |
Output is correct |
69 |
Correct |
2503 ms |
92764 KB |
Output is correct |