# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1048818 | 2024-08-08T09:38:39 Z | Gromp15 | Ancient Books (IOI17_books) | C++17 | 180 ms | 188432 KB |
#include <bits/stdc++.h> #include "books.h" #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() using namespace std; template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template<typename op> struct sparse_table { op x; vector<vector<int>> table; sparse_table(const vector<int>& a, op t) : table(__lg(sz(a)) + 1, vector<int>(sz(a))), x(t) { for (int i = 0; i < sz(a); i++) table[0][i] = a[i]; for (int i = 1; i <= __lg(sz(a)); i++) { for (int j = 0; j < sz(a); j++) { if (j + (1 << i) - 1 >= sz(a)) break; table[i][j] = x(table[i-1][j], table[i-1][j+(1<<(i-1))]); } } } int query(int l, int r) { int h = __lg(r-l+1); return x(table[h][l], table[h][r-(1<<h)+1]); } }; long long minimum_walk(std::vector<int> p, int s) { int n = p.size(); { int l = s, r = s; bool F = 0; for (int i = 0; i < n; i++) if (i != p[i]) ckmin(l, i), r = i, F = 1; if (!F) return 0; p = vector<int>(p.begin() + l, p.begin() + r + 1); n = r - l + 1; } vector<int> L(n), R(n); long long ans = 0; vector<bool> vis(n); for (int i = 0; i < n; i++) if (!vis[i]) { int right = i; int tmp = i; vector<int> cur; while (!vis[tmp]) { cur.emplace_back(tmp); ckmax(right, tmp); ans += abs(tmp - p[tmp]), vis[tmp] = 1, tmp = p[tmp]; } for (int v : cur) L[v] = i, R[v] = right; } sparse_table mn(L, [&](int x, int y) { return min(x, y); }); sparse_table mx(R, [&](int x, int y) { return max(x, y); }); vector<int> to(n); // [i, s] can reach where for (int i = 0; i <= s; i++) { to[i] = mn.query(i, s) < i ? to[mn.query(i, s)] : mn.query(i, s); } vector<int> req(n); for (int i = 0; i <= s; i++) req[i] = 1 + (to[i] ? req[to[i] - 1] : 0); vector<int> from(n); for (int i = n-1; i >= s; i--) { from[i] = mx.query(s, i) > i ? from[mx.query(s, i)] : mx.query(s, i); } vector<int> req2(n); for (int i = n-1; i >= s; i--) req2[i] = 1 + (from[i] + 1 < n ? req2[from[i] + 1] : 0); return ans + (req2[s] - 1 + (to[s] ? req[to[s] - 1] : 0)) * 2; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 0 ms | 348 KB | Output is correct |
22 | Correct | 0 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 0 ms | 348 KB | Output is correct |
22 | Correct | 0 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 0 ms | 348 KB | Output is correct |
30 | Correct | 156 ms | 188296 KB | Output is correct |
31 | Correct | 141 ms | 188352 KB | Output is correct |
32 | Correct | 52 ms | 8016 KB | Output is correct |
33 | Correct | 136 ms | 188176 KB | Output is correct |
34 | Correct | 145 ms | 188172 KB | Output is correct |
35 | Correct | 145 ms | 188172 KB | Output is correct |
36 | Correct | 134 ms | 188256 KB | Output is correct |
37 | Correct | 129 ms | 188432 KB | Output is correct |
38 | Correct | 120 ms | 188340 KB | Output is correct |
39 | Correct | 119 ms | 188348 KB | Output is correct |
40 | Correct | 122 ms | 188176 KB | Output is correct |
41 | Correct | 156 ms | 188328 KB | Output is correct |
42 | Correct | 144 ms | 188180 KB | Output is correct |
43 | Correct | 180 ms | 188328 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 348 KB | 3rd lines differ - on the 1st token, expected: '3304', found: '4070' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 0 ms | 348 KB | Output is correct |
22 | Correct | 0 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 0 ms | 348 KB | Output is correct |
30 | Correct | 156 ms | 188296 KB | Output is correct |
31 | Correct | 141 ms | 188352 KB | Output is correct |
32 | Correct | 52 ms | 8016 KB | Output is correct |
33 | Correct | 136 ms | 188176 KB | Output is correct |
34 | Correct | 145 ms | 188172 KB | Output is correct |
35 | Correct | 145 ms | 188172 KB | Output is correct |
36 | Correct | 134 ms | 188256 KB | Output is correct |
37 | Correct | 129 ms | 188432 KB | Output is correct |
38 | Correct | 120 ms | 188340 KB | Output is correct |
39 | Correct | 119 ms | 188348 KB | Output is correct |
40 | Correct | 122 ms | 188176 KB | Output is correct |
41 | Correct | 156 ms | 188328 KB | Output is correct |
42 | Correct | 144 ms | 188180 KB | Output is correct |
43 | Correct | 180 ms | 188328 KB | Output is correct |
44 | Incorrect | 0 ms | 348 KB | 3rd lines differ - on the 1st token, expected: '3304', found: '4070' |
45 | Halted | 0 ms | 0 KB | - |