#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
const int MAX_N = 1e6 + 5;
int H, W;
vector <int> R, C;
int tree[4 * MAX_N];
struct State {
int minR, maxR, minC, maxC;
}state[MAX_N];
void update(int idx, int l, int r, int q, int v) {
if(l == r) {
tree[idx] = v;
return;
}
int mid = (l + r) / 2;
if(q <= mid) {
update(idx * 2, l, mid, q, v);
}
else {
update(idx * 2 + 1, mid + 1, r, q, v);
}
tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}
void give_initial_chart(int h, int w, vector <int> r, vector <int> c) {
H = h, W = w, R = r, C = c;
int minR = H - 1, maxR = 0, minC = W - 1, maxC = 0;
for(int i = 0; i < H * W; i++) {
minR = min(minR, R[i]);
maxR = max(maxR, R[i]);
minC = min(minC, C[i]);
maxC = max(maxC, C[i]);
state[i] = {minR, maxR, minC, maxC};
update(1, 0, H * W - 1, i, (maxR - minR + 1) * (maxC - minC + 1) == i + 1);
}
}
int swap_seats(int a, int b) {
if(a > b) {
swap(a, b);
}
swap(R[a], R[b]), swap(C[a], C[b]);
int minR = H - 1, maxR = 0, minC = W - 1, maxC = 0;
if(a > 0) {
minR = state[a - 1].minR;
maxR = state[a - 1].maxR;
minC = state[a - 1].minC;
maxC = state[a - 1].maxC;
}
for(int i = a; i <= b; i++) {
minR = min(minR, R[i]);
maxR = max(maxR, R[i]);
minC = min(minC, C[i]);
maxC = max(maxC, C[i]);
state[i] = {minR, maxR, minC, maxC};
update(1, 0, H * W - 1, i, (maxR - minR + 1) * (maxC - minC + 1) == i + 1);
}
return tree[1];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
340 KB |
Output is correct |
2 |
Correct |
4 ms |
448 KB |
Output is correct |
3 |
Correct |
10 ms |
468 KB |
Output is correct |
4 |
Correct |
8 ms |
452 KB |
Output is correct |
5 |
Correct |
8 ms |
468 KB |
Output is correct |
6 |
Correct |
8 ms |
468 KB |
Output is correct |
7 |
Correct |
8 ms |
456 KB |
Output is correct |
8 |
Correct |
7 ms |
412 KB |
Output is correct |
9 |
Correct |
8 ms |
476 KB |
Output is correct |
10 |
Correct |
8 ms |
444 KB |
Output is correct |
11 |
Correct |
9 ms |
484 KB |
Output is correct |
12 |
Correct |
9 ms |
448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
340 KB |
Output is correct |
2 |
Correct |
4 ms |
448 KB |
Output is correct |
3 |
Correct |
10 ms |
468 KB |
Output is correct |
4 |
Correct |
8 ms |
452 KB |
Output is correct |
5 |
Correct |
8 ms |
468 KB |
Output is correct |
6 |
Correct |
8 ms |
468 KB |
Output is correct |
7 |
Correct |
8 ms |
456 KB |
Output is correct |
8 |
Correct |
7 ms |
412 KB |
Output is correct |
9 |
Correct |
8 ms |
476 KB |
Output is correct |
10 |
Correct |
8 ms |
444 KB |
Output is correct |
11 |
Correct |
9 ms |
484 KB |
Output is correct |
12 |
Correct |
9 ms |
448 KB |
Output is correct |
13 |
Correct |
1542 ms |
1028 KB |
Output is correct |
14 |
Correct |
1583 ms |
964 KB |
Output is correct |
15 |
Correct |
1540 ms |
1048 KB |
Output is correct |
16 |
Correct |
1518 ms |
1032 KB |
Output is correct |
17 |
Correct |
1544 ms |
1032 KB |
Output is correct |
18 |
Correct |
1576 ms |
1024 KB |
Output is correct |
19 |
Correct |
1558 ms |
1028 KB |
Output is correct |
20 |
Correct |
1601 ms |
1032 KB |
Output is correct |
21 |
Correct |
1544 ms |
1040 KB |
Output is correct |
22 |
Correct |
1548 ms |
1032 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4054 ms |
47688 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2361 ms |
864 KB |
Output is correct |
2 |
Correct |
2752 ms |
6092 KB |
Output is correct |
3 |
Correct |
3475 ms |
63596 KB |
Output is correct |
4 |
Correct |
3575 ms |
63648 KB |
Output is correct |
5 |
Correct |
3442 ms |
63684 KB |
Output is correct |
6 |
Correct |
3356 ms |
63544 KB |
Output is correct |
7 |
Correct |
3522 ms |
63620 KB |
Output is correct |
8 |
Correct |
3477 ms |
63720 KB |
Output is correct |
9 |
Correct |
3611 ms |
63592 KB |
Output is correct |
10 |
Correct |
3403 ms |
63612 KB |
Output is correct |
11 |
Correct |
3625 ms |
63648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
1360 KB |
Output is correct |
2 |
Correct |
21 ms |
1972 KB |
Output is correct |
3 |
Correct |
85 ms |
1976 KB |
Output is correct |
4 |
Correct |
1045 ms |
2004 KB |
Output is correct |
5 |
Execution timed out |
4021 ms |
2064 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
340 KB |
Output is correct |
2 |
Correct |
4 ms |
448 KB |
Output is correct |
3 |
Correct |
10 ms |
468 KB |
Output is correct |
4 |
Correct |
8 ms |
452 KB |
Output is correct |
5 |
Correct |
8 ms |
468 KB |
Output is correct |
6 |
Correct |
8 ms |
468 KB |
Output is correct |
7 |
Correct |
8 ms |
456 KB |
Output is correct |
8 |
Correct |
7 ms |
412 KB |
Output is correct |
9 |
Correct |
8 ms |
476 KB |
Output is correct |
10 |
Correct |
8 ms |
444 KB |
Output is correct |
11 |
Correct |
9 ms |
484 KB |
Output is correct |
12 |
Correct |
9 ms |
448 KB |
Output is correct |
13 |
Correct |
1542 ms |
1028 KB |
Output is correct |
14 |
Correct |
1583 ms |
964 KB |
Output is correct |
15 |
Correct |
1540 ms |
1048 KB |
Output is correct |
16 |
Correct |
1518 ms |
1032 KB |
Output is correct |
17 |
Correct |
1544 ms |
1032 KB |
Output is correct |
18 |
Correct |
1576 ms |
1024 KB |
Output is correct |
19 |
Correct |
1558 ms |
1028 KB |
Output is correct |
20 |
Correct |
1601 ms |
1032 KB |
Output is correct |
21 |
Correct |
1544 ms |
1040 KB |
Output is correct |
22 |
Correct |
1548 ms |
1032 KB |
Output is correct |
23 |
Execution timed out |
4054 ms |
47688 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |