#include "books.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
#define fi first
#define se second
using ll = long long;
struct segment_tree {
#define il i * 2
#define ir i * 2 + 1
vector <int> val;
int n, x, y, res;
void build(int i, int l, int r,
const vector <int> &idx) {
if (l == r) val[i] = idx[l];
else {
int m = (l + r) / 2;
build(il, l, m, idx);
build(ir, m + 1, r, idx);
val[i] = max(val[il], val[ir]);
}
}
void init(const vector <int> &idx) {
n = idx.size();
val.resize(n * 4);
build(1, 0, n - 1, idx);
}
void init(int n) {
this->n = n;
val.assign(n * 4, -1e9);
}
void rep(int i, int l, int r, int v) {
if (l == r) val[i] = v;
else {
int m = (l + r) / 2;
if (m >= x) rep(il, l, m, v);
else rep(ir, m + 1, r, v);
val[i] = max(val[il], val[ir]);
}
}
void get(int i, int l, int r) {
if (l >= x && r <= y) {
res = max(res, val[i]);
return;
}
int m = (l + r) / 2;
if (m >= x) get(il, l, m);
if (m < y) get(ir, m + 1, r);
}
void rep(int p, int v) {
x = p; rep(1, 0, n - 1, v);
}
int get(int l, int r) {
x = l; y = r; res = -1e9;
get(1, 0, n - 1); return res;
}
};
vector <int> lef, rig, scc;
vector <vector <int>> own, cmp;
segment_tree seg1, seg2;
int timer = 0;
stack <int> stk;
vector <int> num, low;
void tarjan(int u) {
low[u] = num[u] = ++timer;
for (int i : own[u]) {
seg1.rep(i, -1);
seg2.rep(i, -low[u]);
}
stk.push(u);
int v = seg1.get(lef[u], rig[u]);
while (~v) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
low[u] = min(low[u], -seg2.get(lef[u], rig[u]));
if (num[u] == low[u]) {
cmp.emplace_back();
do {
v = stk.top(); stk.pop();
cmp.back().push_back(v);
scc[v] = cmp.size() - 1;
num[v] = low[v] = 1e9;
scc[v] = timer;
} while (v != u);
}
}
}
ll minimum_walk(vector<int> p, int s) {
int cnt = 0, n = p.size();
vector <int> idx(n, -1);
for (int i = 0; i < n; i++) {
if (~idx[i]) continue;
int u = i;
lef.push_back(i);
rig.push_back(i);
own.emplace_back();
while (idx[u] < 0) {
own[cnt].push_back(u);
lef[cnt] = min(lef[cnt], u);
rig[cnt] = max(rig[cnt], u);
idx[u] = cnt; u = p[u];
}
cnt++;
}
scc.resize(cnt);
num.resize(cnt); low.resize(cnt);
seg1.init(idx); seg2.init(n);
for (int i = 0; i < cnt; i++)
if (!num[i]) tarjan(i);
reverse(cmp.begin(), cmp.end());
num.assign(cmp.size(), 0);
vector <pair <int, int>> tmp;
int mi = s, ma = s;
seg1.init(idx); seg2.init(n);
for (int i = 0; i < cmp.size(); i++) {
if (!num[i]) {
int l = -1, r = n;
for (int j : cmp[i])
for (int k : own[j]) {
if (k < s) l = max(l, k);
if (k > s) r = min(r, k);
seg1.rep(k, -1);
}
if (l >= 0 && r < n) {
tmp.emplace_back(l, r);
seg2.rep(r, r);
} else if (l >= 0) mi = min(mi, l);
else if (r < n) ma = max(ma, r);
}
for (int j : cmp[i])
for (int k : own[j])
seg1.rep(k, -1);
for (int j : cmp[i]) {
int k = seg1.get(lef[j], rig[j]);
while (k >= 0) {
num[scc[k]] = true;
for (int l : own[k])
seg1.rep(l, -1);
}
}
}
sort(tmp.rbegin(), tmp.rend());
long long res = 2ll * (max(ma, seg2.val[1]) - mi);
for (auto &p : tmp) {
seg2.rep(p.se, -1);
res = min(res, 2ll * (max(ma, seg2.val[1]) - min(mi, p.fi)));
}
for (int i = 0; i < n; i++)
res += abs(i - p[i]);
return res;
return 0;
}
Compilation message
books.cpp: In function '{anonymous}::ll minimum_walk(std::vector<int>, int)':
books.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i = 0; i < cmp.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Execution timed out |
2106 ms |
812736 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Execution timed out |
2106 ms |
812736 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Execution timed out |
2106 ms |
812736 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2109 ms |
556868 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Execution timed out |
2106 ms |
812736 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
