#include "books.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
typedef long long ll;
typedef pair<int, int> pii;
bool vis[MAXN];
int uf[MAXN];
pii range[MAXN];
// vector<int> in_comp[MAXN];
int par[MAXN];
// int dist[MAXN];
int n;
int _abs(int v) {
return v < 0 ? -v : v;
}
int find(int i) {
return uf[i] == i ? i : uf[i] = find(uf[i]);
}
void merge(int i, int j) {
i = find(i);
j = find(j);
// if (i == j) return;
assert(i != j);
uf[i] = j;
range[i].first = min(range[i].first, range[j].first);
range[i].second = max(range[i].second, range[j].second);
}
ll minimum_walk(vector<int> p, int s) {
ll ans = 0;
n = p.size();
for (int i = 0; i < n; i++) ans += _abs(p[i]-i);
if (ans == 0) return 0;
vector<pii> intervals;
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
int cur = i;
int l = i, r = i;
do {
l = min(l, cur);
r = max(r, cur);
uf[cur] = i;
// in_comp[i].push_back(cur);
vis[cur] = 1;
cur = p[cur];
} while (cur != i);
if (r > l || i == s) intervals.push_back(pii(l, r));
range[i] = pii(l, r);
}
sort(intervals.begin(), intervals.end()); // they are probably already sorted
// fill(dist, dist+n, MAXN);
int curr = intervals[0].second;
vector<int> stck;
for (int i = 0; i < intervals.size(); i++) {
while (!stck.empty() && stck.back() < intervals[i].first) {
int v = stck.back(); stck.pop_back();
if (stck.empty()) par[find(v)] = -1;
else par[find(v)] = find(stck.back());
}
while (!stck.empty() && stck.back() < intervals[i].second) {
int v = stck.back(); stck.pop_back();
merge(v, intervals[i].second);
}
stck.push_back(intervals[i].second);
// assert(curr != intervals[i].first);
if (curr > intervals[i].first) {
curr = max(curr, intervals[i].second);
continue;
}
ans += 2*(intervals[i].first-curr);
curr = intervals[i].second;
}
for (int i = 1; i < stck.size(); i++) par[find(stck[i])] = find(stck[i-1]);
par[find(stck[0])] = -1;
// return 0;
int dist = 0;
s = find(s);
while (par[s] != -1) {
int nxt = find(par[s]);
dist += min(range[nxt].second-range[s].second, range[s].first-range[nxt].first);
s = nxt;
}
return ans+2*dist;
}
Compilation message
books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i = 0; i < intervals.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
books.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 1; i < stck.size(); i++) par[find(stck[i])] = find(stck[i-1]);
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
308 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
308 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
308 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
308 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
312 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
308 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
308 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
308 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
312 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
109 ms |
13752 KB |
Output is correct |
| 31 |
Correct |
104 ms |
13800 KB |
Output is correct |
| 32 |
Correct |
78 ms |
8896 KB |
Output is correct |
| 33 |
Correct |
91 ms |
27116 KB |
Output is correct |
| 34 |
Correct |
95 ms |
27108 KB |
Output is correct |
| 35 |
Correct |
105 ms |
27244 KB |
Output is correct |
| 36 |
Correct |
109 ms |
26840 KB |
Output is correct |
| 37 |
Correct |
89 ms |
25828 KB |
Output is correct |
| 38 |
Correct |
87 ms |
22320 KB |
Output is correct |
| 39 |
Correct |
96 ms |
21272 KB |
Output is correct |
| 40 |
Correct |
86 ms |
15824 KB |
Output is correct |
| 41 |
Correct |
95 ms |
13972 KB |
Output is correct |
| 42 |
Correct |
101 ms |
14316 KB |
Output is correct |
| 43 |
Correct |
106 ms |
27588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3594' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
308 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
308 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
308 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
312 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
109 ms |
13752 KB |
Output is correct |
| 31 |
Correct |
104 ms |
13800 KB |
Output is correct |
| 32 |
Correct |
78 ms |
8896 KB |
Output is correct |
| 33 |
Correct |
91 ms |
27116 KB |
Output is correct |
| 34 |
Correct |
95 ms |
27108 KB |
Output is correct |
| 35 |
Correct |
105 ms |
27244 KB |
Output is correct |
| 36 |
Correct |
109 ms |
26840 KB |
Output is correct |
| 37 |
Correct |
89 ms |
25828 KB |
Output is correct |
| 38 |
Correct |
87 ms |
22320 KB |
Output is correct |
| 39 |
Correct |
96 ms |
21272 KB |
Output is correct |
| 40 |
Correct |
86 ms |
15824 KB |
Output is correct |
| 41 |
Correct |
95 ms |
13972 KB |
Output is correct |
| 42 |
Correct |
101 ms |
14316 KB |
Output is correct |
| 43 |
Correct |
106 ms |
27588 KB |
Output is correct |
| 44 |
Incorrect |
1 ms |
340 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3594' |
| 45 |
Halted |
0 ms |
0 KB |
- |
