#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];
vector<int> cont[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);
if (cont[i].size() < cont[j].size()) swap(i, j);
for (int v: cont[j]) {
cont[i].push_back(v);
uf[v] = i;
}
cont[j].clear();
uf[j] = i;
// range[i].first = min(range[i].first, range[j].first);
// range[i].second = max(range[i].second, range[j].second);
}
void upd(int cur, queue<int> &q) {
int cdist = 1+dist[find(cur)];
if (cur && dist[find(cur-1)] > cdist) {
assert(dist[find(cur-1)] == MAXN);
dist[find(cur-1)] = cdist;
q.push(find(cur-1));
}
if (cur < n-1 && dist[find(cur+1)] > cdist) {
assert(dist[find(cur+1)] == MAXN);
dist[find(cur+1)] = cdist;
q.push(find(cur+1));
}
}
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;
cont[i].push_back(cur);
vis[cur] = 1;
cur = p[cur];
} while (cur != i);
if (l == r && i == s) intervals.push_back(pii(l, r));
sort(cont[i].begin(), cont[i].end());
if (r > l) {
for (int j = 0; j < cont[i].size()-1; j++) intervals.push_back(pii(cont[i][j], cont[i][j+1]));
}
// 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()) dist[find(v)] = 0;
// 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]);
dist[find(stck[0])] = 0;
queue<int> q;
for (int i = 0; i < n; i++) {
if (dist[i] == 0) dist[find(i)] = 0;
}
for (int i = 0; i < n; i++) {
if (i == find(i) && dist[i] == 0) q.push(i);
}
while (!q.empty()) {
int v = q.front(); q.pop();
for (int e: cont[v]) upd(e, q);
}
// 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[find(s)];
}
Compilation message
books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int j = 0; j < cont[i].size()-1; j++) intervals.push_back(pii(cont[i][j], cont[i][j+1]));
| ~~^~~~~~~~~~~~~~~~~~
books.cpp:88: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]
88 | for (int i = 0; i < intervals.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
48044 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
48044 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
48044 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
48112 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
48044 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
