#include <bits/stdc++.h>
#include "books.h"
using namespace std;
const int INF = 0x3f3f3f3f;
vector<vector<pair<int, int>>> adj;
int create()
{
adj.emplace_back();
return adj.size()-1;
}
int build(int ini, int fim)
{
if (ini == fim)
{
return ini;
}
int pos = create();
int m = (ini + fim) >> 1;
adj[pos].emplace_back(build(ini, m), 0);
adj[pos].emplace_back(build(m+1, fim), 0);
return pos;
}
void update(int pos, int ini, int fim, int p, int q, int val)
{
if (q < ini || p > fim) return;
if (p <= ini && fim <= q) {adj[val].emplace_back(pos, 0); return;}
int m = (ini + fim) >> 1;
int e = adj[pos][0].first, d = adj[pos][1].first;
update(e, ini, m, p, q, val);
update(d, m+1, fim, p, q, val);
}
long long minimum_walk(std::vector<int> p, int s) {
int N = p.size();
long long resp = 0;
for (int i = 0; i < N; i++) resp += abs(p[i]-i);
if (resp == 0) return 0;
vector<int> minSuf(N); minSuf.back() = p.back();
for (int i = N-2; i >= 0; i--) minSuf[i] = min(minSuf[i+1], p[i]);
vector<int> maxPref(N); maxPref[0] = p[0];
for (int i = 1; i < N; i++) maxPref[i] = max(maxPref[i-1], p[i]);
int lastS = 0; vector<pair<int, int>> comps;
for (int i = 1; i < N; i++) if (maxPref[i-1] < i && minSuf[i] >= i)
{
comps.emplace_back(lastS, i-1);
// resp += i - lastS;
lastS = i;
}
comps.emplace_back(lastS, N-1);
while (!comps.empty() && comps.back().first == comps.back().second) comps.pop_back();
reverse(comps.begin(), comps.end());
while (!comps.empty() && comps.back().first == comps.back().second) comps.pop_back();
reverse(comps.begin(), comps.end());
for (int i = 0; i+1 < comps.size(); i++) resp += 2*(comps[i+1].first - comps[i].second);
if (s < comps[0].first) resp += 2*(comps[0].first - s);
else if (s > comps.back().second) resp += 2*(s - comps.back().second);
else
{
//Parte ruim
adj.resize(N);
int root = build(0, N-1);
for (int i = 0; i < N; i++)
{
int l = min(i, p[i]), r = max(i, p[i]);
update(root, 0, N-1, l, r, i);
if (l > 0) adj[i].emplace_back(l-1, +1);
if (r+1 < N) adj[i].emplace_back(r+1, +1);
}
priority_queue<pair<int, int>> q; vector<int> Marc(adj.size()), Dist(adj.size(), INF);
q.emplace(Dist[s] = 0, s);
while (!q.empty())
{
auto [d, cur] = q.top(); q.pop();
if (Marc[cur]) continue;
Marc[cur] = 1;
for (auto [viz, p] : adj[cur])
{
if (d + p < Dist[viz])
{
Dist[viz] = d + p;
q.emplace(Dist[viz], viz);
}
}
}
for (auto [x, y] : comps)
{
if (x <= s && s <= y)
{
resp += 2*Dist[x];
break;
}
}
}
return resp;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:57:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i = 0; i+1 < comps.size(); i++) resp += 2*(comps[i+1].first - comps[i].second);
| ~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 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 |
344 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 |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 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 |
348 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 |
344 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 |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 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 |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
372 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
1 ms |
604 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 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 |
344 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 |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 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 |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
372 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
1 ms |
604 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Execution timed out |
2061 ms |
372712 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
604 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3582' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 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 |
344 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 |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 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 |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
372 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
1 ms |
604 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Execution timed out |
2061 ms |
372712 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |