# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
122325 |
2019-06-28T04:58:09 Z |
nvmdava |
Seats (IOI18_seats) |
C++17 |
|
3559 ms |
73448 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> r, c;
vector<vector<int> > s;
int cnt[2097152], mn[2097152], lz[2097152];
int L, R, val;
inline void push(int id, int l, int r){
mn[id] += lz[id];
if(l != r){
lz[id << 1] += lz[id];
lz[id << 1 | 1] += lz[id];
}
lz[id] = 0;
}
inline void update(int id, int l, int r){
push(id, l, r);
if(l > R || r < L) return;
if(l >= L && r <= R){
lz[id] += val;
push(id, l, r);
return;
}
int m = (l + r) >> 1;
update(id << 1, l, m);
update(id << 1 | 1, m + 1, r);
if(mn[id << 1] < mn[id << 1 | 1]){
mn[id] = mn[id << 1];
cnt[id] = cnt[id << 1];
} else if(mn[id << 1] > mn[id << 1 | 1]){
mn[id] = mn[id << 1 | 1];
cnt[id] = cnt[id << 1 | 1];
} else {
mn[id] = mn[id << 1];
cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
}
}
inline void build(int id, int l, int r){
if(l == r){
cnt[id] = 1;
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
}
vector<int> ord;
inline void order(int& a, int& b, int& c, int& d){
ord = {a, b, c, d};
for(int i = 1 ; i < 4 ; i++){
for(int j = 0 ; j < 3 ; j++){
if( ord[j] > ord[j+1] ){
swap(ord[j], ord[j+1]);
}
}
}
}
int n;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
n = H * W;
int i, j;
if(H > W){
swap(H, W);
swap(R, C);
}
for(i = 0; i <= H + 1; i++){
s.push_back(vector<int>(W + 2, n + 1));
}
r.push_back(0);
c.push_back(0);
build(1, 1, n);
for(i = 0; i < n; i++){
R[i]++;
C[i]++;
s[R[i]][C[i]] = i + 1;
c.push_back(C[i]);
r.push_back(R[i]);
}
val = 1;
for(i = 0; i <= H; i++){
for(j = 0; j <= W; j++){
order(s[i][j], s[i + 1][j], s[i][j + 1], s[i + 1][j + 1]);
L = ord[0];
::R = ord[1] - 1;
if(L <= ::R)update(1, 1, n);
L = ord[2];
::R = ord[3] - 1;
if(L <= ::R)update(1, 1, n);
}
}
}
int dx[] = {1, -1, 1, -1};
int dy[] = {1, 1, -1, -1};
int t[2];
int swap_seats(int a, int b){
a++; b++;
val = -1;
int i, j, x, y;
t[0] = a; t[1] = b;
for(j = 0; j < 2; j++){
x = r[t[j]], y = c[t[j]];
for(i = 0; i < 4; i++){
order(s[x][y], s[x + dx[i]][y], s[x][y + dy[i]], s[x + dx[i]][y + dy[i]]);
L = ord[0];
R = ord[1] - 1;
if(L <= R) update(1, 1, n);
L = ord[2];
R = ord[3] - 1;
if(L <= R) update(1, 1, n);
}
}
swap(r[a], r[b]);
swap(c[a], c[b]);
swap(s[r[a]][c[a]], s[r[b]][c[b]]);
val = 1;
for(j = 0; j < 2; j++){
x = r[t[j]], y = c[t[j]];
for(i = 0; i < 4; i++){
order(s[x][y], s[x + dx[i]][y], s[x][y + dy[i]], s[x + dx[i]][y + dy[i]]);
L = ord[0];
R = ord[1] - 1;
if(L <= R) update(1, 1, n);
L = ord[2];
R = ord[3] - 1;
if(L <= R) update(1, 1, n);
}
}
return cnt[1];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
512 KB |
Output is correct |
2 |
Correct |
21 ms |
488 KB |
Output is correct |
3 |
Correct |
30 ms |
504 KB |
Output is correct |
4 |
Correct |
17 ms |
468 KB |
Output is correct |
5 |
Correct |
16 ms |
512 KB |
Output is correct |
6 |
Correct |
26 ms |
512 KB |
Output is correct |
7 |
Correct |
28 ms |
504 KB |
Output is correct |
8 |
Correct |
27 ms |
508 KB |
Output is correct |
9 |
Correct |
26 ms |
504 KB |
Output is correct |
10 |
Correct |
28 ms |
504 KB |
Output is correct |
11 |
Correct |
26 ms |
632 KB |
Output is correct |
12 |
Correct |
16 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
512 KB |
Output is correct |
2 |
Correct |
21 ms |
488 KB |
Output is correct |
3 |
Correct |
30 ms |
504 KB |
Output is correct |
4 |
Correct |
17 ms |
468 KB |
Output is correct |
5 |
Correct |
16 ms |
512 KB |
Output is correct |
6 |
Correct |
26 ms |
512 KB |
Output is correct |
7 |
Correct |
28 ms |
504 KB |
Output is correct |
8 |
Correct |
27 ms |
508 KB |
Output is correct |
9 |
Correct |
26 ms |
504 KB |
Output is correct |
10 |
Correct |
28 ms |
504 KB |
Output is correct |
11 |
Correct |
26 ms |
632 KB |
Output is correct |
12 |
Correct |
16 ms |
512 KB |
Output is correct |
13 |
Correct |
68 ms |
1152 KB |
Output is correct |
14 |
Correct |
80 ms |
1152 KB |
Output is correct |
15 |
Correct |
43 ms |
1152 KB |
Output is correct |
16 |
Correct |
33 ms |
1280 KB |
Output is correct |
17 |
Correct |
58 ms |
1152 KB |
Output is correct |
18 |
Correct |
56 ms |
1152 KB |
Output is correct |
19 |
Correct |
55 ms |
1152 KB |
Output is correct |
20 |
Correct |
48 ms |
1276 KB |
Output is correct |
21 |
Correct |
34 ms |
1280 KB |
Output is correct |
22 |
Correct |
34 ms |
1280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2425 ms |
52652 KB |
Output is correct |
2 |
Correct |
1120 ms |
52772 KB |
Output is correct |
3 |
Correct |
1037 ms |
52636 KB |
Output is correct |
4 |
Correct |
855 ms |
52644 KB |
Output is correct |
5 |
Correct |
911 ms |
52744 KB |
Output is correct |
6 |
Correct |
815 ms |
52636 KB |
Output is correct |
7 |
Correct |
953 ms |
52772 KB |
Output is correct |
8 |
Correct |
1057 ms |
52636 KB |
Output is correct |
9 |
Correct |
1061 ms |
52900 KB |
Output is correct |
10 |
Correct |
1109 ms |
52900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
1184 KB |
Output is correct |
2 |
Correct |
162 ms |
6204 KB |
Output is correct |
3 |
Correct |
890 ms |
52644 KB |
Output is correct |
4 |
Correct |
2326 ms |
52644 KB |
Output is correct |
5 |
Correct |
793 ms |
60528 KB |
Output is correct |
6 |
Correct |
2546 ms |
60416 KB |
Output is correct |
7 |
Correct |
906 ms |
55192 KB |
Output is correct |
8 |
Correct |
1169 ms |
52720 KB |
Output is correct |
9 |
Correct |
858 ms |
52668 KB |
Output is correct |
10 |
Correct |
948 ms |
53376 KB |
Output is correct |
11 |
Correct |
860 ms |
56576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
1396 KB |
Output is correct |
2 |
Correct |
88 ms |
1396 KB |
Output is correct |
3 |
Correct |
142 ms |
1420 KB |
Output is correct |
4 |
Correct |
204 ms |
1456 KB |
Output is correct |
5 |
Correct |
326 ms |
2132 KB |
Output is correct |
6 |
Correct |
1307 ms |
60812 KB |
Output is correct |
7 |
Correct |
1642 ms |
60924 KB |
Output is correct |
8 |
Correct |
1261 ms |
60924 KB |
Output is correct |
9 |
Correct |
3050 ms |
60796 KB |
Output is correct |
10 |
Correct |
1269 ms |
60796 KB |
Output is correct |
11 |
Correct |
1269 ms |
60924 KB |
Output is correct |
12 |
Correct |
1195 ms |
60924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
512 KB |
Output is correct |
2 |
Correct |
21 ms |
488 KB |
Output is correct |
3 |
Correct |
30 ms |
504 KB |
Output is correct |
4 |
Correct |
17 ms |
468 KB |
Output is correct |
5 |
Correct |
16 ms |
512 KB |
Output is correct |
6 |
Correct |
26 ms |
512 KB |
Output is correct |
7 |
Correct |
28 ms |
504 KB |
Output is correct |
8 |
Correct |
27 ms |
508 KB |
Output is correct |
9 |
Correct |
26 ms |
504 KB |
Output is correct |
10 |
Correct |
28 ms |
504 KB |
Output is correct |
11 |
Correct |
26 ms |
632 KB |
Output is correct |
12 |
Correct |
16 ms |
512 KB |
Output is correct |
13 |
Correct |
68 ms |
1152 KB |
Output is correct |
14 |
Correct |
80 ms |
1152 KB |
Output is correct |
15 |
Correct |
43 ms |
1152 KB |
Output is correct |
16 |
Correct |
33 ms |
1280 KB |
Output is correct |
17 |
Correct |
58 ms |
1152 KB |
Output is correct |
18 |
Correct |
56 ms |
1152 KB |
Output is correct |
19 |
Correct |
55 ms |
1152 KB |
Output is correct |
20 |
Correct |
48 ms |
1276 KB |
Output is correct |
21 |
Correct |
34 ms |
1280 KB |
Output is correct |
22 |
Correct |
34 ms |
1280 KB |
Output is correct |
23 |
Correct |
2425 ms |
52652 KB |
Output is correct |
24 |
Correct |
1120 ms |
52772 KB |
Output is correct |
25 |
Correct |
1037 ms |
52636 KB |
Output is correct |
26 |
Correct |
855 ms |
52644 KB |
Output is correct |
27 |
Correct |
911 ms |
52744 KB |
Output is correct |
28 |
Correct |
815 ms |
52636 KB |
Output is correct |
29 |
Correct |
953 ms |
52772 KB |
Output is correct |
30 |
Correct |
1057 ms |
52636 KB |
Output is correct |
31 |
Correct |
1061 ms |
52900 KB |
Output is correct |
32 |
Correct |
1109 ms |
52900 KB |
Output is correct |
33 |
Correct |
69 ms |
1184 KB |
Output is correct |
34 |
Correct |
162 ms |
6204 KB |
Output is correct |
35 |
Correct |
890 ms |
52644 KB |
Output is correct |
36 |
Correct |
2326 ms |
52644 KB |
Output is correct |
37 |
Correct |
793 ms |
60528 KB |
Output is correct |
38 |
Correct |
2546 ms |
60416 KB |
Output is correct |
39 |
Correct |
906 ms |
55192 KB |
Output is correct |
40 |
Correct |
1169 ms |
52720 KB |
Output is correct |
41 |
Correct |
858 ms |
52668 KB |
Output is correct |
42 |
Correct |
948 ms |
53376 KB |
Output is correct |
43 |
Correct |
860 ms |
56576 KB |
Output is correct |
44 |
Correct |
45 ms |
1396 KB |
Output is correct |
45 |
Correct |
88 ms |
1396 KB |
Output is correct |
46 |
Correct |
142 ms |
1420 KB |
Output is correct |
47 |
Correct |
204 ms |
1456 KB |
Output is correct |
48 |
Correct |
326 ms |
2132 KB |
Output is correct |
49 |
Correct |
1307 ms |
60812 KB |
Output is correct |
50 |
Correct |
1642 ms |
60924 KB |
Output is correct |
51 |
Correct |
1261 ms |
60924 KB |
Output is correct |
52 |
Correct |
3050 ms |
60796 KB |
Output is correct |
53 |
Correct |
1269 ms |
60796 KB |
Output is correct |
54 |
Correct |
1269 ms |
60924 KB |
Output is correct |
55 |
Correct |
1195 ms |
60924 KB |
Output is correct |
56 |
Correct |
120 ms |
1352 KB |
Output is correct |
57 |
Correct |
318 ms |
1580 KB |
Output is correct |
58 |
Correct |
551 ms |
2172 KB |
Output is correct |
59 |
Correct |
1841 ms |
53200 KB |
Output is correct |
60 |
Correct |
3559 ms |
53168 KB |
Output is correct |
61 |
Correct |
1701 ms |
69704 KB |
Output is correct |
62 |
Correct |
1348 ms |
73448 KB |
Output is correct |
63 |
Correct |
3444 ms |
72188 KB |
Output is correct |
64 |
Correct |
2032 ms |
70324 KB |
Output is correct |
65 |
Correct |
1923 ms |
69540 KB |
Output is correct |
66 |
Correct |
1823 ms |
69540 KB |
Output is correct |
67 |
Correct |
2021 ms |
70396 KB |
Output is correct |
68 |
Correct |
1449 ms |
72188 KB |
Output is correct |
69 |
Correct |
3282 ms |
73352 KB |
Output is correct |