#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct DisjointSet {
int n;
vector<int> parent, rank;
DisjointSet(int _n) : n(_n) {
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
rank.resize(n, 0);
}
int find(int u) {
return parent[u] = (u == parent[u] ? u : find(parent[u]));
}
void merge(int u, int v) {
u = find(u); v = find(v);
if (u == v) return;
if (rank[u] > rank[v]) swap(u, v);
parent[u] = v;
if (rank[u] == rank[v]) ++rank[v];
}
};
struct FenwickTree {
vector<int> tree;
FenwickTree(int size) {
tree.resize(size+1, 0);
}
int sum(int pos) {
int ret = 0;
for (int i=pos+1; i>0; i &= (i-1)) ret += tree[i];
return ret;
}
void add(int pos, int val) {
for (int i=pos+1; i<tree.size(); i+=(i & -i)) tree[i] += val;
}
};
const int MAX_N = 1e6 + 1;
const ll INF = 4e18;
DisjointSet dsu(MAX_N);
FenwickTree fen(MAX_N);
bool visited[MAX_N];
vector<int> cycle[MAX_N];
vector<int> adj[MAX_N];
ll dp[MAX_N];
void dfs(int here, int parent = -1) {
bool merged = false;
if (parent != -1) {
int mn = *min_element(cycle[here].begin(), cycle[here].end());
int mx = *max_element(cycle[here].begin(), cycle[here].end());
if (fen.sum(mx) - fen.sum(mn) > 0) {
dsu.merge(here, parent);
for (int x: cycle[here]) fen.add(x, 1);
if (cycle[here].size() > cycle[parent].size()) swap(cycle[here], cycle[parent]);
for (int x: cycle[here]) cycle[parent].push_back(x);
merged = true;
}
}
if (!merged) {
for (int x: cycle[here]) fen.add(x, 1);
}
for (int there: adj[here]) {
dfs(there, here);
}
if (!merged) {
for (int x: cycle[dsu.find(here)]) fen.add(x, -1);
}
}
ll minimum_walk(vector<int> p, int s) {
int n = p.size();
vector<pii> range;
ll jump_len = 0;
for (int i=0; i<n; ++i) {
if (!visited[i]) {
int l = i, r = i;
jump_len += abs(i-p[i]);
visited[i] = true;
int x = p[i];
while (x != i) {
l = min(l, x);
r = max(r, x);
jump_len += abs(x-p[x]);
visited[x] = true;
dsu.merge(x, i);
x = p[x];
}
range.push_back({ l+1, i });
range.push_back({ -r-1, i });
}
}
sort(range.begin(), range.end(), [](const pii& a, const pii& b) {
return abs(a.first) < abs(b.first);
});
vector<pii> st;
for (auto[x, idx]: range) {
// cout << x << ' ' << idx << endl;
if (x >= 0) {
st.push_back({ idx, 1 });
} else {
int remove_cnt = 0;
while (dsu.find(st.back().first) != dsu.find(idx)) {
dsu.merge(st.back().first, idx);
remove_cnt++;
}
assert(!st.empty() && dsu.find(st.back().first) == dsu.find(idx));
st.back().second += remove_cnt-1;
if (st.back().second <= 0) st.pop_back();
}
}
vector<pair<pii, int>> dfs_order;
for (int i=0; i<n; ++i) cycle[dsu.find(i)].push_back(i);
for (int i=0; i<n; ++i) {
if (dsu.find(i) == i) {
dfs_order.push_back({ { cycle[i][0], cycle[i].back() }, i });
}
}
sort(dfs_order.begin(), dfs_order.end());
st.clear();
vector<int> roots;
for (int i=0; i<dfs_order.size(); ++i) {
while (!st.empty() && st.back().first < dfs_order[i].first.first) {
st.pop_back();
}
if (!st.empty()) {
adj[st.back().second].push_back(dfs_order[i].second);
// cout << st.back().second << ' ' << dfs_order[i].second << endl;
}
if (st.empty()) roots.push_back(dfs_order[i].second);
st.push_back({ dfs_order[i].first.second, dfs_order[i].second });
}
for (int r: roots) dfs(r);
ll accum = s;
// for (int i=0; i<n; ++i) {
// if (dsu.find(i) == i && cycle[i].size() >= 2) {
// ll l = INF, r = INF;
// for (int x: cycle[i]) {
// if (x <= s) l = min(l, (ll)s-x);
// if (x >= s) r = min(r, (ll)x-s);
// }
// cout << i << ' ' << l << ' ' << r << endl;
// if (l > INF/2) accum = max(accum, s+r);
// else dp[s-l] = s+r;
// }
// }
for (int root: roots) {
ll l = INF, r = INF;
for (int x: cycle[root]) {
if (x <= s) l = min(l, (ll)s-x);
if (x >= s) r = min(r, (ll)x-s);
}
// cout << root << ' ' << l << ' ' << r << endl;
if (l > INF/2) accum = max(accum, s+r);
else dp[s-l] = s+r;
}
ll ans = INF;
for (int i=0; i<=s; ++i) {
// cout << i << ' ' << accum << endl;
ans = min(ans, accum-i);
accum = max(accum, dp[i]);
}
// cout << jump_len << endl;
return jump_len + 2 * ans;
}
Compilation message
books.cpp: In member function 'void FenwickTree::add(int, int)':
books.cpp:42:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i=pos+1; i<tree.size(); i+=(i & -i)) tree[i] += val;
| ~^~~~~~~~~~~~
books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for (int i=0; i<dfs_order.size(); ++i) {
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
58964 KB |
Output is correct |
| 2 |
Correct |
32 ms |
58984 KB |
Output is correct |
| 3 |
Correct |
28 ms |
58980 KB |
Output is correct |
| 4 |
Correct |
28 ms |
58988 KB |
Output is correct |
| 5 |
Incorrect |
28 ms |
58964 KB |
3rd lines differ - on the 1st token, expected: '4', found: '10' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
58964 KB |
Output is correct |
| 2 |
Correct |
32 ms |
58984 KB |
Output is correct |
| 3 |
Correct |
28 ms |
58980 KB |
Output is correct |
| 4 |
Correct |
28 ms |
58988 KB |
Output is correct |
| 5 |
Incorrect |
28 ms |
58964 KB |
3rd lines differ - on the 1st token, expected: '4', found: '10' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
58964 KB |
Output is correct |
| 2 |
Correct |
32 ms |
58984 KB |
Output is correct |
| 3 |
Correct |
28 ms |
58980 KB |
Output is correct |
| 4 |
Correct |
28 ms |
58988 KB |
Output is correct |
| 5 |
Incorrect |
28 ms |
58964 KB |
3rd lines differ - on the 1st token, expected: '4', found: '10' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
59212 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3574' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
58964 KB |
Output is correct |
| 2 |
Correct |
32 ms |
58984 KB |
Output is correct |
| 3 |
Correct |
28 ms |
58980 KB |
Output is correct |
| 4 |
Correct |
28 ms |
58988 KB |
Output is correct |
| 5 |
Incorrect |
28 ms |
58964 KB |
3rd lines differ - on the 1st token, expected: '4', found: '10' |
| 6 |
Halted |
0 ms |
0 KB |
- |
