#include <bits/stdc++.h>
#include "seats.h"
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int H, W;
vector<vector<int>> M;
int Min[4040404], Cnt[4040404];
int S[1010101], lazy[4040404];
int R[1010101], C[1010101];
void init(int id, int s, int e){
if (s == e){
Min[id] = S[s];
Cnt[id] = 1;
return;
}
int mid = (s+e)/2;
init(id*2, s, mid);
init(id*2+1, mid+1, e);
Min[id] = min(Min[id*2], Min[id*2+1]), Cnt[id] = 0;
if (Min[id] == Min[id*2]) Cnt[id] += Cnt[id*2];
if (Min[id] == Min[id*2+1]) Cnt[id] += Cnt[id*2+1];
}
void update(int id, int s, int e, int ts, int te, int v){
if (e < ts || te < s) return;
if (ts <= s && e <= te){
Min[id] += v;
lazy[id] += v;
return;
}
Min[id*2] += lazy[id];
Min[id*2+1] += lazy[id];
lazy[id*2] += lazy[id];
lazy[id*2+1] += lazy[id];
lazy[id] = 0;
int mid = (s+e)/2;
update(id*2, s, mid, ts, te, v);
update(id*2+1, mid+1, e, ts, te, v);
Min[id] = min(Min[id*2], Min[id*2+1]), Cnt[id] = 0;
if (Min[id] == Min[id*2]) Cnt[id] += Cnt[id*2];
if (Min[id] == Min[id*2+1]) Cnt[id] += Cnt[id*2+1];
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c){
H=h, W=w;
M.reserve(H+2);
for (int i=0; i<=H+1; i++) M[i].reserve(W+2);
for (int i=0; i<=W+1; i++) M[0][i] = M[H+1][i] = H*W+1;
for (int i=0; i<=H+1; i++) M[i][0] = M[i][W+1] = H*W+1;
for (int i=1; i<=H*W; i++){
R[i] = r[i-1]+1, C[i] = c[i-1]+1;
M[R[i]][C[i]] = i;
}
for (int i=0; i<=H; i++) for (int j=0; j<=W; j++){
vector<int> t;
t.push_back(M[i][j]); t.push_back(M[i][j+1]);
t.push_back(M[i+1][j]); t.push_back(M[i+1][j+1]);
sort(t.begin(), t.end());
S[t[0]]++, S[t[1]]--;
S[t[2]]++, S[t[3]]--;
}
for (int i=1; i<=H*W; i++) S[i] += S[i-1];
init(1, 1, H*W);
}
void angle(int x, int y, int v){
vector<int> t;
t.push_back(M[x][y]); t.push_back(M[x][y+1]);
t.push_back(M[x+1][y]); t.push_back(M[x+1][y+1]);
sort(t.begin(), t.end());
update(1, 1, H*W, t[0], t[1]-1, v);
update(1, 1, H*W, t[2], t[3]-1, v);
}
int swap_seats(int a, int b) {
a++, b++;
angle(R[a]-1, C[a]-1, -1);
angle(R[a], C[a]-1, -1);
angle(R[a]-1, C[a], -1);
angle(R[a], C[a], -1);
angle(R[b]-1, C[b]-1, -1);
angle(R[b], C[b]-1, -1);
angle(R[b]-1, C[b], -1);
angle(R[b], C[b], -1);
swap(M[R[a]][C[a]], M[R[b]][C[b]]);
swap(R[a], R[b]);
swap(C[a], C[b]);
angle(R[a]-1, C[a]-1, 1);
angle(R[a], C[a]-1, 1);
angle(R[a]-1, C[a], 1);
angle(R[a], C[a], 1);
angle(R[b]-1, C[b]-1, 1);
angle(R[b], C[b]-1, 1);
angle(R[b]-1, C[b], 1);
angle(R[b], C[b], 1);
return Cnt[1];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
504 KB |
Output is correct |
2 |
Correct |
31 ms |
512 KB |
Output is correct |
3 |
Correct |
42 ms |
504 KB |
Output is correct |
4 |
Correct |
29 ms |
512 KB |
Output is correct |
5 |
Correct |
27 ms |
512 KB |
Output is correct |
6 |
Correct |
37 ms |
512 KB |
Output is correct |
7 |
Correct |
40 ms |
512 KB |
Output is correct |
8 |
Correct |
38 ms |
508 KB |
Output is correct |
9 |
Correct |
38 ms |
512 KB |
Output is correct |
10 |
Correct |
43 ms |
504 KB |
Output is correct |
11 |
Correct |
39 ms |
508 KB |
Output is correct |
12 |
Correct |
28 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
504 KB |
Output is correct |
2 |
Correct |
31 ms |
512 KB |
Output is correct |
3 |
Correct |
42 ms |
504 KB |
Output is correct |
4 |
Correct |
29 ms |
512 KB |
Output is correct |
5 |
Correct |
27 ms |
512 KB |
Output is correct |
6 |
Correct |
37 ms |
512 KB |
Output is correct |
7 |
Correct |
40 ms |
512 KB |
Output is correct |
8 |
Correct |
38 ms |
508 KB |
Output is correct |
9 |
Correct |
38 ms |
512 KB |
Output is correct |
10 |
Correct |
43 ms |
504 KB |
Output is correct |
11 |
Correct |
39 ms |
508 KB |
Output is correct |
12 |
Correct |
28 ms |
512 KB |
Output is correct |
13 |
Correct |
82 ms |
1308 KB |
Output is correct |
14 |
Correct |
84 ms |
1304 KB |
Output is correct |
15 |
Correct |
50 ms |
1400 KB |
Output is correct |
16 |
Correct |
45 ms |
1828 KB |
Output is correct |
17 |
Correct |
80 ms |
1332 KB |
Output is correct |
18 |
Correct |
67 ms |
1280 KB |
Output is correct |
19 |
Correct |
69 ms |
1400 KB |
Output is correct |
20 |
Correct |
57 ms |
1528 KB |
Output is correct |
21 |
Correct |
43 ms |
1408 KB |
Output is correct |
22 |
Correct |
52 ms |
1792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
803 ms |
49800 KB |
Output is correct |
2 |
Correct |
588 ms |
49632 KB |
Output is correct |
3 |
Correct |
564 ms |
49632 KB |
Output is correct |
4 |
Correct |
621 ms |
49508 KB |
Output is correct |
5 |
Correct |
559 ms |
49380 KB |
Output is correct |
6 |
Correct |
515 ms |
49380 KB |
Output is correct |
7 |
Correct |
514 ms |
49376 KB |
Output is correct |
8 |
Correct |
532 ms |
49508 KB |
Output is correct |
9 |
Correct |
525 ms |
49376 KB |
Output is correct |
10 |
Correct |
514 ms |
49376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
75 ms |
1280 KB |
Output is correct |
2 |
Correct |
140 ms |
6556 KB |
Output is correct |
3 |
Correct |
517 ms |
51808 KB |
Output is correct |
4 |
Correct |
797 ms |
52064 KB |
Output is correct |
5 |
Correct |
632 ms |
59744 KB |
Output is correct |
6 |
Correct |
1115 ms |
103016 KB |
Output is correct |
7 |
Correct |
671 ms |
54496 KB |
Output is correct |
8 |
Correct |
523 ms |
51936 KB |
Output is correct |
9 |
Correct |
525 ms |
52140 KB |
Output is correct |
10 |
Correct |
540 ms |
56552 KB |
Output is correct |
11 |
Correct |
609 ms |
75364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
164 ms |
1908 KB |
Output is correct |
2 |
Correct |
204 ms |
2164 KB |
Output is correct |
3 |
Correct |
262 ms |
2012 KB |
Output is correct |
4 |
Correct |
313 ms |
2048 KB |
Output is correct |
5 |
Correct |
462 ms |
2624 KB |
Output is correct |
6 |
Correct |
1201 ms |
57572 KB |
Output is correct |
7 |
Correct |
1240 ms |
57660 KB |
Output is correct |
8 |
Correct |
1364 ms |
57744 KB |
Output is correct |
9 |
Correct |
1534 ms |
57728 KB |
Output is correct |
10 |
Correct |
1120 ms |
57700 KB |
Output is correct |
11 |
Correct |
1158 ms |
57572 KB |
Output is correct |
12 |
Correct |
1088 ms |
57756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
504 KB |
Output is correct |
2 |
Correct |
31 ms |
512 KB |
Output is correct |
3 |
Correct |
42 ms |
504 KB |
Output is correct |
4 |
Correct |
29 ms |
512 KB |
Output is correct |
5 |
Correct |
27 ms |
512 KB |
Output is correct |
6 |
Correct |
37 ms |
512 KB |
Output is correct |
7 |
Correct |
40 ms |
512 KB |
Output is correct |
8 |
Correct |
38 ms |
508 KB |
Output is correct |
9 |
Correct |
38 ms |
512 KB |
Output is correct |
10 |
Correct |
43 ms |
504 KB |
Output is correct |
11 |
Correct |
39 ms |
508 KB |
Output is correct |
12 |
Correct |
28 ms |
512 KB |
Output is correct |
13 |
Correct |
82 ms |
1308 KB |
Output is correct |
14 |
Correct |
84 ms |
1304 KB |
Output is correct |
15 |
Correct |
50 ms |
1400 KB |
Output is correct |
16 |
Correct |
45 ms |
1828 KB |
Output is correct |
17 |
Correct |
80 ms |
1332 KB |
Output is correct |
18 |
Correct |
67 ms |
1280 KB |
Output is correct |
19 |
Correct |
69 ms |
1400 KB |
Output is correct |
20 |
Correct |
57 ms |
1528 KB |
Output is correct |
21 |
Correct |
43 ms |
1408 KB |
Output is correct |
22 |
Correct |
52 ms |
1792 KB |
Output is correct |
23 |
Correct |
803 ms |
49800 KB |
Output is correct |
24 |
Correct |
588 ms |
49632 KB |
Output is correct |
25 |
Correct |
564 ms |
49632 KB |
Output is correct |
26 |
Correct |
621 ms |
49508 KB |
Output is correct |
27 |
Correct |
559 ms |
49380 KB |
Output is correct |
28 |
Correct |
515 ms |
49380 KB |
Output is correct |
29 |
Correct |
514 ms |
49376 KB |
Output is correct |
30 |
Correct |
532 ms |
49508 KB |
Output is correct |
31 |
Correct |
525 ms |
49376 KB |
Output is correct |
32 |
Correct |
514 ms |
49376 KB |
Output is correct |
33 |
Correct |
75 ms |
1280 KB |
Output is correct |
34 |
Correct |
140 ms |
6556 KB |
Output is correct |
35 |
Correct |
517 ms |
51808 KB |
Output is correct |
36 |
Correct |
797 ms |
52064 KB |
Output is correct |
37 |
Correct |
632 ms |
59744 KB |
Output is correct |
38 |
Correct |
1115 ms |
103016 KB |
Output is correct |
39 |
Correct |
671 ms |
54496 KB |
Output is correct |
40 |
Correct |
523 ms |
51936 KB |
Output is correct |
41 |
Correct |
525 ms |
52140 KB |
Output is correct |
42 |
Correct |
540 ms |
56552 KB |
Output is correct |
43 |
Correct |
609 ms |
75364 KB |
Output is correct |
44 |
Correct |
164 ms |
1908 KB |
Output is correct |
45 |
Correct |
204 ms |
2164 KB |
Output is correct |
46 |
Correct |
262 ms |
2012 KB |
Output is correct |
47 |
Correct |
313 ms |
2048 KB |
Output is correct |
48 |
Correct |
462 ms |
2624 KB |
Output is correct |
49 |
Correct |
1201 ms |
57572 KB |
Output is correct |
50 |
Correct |
1240 ms |
57660 KB |
Output is correct |
51 |
Correct |
1364 ms |
57744 KB |
Output is correct |
52 |
Correct |
1534 ms |
57728 KB |
Output is correct |
53 |
Correct |
1120 ms |
57700 KB |
Output is correct |
54 |
Correct |
1158 ms |
57572 KB |
Output is correct |
55 |
Correct |
1088 ms |
57756 KB |
Output is correct |
56 |
Correct |
226 ms |
2092 KB |
Output is correct |
57 |
Correct |
422 ms |
2148 KB |
Output is correct |
58 |
Correct |
636 ms |
2876 KB |
Output is correct |
59 |
Correct |
1636 ms |
49888 KB |
Output is correct |
60 |
Correct |
2554 ms |
49800 KB |
Output is correct |
61 |
Correct |
1379 ms |
50016 KB |
Output is correct |
62 |
Correct |
1176 ms |
53860 KB |
Output is correct |
63 |
Correct |
1914 ms |
52324 KB |
Output is correct |
64 |
Correct |
1495 ms |
50808 KB |
Output is correct |
65 |
Correct |
1280 ms |
49888 KB |
Output is correct |
66 |
Correct |
1568 ms |
50280 KB |
Output is correct |
67 |
Correct |
1523 ms |
54572 KB |
Output is correct |
68 |
Correct |
1235 ms |
64088 KB |
Output is correct |
69 |
Correct |
2067 ms |
73412 KB |
Output is correct |