#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const int INF=INT_MAX>>1;
struct SegTree{
using T=pair<int,int>;
inline T op(T x,T y){
return {min(x.first,y.first),max(x.second,y.second)};
}
inline T e(){
return {INF,-INF};
}
vector<T> tree;
int size;
SegTree(int sz):size(sz){
tree.resize(size*2,e());
}
inline T get(int pos){
return tree[pos+size];
}
inline void set(int pos,T val){
pos+=size;
tree[pos]=val;
pos>>=1;
while(pos>=1){
tree[pos]=op(tree[pos*2],tree[pos*2+1]);
pos>>=1;
}
}
T prod(int lf,int ri){
lf+=size;
ri+=size;
T rl=e();
T rr=e();
while(lf<ri){
if(lf&1){
rl=op(rl,tree[lf]);
lf++;
}
if(ri&1){
ri--;
rr=op(tree[ri],rr);
}
lf>>=1;
ri>>=1;
}
return op(rl,rr);
}
};
long long minimum_walk(std::vector<int> p, int s) {
int n=p.size();
vector<int> vis(n,-1);
vector<pair<int,int>> wide;
int cnt=0;
ll ans=0;
rep(i,n){
if(vis[i]>=0)continue;
if(p[i]==i&&i!=s)continue;
int lf=i;
int ri=i;
int pos=i;
while(vis[p[pos]]==-1){
ans+=abs(pos-p[pos]);
pos=p[pos];
vis[pos]=cnt;
lf=min(lf,pos);
ri=max(ri,pos);
}
cnt++;
wide.emplace_back(lf,ri);
}
int sl,sr;
{
vector<pair<int,int>> seg=wide;
sort(all(seg));
vector<pair<int,int>> re={seg[0]};
rng(i,1,seg.size()){
if(seg[i].first<=re.back().second){
re.back().second=max(re.back().second,seg[i].second);
}
else{
re.emplace_back(seg[i]);
}
}
rep(i,re.size()-1){
ans+=2*(re[i+1].first-re[i].second);
}
for(auto i:re){
if(i.first<=s&&s<=i.second){
sl=i.first;
sr=i.second;
break;
}
}
}
vector<int> dist(cnt,INF);
dist[vis[s]]=0;
SegTree seg(n);
rng(i,sl,sr+1){
if(vis[i]!=-1){
seg.set(i,{i,i});
}
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({0,vis[s]});
while(!pq.empty()){
int dis,pos;
tie(dis,pos)=pq.top();
pq.pop();
if(dist[pos]!=dis)continue;
int lf,ri;
tie(lf,ri)=wide[pos];
while(true){
int nxt=seg.prod(lf+1,ri).first;
if(nxt>n)break;
seg.set(nxt,seg.e());
if(dist[vis[nxt]]>dis){
dist[vis[nxt]]=dis;
pq.push({dist[vis[nxt]],vis[nxt]});
}
}
int nxt;
nxt=seg.prod(0,lf).second;
if(0<=nxt){
if(dist[vis[nxt]]>dis+abs(nxt-lf)){
dist[vis[nxt]]=dis+abs(nxt-lf);
pq.push({dist[vis[nxt]],vis[nxt]});
}
}
nxt=seg.prod(ri+1,n).first;
if(nxt<n){
if(dist[vis[nxt]]>dis+abs(nxt-ri)){
dist[vis[nxt]]=dis+abs(nxt-ri);
pq.push({dist[vis[nxt]],vis[nxt]});
}
}
}
rep(i,cnt){
if(wide[i].first==sl){
ans+=dist[i]*2;
break;
}
}
return ans;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define rng(i,l,r) for(int i=(l); i<(r); i++)
| ^
books.cpp:85:3: note: in expansion of macro 'rng'
85 | rng(i,1,seg.size()){
| ^~~
books.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define rep(i,n) for(int i=0; i<(n); i++)
| ^
books.cpp:93:3: note: in expansion of macro 'rep'
93 | rep(i,re.size()-1){
| ^~~
books.cpp:5:36: warning: 'sr' may be used uninitialized in this function [-Wmaybe-uninitialized]
5 | #define rng(i,l,r) for(int i=(l); i<(r); i++)
| ^
books.cpp:80:9: note: 'sr' was declared here
80 | int sl,sr;
| ^~
books.cpp:80:6: warning: 'sl' may be used uninitialized in this function [-Wmaybe-uninitialized]
80 | int sl,sr;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
436 KB |
Output is correct |
3 |
Correct |
0 ms |
348 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 |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 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 |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 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 |
432 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
436 KB |
Output is correct |
3 |
Correct |
0 ms |
348 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 |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 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 |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 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 |
432 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 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 |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
384 KB |
Output is correct |
26 |
Correct |
0 ms |
604 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
436 KB |
Output is correct |
3 |
Correct |
0 ms |
348 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 |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 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 |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 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 |
432 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 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 |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
384 KB |
Output is correct |
26 |
Correct |
0 ms |
604 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
432 KB |
Output is correct |
30 |
Correct |
240 ms |
34388 KB |
Output is correct |
31 |
Correct |
238 ms |
34544 KB |
Output is correct |
32 |
Correct |
77 ms |
34412 KB |
Output is correct |
33 |
Correct |
85 ms |
36816 KB |
Output is correct |
34 |
Correct |
97 ms |
36732 KB |
Output is correct |
35 |
Correct |
88 ms |
36892 KB |
Output is correct |
36 |
Correct |
87 ms |
36308 KB |
Output is correct |
37 |
Correct |
78 ms |
34824 KB |
Output is correct |
38 |
Correct |
79 ms |
34660 KB |
Output is correct |
39 |
Correct |
82 ms |
34544 KB |
Output is correct |
40 |
Correct |
83 ms |
34548 KB |
Output is correct |
41 |
Correct |
127 ms |
34392 KB |
Output is correct |
42 |
Correct |
90 ms |
34388 KB |
Output is correct |
43 |
Correct |
220 ms |
41396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 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 |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
436 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
436 KB |
Output is correct |
3 |
Correct |
0 ms |
348 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 |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 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 |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 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 |
432 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 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 |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
384 KB |
Output is correct |
26 |
Correct |
0 ms |
604 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
432 KB |
Output is correct |
30 |
Correct |
240 ms |
34388 KB |
Output is correct |
31 |
Correct |
238 ms |
34544 KB |
Output is correct |
32 |
Correct |
77 ms |
34412 KB |
Output is correct |
33 |
Correct |
85 ms |
36816 KB |
Output is correct |
34 |
Correct |
97 ms |
36732 KB |
Output is correct |
35 |
Correct |
88 ms |
36892 KB |
Output is correct |
36 |
Correct |
87 ms |
36308 KB |
Output is correct |
37 |
Correct |
78 ms |
34824 KB |
Output is correct |
38 |
Correct |
79 ms |
34660 KB |
Output is correct |
39 |
Correct |
82 ms |
34544 KB |
Output is correct |
40 |
Correct |
83 ms |
34548 KB |
Output is correct |
41 |
Correct |
127 ms |
34392 KB |
Output is correct |
42 |
Correct |
90 ms |
34388 KB |
Output is correct |
43 |
Correct |
220 ms |
41396 KB |
Output is correct |
44 |
Correct |
1 ms |
344 KB |
Output is correct |
45 |
Correct |
0 ms |
348 KB |
Output is correct |
46 |
Correct |
0 ms |
348 KB |
Output is correct |
47 |
Correct |
0 ms |
344 KB |
Output is correct |
48 |
Correct |
0 ms |
348 KB |
Output is correct |
49 |
Correct |
0 ms |
344 KB |
Output is correct |
50 |
Correct |
0 ms |
348 KB |
Output is correct |
51 |
Correct |
1 ms |
348 KB |
Output is correct |
52 |
Correct |
0 ms |
348 KB |
Output is correct |
53 |
Correct |
0 ms |
348 KB |
Output is correct |
54 |
Correct |
1 ms |
348 KB |
Output is correct |
55 |
Correct |
0 ms |
348 KB |
Output is correct |
56 |
Correct |
1 ms |
348 KB |
Output is correct |
57 |
Correct |
0 ms |
348 KB |
Output is correct |
58 |
Correct |
1 ms |
344 KB |
Output is correct |
59 |
Correct |
0 ms |
436 KB |
Output is correct |
60 |
Correct |
0 ms |
348 KB |
Output is correct |
61 |
Correct |
0 ms |
348 KB |
Output is correct |
62 |
Correct |
1 ms |
348 KB |
Output is correct |
63 |
Correct |
1 ms |
344 KB |
Output is correct |
64 |
Correct |
156 ms |
37384 KB |
Output is correct |
65 |
Correct |
143 ms |
37320 KB |
Output is correct |
66 |
Correct |
208 ms |
34848 KB |
Output is correct |
67 |
Correct |
206 ms |
34640 KB |
Output is correct |
68 |
Correct |
20 ms |
4032 KB |
Output is correct |
69 |
Correct |
21 ms |
3676 KB |
Output is correct |
70 |
Correct |
18 ms |
4016 KB |
Output is correct |
71 |
Correct |
16 ms |
3932 KB |
Output is correct |
72 |
Correct |
12 ms |
3928 KB |
Output is correct |
73 |
Correct |
20 ms |
3676 KB |
Output is correct |
74 |
Correct |
83 ms |
36592 KB |
Output is correct |
75 |
Correct |
82 ms |
36600 KB |
Output is correct |
76 |
Correct |
218 ms |
41284 KB |
Output is correct |
77 |
Correct |
204 ms |
41268 KB |
Output is correct |
78 |
Correct |
212 ms |
40572 KB |
Output is correct |
79 |
Correct |
216 ms |
40420 KB |
Output is correct |
80 |
Correct |
73 ms |
34400 KB |
Output is correct |
81 |
Correct |
307 ms |
41232 KB |
Output is correct |
82 |
Correct |
312 ms |
40816 KB |
Output is correct |
83 |
Correct |
221 ms |
37196 KB |
Output is correct |
84 |
Correct |
229 ms |
36976 KB |
Output is correct |
85 |
Correct |
212 ms |
35720 KB |
Output is correct |
86 |
Correct |
216 ms |
34928 KB |
Output is correct |
87 |
Correct |
166 ms |
36252 KB |
Output is correct |
88 |
Correct |
223 ms |
37960 KB |
Output is correct |
89 |
Correct |
244 ms |
37808 KB |
Output is correct |
90 |
Correct |
210 ms |
34652 KB |
Output is correct |
91 |
Correct |
213 ms |
34656 KB |
Output is correct |
92 |
Correct |
212 ms |
34404 KB |
Output is correct |