#include"books.h"
#include <vector>
#include<bits/stdc++.h>
const long long maxn=1000000+10;
using namespace std;
long long vis[maxn],visa[maxn],all[maxn],av[maxn],tr[maxn];
long long n;
long long mainres=0,last=0;
vector<pair<long long,pair<long long,long long>>>alle;
struct dsu{
long long par[maxn];
dsu(){
for(long long i=0;i<maxn;i++){
par[i]=i;
}
}
void clear(){
for(long long i=0;i<maxn;i++){
par[i]=i;
}
}
long long root(long long u){
if(u==par[u]){
return u;
}
return par[u]=root(par[u]);
}
long long con(long long u,long long v){
u=root(u);
v=root(v);
if(u==v){
return 0;
}
par[u]=v;
return 1;
}
}ds;
void solve(long long l,long long r,long long cl,long long cr){
//cout<<l<<" "<<r<<" "<<cl<<" "<<cr<<" "<<mainres<<"\n";
if(l!=cl){
l--;
cl=min(cl,av[l]);
cr=max(cr,tr[av[l]]);
return solve(l,r,cl,cr);
}
if(r!=cr){
r++;
cl=min(cl,av[r]);
cr=max(cr,tr[av[r]]);
return solve(l,r,cl,cr);
}
long long fl=0,fr=0,hl=l-1,hr=r+1,mxl=l,mxr=r;
for(;;hr++){
if(hr==n){
break;
}
if(hr==all[hr]){
continue;
}
if(hr>mxr){
fr+=(hr-mxr)*2;
}
mxr=max(mxr,tr[av[hr]]);
if(av[hr]<l){
break;
}
}
for(;hl>=0;hl--){
if(hl==all[hl]){
continue;
}
if(hl<mxl){
fl+=(mxl-hl)*2;
}
mxl=min(mxl,av[hl]);
if(tr[av[hl]]>r){
break;
}
}
if(hr==n){
mainres+=fr+fl;
return ;
}
if(fl<fr){
mainres+=fl;
return solve(l,r,mxl,cr);
}else{
mainres+=fr;
return solve(l,r,cl,mxr);
}
}
long long minimum_walk(std::vector<int> p,int s){
mainres=0;
n=p.size();
for(long long i=0;i<=n;i++){
vis[i]=visa[i]=0;
all[i]=p[i];
}
last=0;
long long cnt1=0;
for(long long i=0;i<n;i++){
if(p[i]>i){
cnt1++;
visa[p[i]]=1;
}
if(visa[i]){
cnt1--;
}
mainres+=cnt1*2;
if(cnt1!=0){
last=i+1;
}
}
for(long long i=0;i<n;i++){
if(i==p[i]){
av[i]=tr[i]=i;
continue;
}
if(vis[i]==0){
//mainres+=2;
long long now=i;
do{
av[now]=i;
vis[now]=1;
tr[i]=max(tr[i],now);
now=p[now];
}while(now!=i);
}
}
last=-1;
alle.clear();
solve(s,s,av[s],tr[av[s]]);
return mainres;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8280 KB |
Output is correct |
2 |
Correct |
3 ms |
8284 KB |
Output is correct |
3 |
Correct |
3 ms |
8280 KB |
Output is correct |
4 |
Correct |
3 ms |
8284 KB |
Output is correct |
5 |
Correct |
3 ms |
8284 KB |
Output is correct |
6 |
Correct |
3 ms |
8284 KB |
Output is correct |
7 |
Correct |
3 ms |
8284 KB |
Output is correct |
8 |
Correct |
3 ms |
8284 KB |
Output is correct |
9 |
Correct |
3 ms |
8272 KB |
Output is correct |
10 |
Correct |
3 ms |
8284 KB |
Output is correct |
11 |
Correct |
3 ms |
8284 KB |
Output is correct |
12 |
Correct |
3 ms |
8284 KB |
Output is correct |
13 |
Correct |
3 ms |
8272 KB |
Output is correct |
14 |
Correct |
3 ms |
8268 KB |
Output is correct |
15 |
Correct |
3 ms |
8284 KB |
Output is correct |
16 |
Correct |
3 ms |
8284 KB |
Output is correct |
17 |
Correct |
3 ms |
8284 KB |
Output is correct |
18 |
Correct |
3 ms |
8284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8280 KB |
Output is correct |
2 |
Correct |
3 ms |
8284 KB |
Output is correct |
3 |
Correct |
3 ms |
8280 KB |
Output is correct |
4 |
Correct |
3 ms |
8284 KB |
Output is correct |
5 |
Correct |
3 ms |
8284 KB |
Output is correct |
6 |
Correct |
3 ms |
8284 KB |
Output is correct |
7 |
Correct |
3 ms |
8284 KB |
Output is correct |
8 |
Correct |
3 ms |
8284 KB |
Output is correct |
9 |
Correct |
3 ms |
8272 KB |
Output is correct |
10 |
Correct |
3 ms |
8284 KB |
Output is correct |
11 |
Correct |
3 ms |
8284 KB |
Output is correct |
12 |
Correct |
3 ms |
8284 KB |
Output is correct |
13 |
Correct |
3 ms |
8272 KB |
Output is correct |
14 |
Correct |
3 ms |
8268 KB |
Output is correct |
15 |
Correct |
3 ms |
8284 KB |
Output is correct |
16 |
Correct |
3 ms |
8284 KB |
Output is correct |
17 |
Correct |
3 ms |
8284 KB |
Output is correct |
18 |
Correct |
3 ms |
8284 KB |
Output is correct |
19 |
Correct |
3 ms |
8280 KB |
Output is correct |
20 |
Correct |
3 ms |
8284 KB |
Output is correct |
21 |
Correct |
3 ms |
8284 KB |
Output is correct |
22 |
Correct |
3 ms |
8284 KB |
Output is correct |
23 |
Correct |
3 ms |
8140 KB |
Output is correct |
24 |
Correct |
4 ms |
8284 KB |
Output is correct |
25 |
Correct |
3 ms |
8212 KB |
Output is correct |
26 |
Correct |
3 ms |
8284 KB |
Output is correct |
27 |
Correct |
3 ms |
8284 KB |
Output is correct |
28 |
Correct |
3 ms |
8284 KB |
Output is correct |
29 |
Correct |
3 ms |
8276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8280 KB |
Output is correct |
2 |
Correct |
3 ms |
8284 KB |
Output is correct |
3 |
Correct |
3 ms |
8280 KB |
Output is correct |
4 |
Correct |
3 ms |
8284 KB |
Output is correct |
5 |
Correct |
3 ms |
8284 KB |
Output is correct |
6 |
Correct |
3 ms |
8284 KB |
Output is correct |
7 |
Correct |
3 ms |
8284 KB |
Output is correct |
8 |
Correct |
3 ms |
8284 KB |
Output is correct |
9 |
Correct |
3 ms |
8272 KB |
Output is correct |
10 |
Correct |
3 ms |
8284 KB |
Output is correct |
11 |
Correct |
3 ms |
8284 KB |
Output is correct |
12 |
Correct |
3 ms |
8284 KB |
Output is correct |
13 |
Correct |
3 ms |
8272 KB |
Output is correct |
14 |
Correct |
3 ms |
8268 KB |
Output is correct |
15 |
Correct |
3 ms |
8284 KB |
Output is correct |
16 |
Correct |
3 ms |
8284 KB |
Output is correct |
17 |
Correct |
3 ms |
8284 KB |
Output is correct |
18 |
Correct |
3 ms |
8284 KB |
Output is correct |
19 |
Correct |
3 ms |
8280 KB |
Output is correct |
20 |
Correct |
3 ms |
8284 KB |
Output is correct |
21 |
Correct |
3 ms |
8284 KB |
Output is correct |
22 |
Correct |
3 ms |
8284 KB |
Output is correct |
23 |
Correct |
3 ms |
8140 KB |
Output is correct |
24 |
Correct |
4 ms |
8284 KB |
Output is correct |
25 |
Correct |
3 ms |
8212 KB |
Output is correct |
26 |
Correct |
3 ms |
8284 KB |
Output is correct |
27 |
Correct |
3 ms |
8284 KB |
Output is correct |
28 |
Correct |
3 ms |
8284 KB |
Output is correct |
29 |
Correct |
3 ms |
8276 KB |
Output is correct |
30 |
Correct |
129 ms |
54008 KB |
Output is correct |
31 |
Correct |
120 ms |
54028 KB |
Output is correct |
32 |
Correct |
89 ms |
61908 KB |
Output is correct |
33 |
Correct |
97 ms |
61776 KB |
Output is correct |
34 |
Correct |
93 ms |
61816 KB |
Output is correct |
35 |
Correct |
94 ms |
61816 KB |
Output is correct |
36 |
Correct |
93 ms |
61836 KB |
Output is correct |
37 |
Correct |
92 ms |
61776 KB |
Output is correct |
38 |
Correct |
90 ms |
59476 KB |
Output is correct |
39 |
Correct |
92 ms |
58764 KB |
Output is correct |
40 |
Correct |
98 ms |
55124 KB |
Output is correct |
41 |
Correct |
106 ms |
54268 KB |
Output is correct |
42 |
Correct |
101 ms |
54360 KB |
Output is correct |
43 |
Correct |
92 ms |
61832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8280 KB |
Output is correct |
2 |
Correct |
3 ms |
8284 KB |
Output is correct |
3 |
Correct |
3 ms |
8284 KB |
Output is correct |
4 |
Correct |
3 ms |
8284 KB |
Output is correct |
5 |
Correct |
3 ms |
8284 KB |
Output is correct |
6 |
Correct |
4 ms |
8280 KB |
Output is correct |
7 |
Correct |
3 ms |
8196 KB |
Output is correct |
8 |
Correct |
3 ms |
8308 KB |
Output is correct |
9 |
Correct |
3 ms |
8156 KB |
Output is correct |
10 |
Correct |
4 ms |
8280 KB |
Output is correct |
11 |
Correct |
4 ms |
8284 KB |
Output is correct |
12 |
Correct |
3 ms |
8284 KB |
Output is correct |
13 |
Correct |
3 ms |
8284 KB |
Output is correct |
14 |
Correct |
3 ms |
8284 KB |
Output is correct |
15 |
Correct |
3 ms |
8284 KB |
Output is correct |
16 |
Correct |
3 ms |
8284 KB |
Output is correct |
17 |
Correct |
3 ms |
8284 KB |
Output is correct |
18 |
Correct |
3 ms |
8220 KB |
Output is correct |
19 |
Correct |
3 ms |
8284 KB |
Output is correct |
20 |
Correct |
3 ms |
8284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8280 KB |
Output is correct |
2 |
Correct |
3 ms |
8284 KB |
Output is correct |
3 |
Correct |
3 ms |
8280 KB |
Output is correct |
4 |
Correct |
3 ms |
8284 KB |
Output is correct |
5 |
Correct |
3 ms |
8284 KB |
Output is correct |
6 |
Correct |
3 ms |
8284 KB |
Output is correct |
7 |
Correct |
3 ms |
8284 KB |
Output is correct |
8 |
Correct |
3 ms |
8284 KB |
Output is correct |
9 |
Correct |
3 ms |
8272 KB |
Output is correct |
10 |
Correct |
3 ms |
8284 KB |
Output is correct |
11 |
Correct |
3 ms |
8284 KB |
Output is correct |
12 |
Correct |
3 ms |
8284 KB |
Output is correct |
13 |
Correct |
3 ms |
8272 KB |
Output is correct |
14 |
Correct |
3 ms |
8268 KB |
Output is correct |
15 |
Correct |
3 ms |
8284 KB |
Output is correct |
16 |
Correct |
3 ms |
8284 KB |
Output is correct |
17 |
Correct |
3 ms |
8284 KB |
Output is correct |
18 |
Correct |
3 ms |
8284 KB |
Output is correct |
19 |
Correct |
3 ms |
8280 KB |
Output is correct |
20 |
Correct |
3 ms |
8284 KB |
Output is correct |
21 |
Correct |
3 ms |
8284 KB |
Output is correct |
22 |
Correct |
3 ms |
8284 KB |
Output is correct |
23 |
Correct |
3 ms |
8140 KB |
Output is correct |
24 |
Correct |
4 ms |
8284 KB |
Output is correct |
25 |
Correct |
3 ms |
8212 KB |
Output is correct |
26 |
Correct |
3 ms |
8284 KB |
Output is correct |
27 |
Correct |
3 ms |
8284 KB |
Output is correct |
28 |
Correct |
3 ms |
8284 KB |
Output is correct |
29 |
Correct |
3 ms |
8276 KB |
Output is correct |
30 |
Correct |
129 ms |
54008 KB |
Output is correct |
31 |
Correct |
120 ms |
54028 KB |
Output is correct |
32 |
Correct |
89 ms |
61908 KB |
Output is correct |
33 |
Correct |
97 ms |
61776 KB |
Output is correct |
34 |
Correct |
93 ms |
61816 KB |
Output is correct |
35 |
Correct |
94 ms |
61816 KB |
Output is correct |
36 |
Correct |
93 ms |
61836 KB |
Output is correct |
37 |
Correct |
92 ms |
61776 KB |
Output is correct |
38 |
Correct |
90 ms |
59476 KB |
Output is correct |
39 |
Correct |
92 ms |
58764 KB |
Output is correct |
40 |
Correct |
98 ms |
55124 KB |
Output is correct |
41 |
Correct |
106 ms |
54268 KB |
Output is correct |
42 |
Correct |
101 ms |
54360 KB |
Output is correct |
43 |
Correct |
92 ms |
61832 KB |
Output is correct |
44 |
Correct |
3 ms |
8280 KB |
Output is correct |
45 |
Correct |
3 ms |
8284 KB |
Output is correct |
46 |
Correct |
3 ms |
8284 KB |
Output is correct |
47 |
Correct |
3 ms |
8284 KB |
Output is correct |
48 |
Correct |
3 ms |
8284 KB |
Output is correct |
49 |
Correct |
4 ms |
8280 KB |
Output is correct |
50 |
Correct |
3 ms |
8196 KB |
Output is correct |
51 |
Correct |
3 ms |
8308 KB |
Output is correct |
52 |
Correct |
3 ms |
8156 KB |
Output is correct |
53 |
Correct |
4 ms |
8280 KB |
Output is correct |
54 |
Correct |
4 ms |
8284 KB |
Output is correct |
55 |
Correct |
3 ms |
8284 KB |
Output is correct |
56 |
Correct |
3 ms |
8284 KB |
Output is correct |
57 |
Correct |
3 ms |
8284 KB |
Output is correct |
58 |
Correct |
3 ms |
8284 KB |
Output is correct |
59 |
Correct |
3 ms |
8284 KB |
Output is correct |
60 |
Correct |
3 ms |
8284 KB |
Output is correct |
61 |
Correct |
3 ms |
8220 KB |
Output is correct |
62 |
Correct |
3 ms |
8284 KB |
Output is correct |
63 |
Correct |
3 ms |
8284 KB |
Output is correct |
64 |
Correct |
89 ms |
61776 KB |
Output is correct |
65 |
Correct |
93 ms |
61776 KB |
Output is correct |
66 |
Correct |
91 ms |
61776 KB |
Output is correct |
67 |
Correct |
90 ms |
61524 KB |
Output is correct |
68 |
Correct |
13 ms |
13404 KB |
Output is correct |
69 |
Correct |
12 ms |
13592 KB |
Output is correct |
70 |
Correct |
13 ms |
13404 KB |
Output is correct |
71 |
Correct |
12 ms |
13344 KB |
Output is correct |
72 |
Correct |
11 ms |
13404 KB |
Output is correct |
73 |
Correct |
11 ms |
12840 KB |
Output is correct |
74 |
Correct |
91 ms |
61776 KB |
Output is correct |
75 |
Correct |
91 ms |
61776 KB |
Output is correct |
76 |
Correct |
96 ms |
61820 KB |
Output is correct |
77 |
Correct |
93 ms |
61776 KB |
Output is correct |
78 |
Correct |
95 ms |
61776 KB |
Output is correct |
79 |
Correct |
96 ms |
61776 KB |
Output is correct |
80 |
Correct |
88 ms |
61820 KB |
Output is correct |
81 |
Correct |
90 ms |
59220 KB |
Output is correct |
82 |
Correct |
86 ms |
59216 KB |
Output is correct |
83 |
Correct |
93 ms |
61776 KB |
Output is correct |
84 |
Correct |
95 ms |
62032 KB |
Output is correct |
85 |
Correct |
109 ms |
61712 KB |
Output is correct |
86 |
Correct |
90 ms |
61780 KB |
Output is correct |
87 |
Correct |
90 ms |
61780 KB |
Output is correct |
88 |
Correct |
91 ms |
61780 KB |
Output is correct |
89 |
Correct |
92 ms |
61832 KB |
Output is correct |
90 |
Correct |
88 ms |
61840 KB |
Output is correct |
91 |
Correct |
92 ms |
60752 KB |
Output is correct |
92 |
Correct |
90 ms |
55768 KB |
Output is correct |