# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
593376 |
2022-07-11T01:58:53 Z |
Temmie |
Seats (IOI18_seats) |
C++17 |
|
3810 ms |
138828 KB |
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
constexpr const int mxn = 1e6 + 3;
struct Seg {
int size;
int res[mxn << 2], min[mxn << 2], laz[mxn << 2];
Seg() = default;
Seg(int s) {
memset(res, 0, sizeof(res));
memset(min, 0, sizeof(min));
memset(laz, 0, sizeof(laz));
size = s;
build(0, 0, size);
}
void build(int now, int l, int r) {
if (!(r - l - 1)) {
res[now] = 1;
return;
}
int mid = (l + r) >> 1;
build(now * 2 + 1, l, mid);
build(now * 2 + 2, mid, r);
res[now] = res[now * 2 + 1] + res[now * 2 + 2];
}
void push(int now, int l, int r) {
min[now] += laz[now];
if (r - l - 1) {
laz[now * 2 + 1] += laz[now];
laz[now * 2 + 2] += laz[now];
}
laz[now] = 0;
}
void update(int l, int r, int val) {
if (r <= l) {
return;
}
update(l, r, val, 0, 0, size);
}
void update(int tl, int tr, int val, int now, int l, int r) {
if (l >= tr || r <= tl) {
return;
}
if (l >= tl && r <= tr) {
laz[now] += val;
return;
}
push(now, l, r);
int mid = (l + r) >> 1;
update(tl, tr, val, now * 2 + 1, l, mid);
update(tl, tr, val, now * 2 + 2, mid, r);
push(now * 2 + 1, l, mid);
push(now * 2 + 2, mid, r);
min[now] = std::min(min[now * 2 + 1], min[now * 2 + 2]);
res[now] =
(min[now * 2 + 1] == min[now] ? res[now * 2 + 1] : 0) +
(min[now * 2 + 2] == min[now] ? res[now * 2 + 2] : 0);
}
int query() {
push(0, 0, size);
return min[0] == 4 ? res[0] : 0;
}
} seg;
int n, m, k;
std::vector <int> g;
int inv[mxn];
void fix(int i, int j, int val) {
int vals[4] = {
g[i * k + j],
g[(i + 1) * k + j],
g[i * k + j + 1],
g[(i + 1) * k + j + 1]
};
std::sort(vals, vals + 4);
seg.update(vals[0], vals[1], val);
seg.update(vals[2], vals[3], val);
}
void give_initial_chart(int h, int w, std::vector <int> r, std::vector <int> c) {
n = h;
m = w;
k = m + 2;
seg = Seg(n * m);
g.resize((n + 2) * (m + 2), n * m);
for (int i = 0; i < n * m; i++) {
inv[i] = ++r[i] * k + ++c[i];
g[r[i] * k + c[i]] = i;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
fix(i, j, 1);
}
}
}
int swap_seats(int a, int b) {
int av[2] = { inv[a] / k, inv[a] % k };
int bv[2] = { inv[b] / k, inv[b] % k };
for (int di = -1; di <= 0; di++) {
for (int dj = -1; dj <= 0; dj++) {
fix(av[0] + di, av[1] + dj, -1);
fix(bv[0] + di, bv[1] + dj, -1);
}
}
std::swap(g[inv[a]], g[inv[b]]);
std::swap(inv[a], inv[b]);
for (int di = -1; di <= 0; di++) {
for (int dj = -1; dj <= 0; dj++) {
fix(av[0] + di, av[1] + dj, 1);
fix(bv[0] + di, bv[1] + dj, 1);
}
}
return seg.query();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
94280 KB |
Output is correct |
2 |
Correct |
62 ms |
94272 KB |
Output is correct |
3 |
Correct |
81 ms |
94292 KB |
Output is correct |
4 |
Correct |
60 ms |
94288 KB |
Output is correct |
5 |
Correct |
58 ms |
94284 KB |
Output is correct |
6 |
Correct |
71 ms |
94276 KB |
Output is correct |
7 |
Correct |
75 ms |
94268 KB |
Output is correct |
8 |
Correct |
70 ms |
94328 KB |
Output is correct |
9 |
Correct |
72 ms |
94320 KB |
Output is correct |
10 |
Correct |
74 ms |
94284 KB |
Output is correct |
11 |
Correct |
71 ms |
94368 KB |
Output is correct |
12 |
Correct |
60 ms |
94264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
94280 KB |
Output is correct |
2 |
Correct |
62 ms |
94272 KB |
Output is correct |
3 |
Correct |
81 ms |
94292 KB |
Output is correct |
4 |
Correct |
60 ms |
94288 KB |
Output is correct |
5 |
Correct |
58 ms |
94284 KB |
Output is correct |
6 |
Correct |
71 ms |
94276 KB |
Output is correct |
7 |
Correct |
75 ms |
94268 KB |
Output is correct |
8 |
Correct |
70 ms |
94328 KB |
Output is correct |
9 |
Correct |
72 ms |
94320 KB |
Output is correct |
10 |
Correct |
74 ms |
94284 KB |
Output is correct |
11 |
Correct |
71 ms |
94368 KB |
Output is correct |
12 |
Correct |
60 ms |
94264 KB |
Output is correct |
13 |
Correct |
129 ms |
94496 KB |
Output is correct |
14 |
Correct |
145 ms |
94436 KB |
Output is correct |
15 |
Correct |
103 ms |
94588 KB |
Output is correct |
16 |
Correct |
83 ms |
94556 KB |
Output is correct |
17 |
Correct |
115 ms |
94532 KB |
Output is correct |
18 |
Correct |
112 ms |
94504 KB |
Output is correct |
19 |
Correct |
108 ms |
94504 KB |
Output is correct |
20 |
Correct |
98 ms |
94540 KB |
Output is correct |
21 |
Correct |
87 ms |
94548 KB |
Output is correct |
22 |
Correct |
83 ms |
94540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2363 ms |
117776 KB |
Output is correct |
2 |
Correct |
1306 ms |
117848 KB |
Output is correct |
3 |
Correct |
1235 ms |
117708 KB |
Output is correct |
4 |
Correct |
1125 ms |
117772 KB |
Output is correct |
5 |
Correct |
1169 ms |
117836 KB |
Output is correct |
6 |
Correct |
1095 ms |
117848 KB |
Output is correct |
7 |
Correct |
1167 ms |
117704 KB |
Output is correct |
8 |
Correct |
1194 ms |
117772 KB |
Output is correct |
9 |
Correct |
1215 ms |
117784 KB |
Output is correct |
10 |
Correct |
1219 ms |
117788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
94512 KB |
Output is correct |
2 |
Correct |
236 ms |
96384 KB |
Output is correct |
3 |
Correct |
1158 ms |
117708 KB |
Output is correct |
4 |
Correct |
2346 ms |
117848 KB |
Output is correct |
5 |
Correct |
1054 ms |
125644 KB |
Output is correct |
6 |
Correct |
2194 ms |
125664 KB |
Output is correct |
7 |
Correct |
1121 ms |
120396 KB |
Output is correct |
8 |
Correct |
1307 ms |
117836 KB |
Output is correct |
9 |
Correct |
1138 ms |
117844 KB |
Output is correct |
10 |
Correct |
1208 ms |
118536 KB |
Output is correct |
11 |
Correct |
1106 ms |
121560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
95288 KB |
Output is correct |
2 |
Correct |
127 ms |
95216 KB |
Output is correct |
3 |
Correct |
219 ms |
95292 KB |
Output is correct |
4 |
Correct |
313 ms |
95232 KB |
Output is correct |
5 |
Correct |
491 ms |
95528 KB |
Output is correct |
6 |
Correct |
1628 ms |
126028 KB |
Output is correct |
7 |
Correct |
1868 ms |
126056 KB |
Output is correct |
8 |
Correct |
1590 ms |
125940 KB |
Output is correct |
9 |
Correct |
2978 ms |
125940 KB |
Output is correct |
10 |
Correct |
1562 ms |
125904 KB |
Output is correct |
11 |
Correct |
1570 ms |
125896 KB |
Output is correct |
12 |
Correct |
1502 ms |
126044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
94280 KB |
Output is correct |
2 |
Correct |
62 ms |
94272 KB |
Output is correct |
3 |
Correct |
81 ms |
94292 KB |
Output is correct |
4 |
Correct |
60 ms |
94288 KB |
Output is correct |
5 |
Correct |
58 ms |
94284 KB |
Output is correct |
6 |
Correct |
71 ms |
94276 KB |
Output is correct |
7 |
Correct |
75 ms |
94268 KB |
Output is correct |
8 |
Correct |
70 ms |
94328 KB |
Output is correct |
9 |
Correct |
72 ms |
94320 KB |
Output is correct |
10 |
Correct |
74 ms |
94284 KB |
Output is correct |
11 |
Correct |
71 ms |
94368 KB |
Output is correct |
12 |
Correct |
60 ms |
94264 KB |
Output is correct |
13 |
Correct |
129 ms |
94496 KB |
Output is correct |
14 |
Correct |
145 ms |
94436 KB |
Output is correct |
15 |
Correct |
103 ms |
94588 KB |
Output is correct |
16 |
Correct |
83 ms |
94556 KB |
Output is correct |
17 |
Correct |
115 ms |
94532 KB |
Output is correct |
18 |
Correct |
112 ms |
94504 KB |
Output is correct |
19 |
Correct |
108 ms |
94504 KB |
Output is correct |
20 |
Correct |
98 ms |
94540 KB |
Output is correct |
21 |
Correct |
87 ms |
94548 KB |
Output is correct |
22 |
Correct |
83 ms |
94540 KB |
Output is correct |
23 |
Correct |
2363 ms |
117776 KB |
Output is correct |
24 |
Correct |
1306 ms |
117848 KB |
Output is correct |
25 |
Correct |
1235 ms |
117708 KB |
Output is correct |
26 |
Correct |
1125 ms |
117772 KB |
Output is correct |
27 |
Correct |
1169 ms |
117836 KB |
Output is correct |
28 |
Correct |
1095 ms |
117848 KB |
Output is correct |
29 |
Correct |
1167 ms |
117704 KB |
Output is correct |
30 |
Correct |
1194 ms |
117772 KB |
Output is correct |
31 |
Correct |
1215 ms |
117784 KB |
Output is correct |
32 |
Correct |
1219 ms |
117788 KB |
Output is correct |
33 |
Correct |
126 ms |
94512 KB |
Output is correct |
34 |
Correct |
236 ms |
96384 KB |
Output is correct |
35 |
Correct |
1158 ms |
117708 KB |
Output is correct |
36 |
Correct |
2346 ms |
117848 KB |
Output is correct |
37 |
Correct |
1054 ms |
125644 KB |
Output is correct |
38 |
Correct |
2194 ms |
125664 KB |
Output is correct |
39 |
Correct |
1121 ms |
120396 KB |
Output is correct |
40 |
Correct |
1307 ms |
117836 KB |
Output is correct |
41 |
Correct |
1138 ms |
117844 KB |
Output is correct |
42 |
Correct |
1208 ms |
118536 KB |
Output is correct |
43 |
Correct |
1106 ms |
121560 KB |
Output is correct |
44 |
Correct |
81 ms |
95288 KB |
Output is correct |
45 |
Correct |
127 ms |
95216 KB |
Output is correct |
46 |
Correct |
219 ms |
95292 KB |
Output is correct |
47 |
Correct |
313 ms |
95232 KB |
Output is correct |
48 |
Correct |
491 ms |
95528 KB |
Output is correct |
49 |
Correct |
1628 ms |
126028 KB |
Output is correct |
50 |
Correct |
1868 ms |
126056 KB |
Output is correct |
51 |
Correct |
1590 ms |
125940 KB |
Output is correct |
52 |
Correct |
2978 ms |
125940 KB |
Output is correct |
53 |
Correct |
1562 ms |
125904 KB |
Output is correct |
54 |
Correct |
1570 ms |
125896 KB |
Output is correct |
55 |
Correct |
1502 ms |
126044 KB |
Output is correct |
56 |
Correct |
150 ms |
95176 KB |
Output is correct |
57 |
Correct |
394 ms |
95252 KB |
Output is correct |
58 |
Correct |
719 ms |
95504 KB |
Output is correct |
59 |
Correct |
2162 ms |
118220 KB |
Output is correct |
60 |
Correct |
3810 ms |
118088 KB |
Output is correct |
61 |
Correct |
2085 ms |
134988 KB |
Output is correct |
62 |
Correct |
1732 ms |
138828 KB |
Output is correct |
63 |
Correct |
3505 ms |
137328 KB |
Output is correct |
64 |
Correct |
2414 ms |
135516 KB |
Output is correct |
65 |
Correct |
2132 ms |
134856 KB |
Output is correct |
66 |
Correct |
2282 ms |
134880 KB |
Output is correct |
67 |
Correct |
2344 ms |
135492 KB |
Output is correct |
68 |
Correct |
1889 ms |
137412 KB |
Output is correct |
69 |
Correct |
3294 ms |
138620 KB |
Output is correct |