#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;
int dist = 0;
s = find(s);
while (par[s] != -1) {
dist += min(range[par[s]].second-range[s].second, range[s].first-range[par[s]].first);
s = find(par[s]);
}
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 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
