#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "books.h"
template<int BASE, typename COMP>
struct SEGTREE {
int n;
VPI tree;
COMP COMPOBJ;
SEGTREE(int sz) {
n = 1;
while (n < sz) n *= 2;
tree = VPI(2*n, {BASE, -1});
}
PII lav(PII a, PII b) {
if (COMPOBJ(a, b)) return a;
return b;
}
void upd(int N, int L, int R, int i, PII s) {
if (i < L || i > R) return;
if (L == R) {
tree[N] = s;
return;
}
int M = (L + R) / 2;
upd(2*N+1, L, M, i, s);
upd(2*N+2, M+1, R, i, s);
tree[N] = lav(tree[2*N+1], tree[2*N+2]);
}
PII get(int N, int L, int R, int l, int r) {
if (l <= L && R <= r) return tree[N];
if (R < l || L > r) return {BASE, -1};
int M = (L + R) / 2;
return lav(get(2*N+1, L, M, l, r), get(2*N+2, M+1, R, l, r));
}
void upd(int i, PII s) {
upd(0, 0, n-1, i, s);
}
PII get(int l, int r) {
if (l > r) return {BASE, -1};
return get(0, 0, n-1, l, r);
}
};
namespace TEST5 {
int s;
VI p;
VI vis, group;
ll ans;
map<PII, VI> comps;
PII getcomp(int s) {
PII ret{s, s};
int u = s;
VI vec;
do {
vec.pb(u);
vis[u] = true;
setmin(ret.ff, u);
setmax(ret.ss, u);
ans += abs(p[u]-u);
u = p[u];
} while (u != s);
for (int u : vec) comps[ret].pb(u);
return ret;
}
PII skizbp;
void compressranges(VPI& ranges) {
int n = ranges.size();
VI vis(n);
function<void(int)> dfs;
VI comp;
SEGTREE<(int)-2e9, greater<PII>> mxval(2*p.size()+30);
SEGTREE<(int)+2e9, less<PII>> mnval(2*p.size()+30);
rep(i, n) {
auto[l, r] = ranges[i];
mxval.upd(l, {r, i});
/*cout << "AT " << l << " SAT {" << r << ", " << i << "}" << endl;*/
mnval.upd(r, {l, i});
}
/*cout << "NOW PRINTING THE GRAPH" << endl;*/
VVI gp(n);
rep(u, n) {
auto[l, r] = ranges[u];
PII p1 = mxval.get(l+1, r-1);
if (p1.ff > r) {
gp[u].pb(p1.ss);
gp[p1.ss].pb(u);
}
PII p2 = mnval.get(l+1, r-1);
if (p2.ff < l) {
gp[u].pb(p2.ss);
gp[p2.ss].pb(u);
}
}
/*cout << "ENDED" << endl;*/
dfs = [&](int u) {
comp.pb(u);
vis[u] = true;
VI harevan;
for (int v : gp[u]) if (!vis[v]) {
dfs(v);
}
};
if (true) {
VPI tmp;
rep(u, n) if (!vis[u]) {
comp.clear();
dfs(u);
PII ret = {+2e9, -2e9};
for (int u : comp) {
setmin(ret.ff, ranges[u].ff);
setmax(ret.ss, ranges[u].ss);
}
VI vec;
for (int u : comp) {
for (int x : comps[ranges[u]]) {
vec.pb(x);
}
}
comps[ret].clear();
for (int x : vec) comps[ret].pb(x);
if (u == 0) skizbp = ret;
tmp.pb(ret);
}
ranges = tmp;
}
sort(all(ranges));
PII glxavor = {s, s};
int cur = -1;
VPI roots;
while (true) {
auto it = upper_bound(all(ranges), PII{cur, +2e9});
if (it == ranges.end()) break;
roots.pb(*it);
if (it->ff <= s && s <= it->ss) {
glxavor = *it;
}
cur = it->ss;
}
replr(i, 1, roots.size()-1) {
ans += (roots[i].ff - roots[i-1].ss)*2;
}
VPI tmp{glxavor};
for (PII p : ranges) {
if (glxavor.ff < p.ff && p.ss < glxavor.ss) {
tmp.pb(p);
}
}
ranges = tmp;
}
ll solve(VI PARG, int SARG) {p = PARG, s = SARG;
VPI ranges;
vis = VI(p.size());
group = VI(p.size(), -1);
ranges.pb(getcomp(s));
rep(u, p.size()) if (u != p[u] && !vis[u]) ranges.pb(getcomp(u));
/*int q;*/
/*cin >> q;*/
/*while (q--) {*/
/* int l, r;*/
/* cin >> l >> r;*/
/* ranges.pb({l, r});*/
/*}*/
compressranges(ranges);
sort(all(ranges), [&](PII a, PII b){
swap(a.ff, a.ss);
swap(b.ff, b.ss);
return a < b;
});
int n = ranges.size();
VPI points;
rep(i, n) {
for (int x : comps[ranges[i]]) {
points.pb({x, i});
}
}
sort(all(points));
VVPI gp(n);
rep(u, n) {
auto[l, r] = ranges[u];
VPI::iterator(it);
it = upper_bound(all(points), PII{r, +2e9});
if (it != points.end()) {
gp[u].pb({it->ss, (it->ff-r)*2});
}
it = lower_bound(all(points), PII{l, -2e9});
if (it != points.begin()) {it--;
gp[u].pb({it->ss, (l-it->ff)*2});
}
}
int start = -1;
rep(i, n) if (ranges[i] == skizbp) start = i;
priority_queue<PLL> pq;
VL dist(n, 1e18);
VI vis(n);
pq.push({0, start});
dist[start] = 0;
while (pq.size()) {
int u = pq.top().ss;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto[v, w] : gp[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
}
return ans + dist.back();
}
}
namespace TEST4 {
int s;
VI p;
VI vis, group;
ll ans;
map<PII, VI> comps;
PII getcomp(int s) {
PII ret{s, s};
int u = s;
VI vec;
do {
vec.pb(u);
vis[u] = true;
setmin(ret.ff, u);
setmax(ret.ss, u);
ans += abs(p[u]-u);
u = p[u];
} while (u != s);
for (int u : vec) comps[ret].pb(u);
return ret;
}
PII skizbp;
void compressranges(VPI& ranges) {
int n = ranges.size();
VI vis(n);
function<void(int)> dfs;
VI comp;
dfs = [&](int u) {
comp.pb(u);
vis[u] = true;
rep(v, n) if (!vis[v]) {
if (ranges[v].ss < ranges[u].ff || ranges[v].ff > ranges[u].ss) continue;
if (ranges[u].ff < ranges[v].ff && ranges[v].ss < ranges[u].ss) continue;
if (ranges[v].ff < ranges[u].ff && ranges[u].ss < ranges[v].ss) continue;
dfs(v);
}
};
if (true) {
VPI tmp;
rep(u, n) if (!vis[u]) {
comp.clear();
dfs(u);
PII ret = {+2e9, -2e9};
for (int u : comp) {
setmin(ret.ff, ranges[u].ff);
setmax(ret.ss, ranges[u].ss);
}
VI vec;
for (int u : comp) {
for (int x : comps[ranges[u]]) {
vec.pb(x);
}
}
comps[ret].clear();
for (int x : vec) comps[ret].pb(x);
if (u == 0) skizbp = ret;
tmp.pb(ret);
}
ranges = tmp;
}
sort(all(ranges));
PII glxavor = {s, s};
int cur = -1;
VPI roots;
while (true) {
auto it = upper_bound(all(ranges), PII{cur, +2e9});
if (it == ranges.end()) break;
roots.pb(*it);
if (it->ff <= s && s <= it->ss) {
glxavor = *it;
}
cur = it->ss;
}
replr(i, 1, roots.size()-1) {
ans += (roots[i].ff - roots[i-1].ss)*2;
}
VPI tmp{glxavor};
for (PII p : ranges) {
if (glxavor.ff < p.ff && p.ss < glxavor.ss) {
tmp.pb(p);
}
}
ranges = tmp;
}
ll solve(VI PARG, int SARG) {p = PARG, s = SARG;
VPI ranges;
vis = VI(p.size());
group = VI(p.size(), -1);
ranges.pb(getcomp(s));
rep(u, p.size()) if (u != p[u] && !vis[u]) ranges.pb(getcomp(u));
compressranges(ranges);
sort(all(ranges), [&](PII a, PII b){
swap(a.ff, a.ss);
swap(b.ff, b.ss);
return a < b;
});
int n = ranges.size();
VPI points;
rep(i, n) {
for (int x : comps[ranges[i]]) {
points.pb({x, i});
}
}
sort(all(points));
VVPI gp(n);
rep(u, n) {
auto[l, r] = ranges[u];
VPI::iterator(it);
it = upper_bound(all(points), PII{r, +2e9});
if (it != points.end()) {
gp[u].pb({it->ss, (it->ff-r)*2});
}
it = lower_bound(all(points), PII{l, -2e9});
if (it != points.begin()) {it--;
gp[u].pb({it->ss, (l-it->ff)*2});
}
}
int start = -1;
rep(i, n) if (ranges[i] == skizbp) start = i;
priority_queue<PLL> pq;
VL dist(n, 1e18);
VI vis(n);
pq.push({0, start});
dist[start] = 0;
while (pq.size()) {
int u = pq.top().ss;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto[v, w] : gp[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
}
return ans + dist.back();
}
}
ll minimum_walk(VI p, int s) {
return TEST5::solve(p, s);
}
Compilation message
books.cpp: In function 'void TEST5::compressranges(VPI&)':
books.cpp:104:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
104 | auto[l, r] = ranges[i];
| ^
books.cpp:112:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
112 | auto[l, r] = ranges[u];
| ^
books.cpp: In function 'll TEST5::solve(VI, int)':
books.cpp:210:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
210 | auto[l, r] = ranges[u];
| ^
books.cpp:211:26: warning: unnecessary parentheses in declaration of 'it' [-Wparentheses]
211 | VPI::iterator(it);
| ^
books.cpp:235:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
235 | for (auto[v, w] : gp[u]) {
| ^
books.cpp: In function 'll TEST4::solve(VI, int)':
books.cpp:354:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
354 | auto[l, r] = ranges[u];
| ^
books.cpp:355:26: warning: unnecessary parentheses in declaration of 'it' [-Wparentheses]
355 | VPI::iterator(it);
| ^
books.cpp:379:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
379 | for (auto[v, w] : gp[u]) {
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
436 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
436 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
564 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
344 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
436 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
564 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
344 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
360 KB |
Output is correct |
30 |
Correct |
252 ms |
112452 KB |
Output is correct |
31 |
Correct |
226 ms |
110936 KB |
Output is correct |
32 |
Correct |
99 ms |
96224 KB |
Output is correct |
33 |
Correct |
304 ms |
129100 KB |
Output is correct |
34 |
Correct |
351 ms |
129044 KB |
Output is correct |
35 |
Correct |
348 ms |
134708 KB |
Output is correct |
36 |
Correct |
371 ms |
129476 KB |
Output is correct |
37 |
Correct |
187 ms |
109548 KB |
Output is correct |
38 |
Correct |
150 ms |
105812 KB |
Output is correct |
39 |
Correct |
156 ms |
106012 KB |
Output is correct |
40 |
Correct |
138 ms |
104608 KB |
Output is correct |
41 |
Correct |
159 ms |
106088 KB |
Output is correct |
42 |
Correct |
138 ms |
105416 KB |
Output is correct |
43 |
Correct |
541 ms |
136124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
600 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
440 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
436 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
564 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
344 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
360 KB |
Output is correct |
30 |
Correct |
252 ms |
112452 KB |
Output is correct |
31 |
Correct |
226 ms |
110936 KB |
Output is correct |
32 |
Correct |
99 ms |
96224 KB |
Output is correct |
33 |
Correct |
304 ms |
129100 KB |
Output is correct |
34 |
Correct |
351 ms |
129044 KB |
Output is correct |
35 |
Correct |
348 ms |
134708 KB |
Output is correct |
36 |
Correct |
371 ms |
129476 KB |
Output is correct |
37 |
Correct |
187 ms |
109548 KB |
Output is correct |
38 |
Correct |
150 ms |
105812 KB |
Output is correct |
39 |
Correct |
156 ms |
106012 KB |
Output is correct |
40 |
Correct |
138 ms |
104608 KB |
Output is correct |
41 |
Correct |
159 ms |
106088 KB |
Output is correct |
42 |
Correct |
138 ms |
105416 KB |
Output is correct |
43 |
Correct |
541 ms |
136124 KB |
Output is correct |
44 |
Correct |
1 ms |
348 KB |
Output is correct |
45 |
Correct |
0 ms |
348 KB |
Output is correct |
46 |
Correct |
1 ms |
348 KB |
Output is correct |
47 |
Correct |
0 ms |
348 KB |
Output is correct |
48 |
Correct |
1 ms |
348 KB |
Output is correct |
49 |
Correct |
1 ms |
348 KB |
Output is correct |
50 |
Correct |
1 ms |
348 KB |
Output is correct |
51 |
Correct |
1 ms |
348 KB |
Output is correct |
52 |
Correct |
1 ms |
348 KB |
Output is correct |
53 |
Correct |
1 ms |
344 KB |
Output is correct |
54 |
Correct |
1 ms |
600 KB |
Output is correct |
55 |
Correct |
1 ms |
348 KB |
Output is correct |
56 |
Correct |
1 ms |
348 KB |
Output is correct |
57 |
Correct |
1 ms |
348 KB |
Output is correct |
58 |
Correct |
1 ms |
348 KB |
Output is correct |
59 |
Correct |
1 ms |
440 KB |
Output is correct |
60 |
Correct |
1 ms |
348 KB |
Output is correct |
61 |
Correct |
1 ms |
348 KB |
Output is correct |
62 |
Correct |
1 ms |
348 KB |
Output is correct |
63 |
Correct |
0 ms |
348 KB |
Output is correct |
64 |
Incorrect |
285 ms |
116392 KB |
3rd lines differ - on the 1st token, expected: '9339550', found: '9339552' |
65 |
Halted |
0 ms |
0 KB |
- |