#include<bits/stdc++.h>
using namespace std;
#define _ int v, int tl, int tr, int l, int r
#define tm (tl+tr >> 1)
#define sol v+v,tl,tm,l,r
#define sag v+v+1,tm+1,tr,l,r
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < ll , ll > pp;
const int mod = 1e9 + 7;
const int N = 1e6 + 6;
set < int > W[N];
int H[N],T[N],n,i,j,l,r,t,a,b,mn,mx,u,h;
int smn[N<<2],smx[N<<2];
ll x;
void up(int p) { // set value at position p
for (smn[p += n] = a, smx[p] = b; p > 1; p >>= 1){
smn[p>>1] = min(smn[p] , smn[p^1]);
smx[p>>1] = max(smx[p] , smx[p^1]);
}
}
void qry(int l, int r) { // sum on interval [l, r)
r++;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l&1) { mn = min(mn , smn[l]); mx = max(mx , smx[l]); l++; }
if (r&1) { r--; mn = min(mn , smn[r]); mx = max(mx , smx[r]); }
}
}
ll minimum_walk(vector < int > p, int s){
x = 0;
n = p.size();
// if(n > 1000) return 0;
memset(smn , 22 , sizeof smn);
for(i=0;i<n;i++){
x += abs(p[i] - i);
if(H[i]) continue;
r = i;
for(j=i; !H[j] ; j = p[j]){
H[j] = 1;
r = max(r , j);
}
for(j=i; !T[j] ; j = p[j]){
T[j] = 1;
a = i; b = r;
up(j);
}
}
for(i=0;i<n && p[i] == i; i++);
for(j=n-1;j>=0 && p[j] == j; j--);
queue < pair < int , pp > > Q[2];
Q[h=0].push(mp(0,mp(s,s)));
for(;;){
if(Q[h].size() == 0) h = !h;
l = Q[h].front().nd.st;
r = Q[h].front().nd.nd;
u = Q[h].front().st;
Q[h].pop();
if(W[l].find(r) != W[l].end()) continue;
// cout << l << " " << r << " " << -u << " aa\n";
if(l <= i && r >= j) return x + -u-u;
W[l].insert(r);
mn = n; mx = 0;
qry(l,r);
Q[h].push(mp(u,mp(mn,mx)));
if(l) Q[!h].push(mp(u-1,mp(l-1,r)));
if(r < n-1) Q[!h].push(mp(u-1,mp(l,r+1)));
}
}
/*
int main(){
cout << minimum_walk({1,0,2,3} , 2);
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
62968 KB |
Output is correct |
2 |
Correct |
51 ms |
62968 KB |
Output is correct |
3 |
Correct |
51 ms |
62996 KB |
Output is correct |
4 |
Correct |
51 ms |
62996 KB |
Output is correct |
5 |
Correct |
52 ms |
63124 KB |
Output is correct |
6 |
Correct |
51 ms |
63124 KB |
Output is correct |
7 |
Correct |
52 ms |
63124 KB |
Output is correct |
8 |
Correct |
51 ms |
63136 KB |
Output is correct |
9 |
Correct |
51 ms |
63204 KB |
Output is correct |
10 |
Correct |
51 ms |
63204 KB |
Output is correct |
11 |
Correct |
52 ms |
63212 KB |
Output is correct |
12 |
Correct |
52 ms |
63212 KB |
Output is correct |
13 |
Correct |
51 ms |
63212 KB |
Output is correct |
14 |
Correct |
52 ms |
63212 KB |
Output is correct |
15 |
Correct |
52 ms |
63212 KB |
Output is correct |
16 |
Correct |
57 ms |
63212 KB |
Output is correct |
17 |
Correct |
51 ms |
63220 KB |
Output is correct |
18 |
Correct |
51 ms |
63220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
62968 KB |
Output is correct |
2 |
Correct |
51 ms |
62968 KB |
Output is correct |
3 |
Correct |
51 ms |
62996 KB |
Output is correct |
4 |
Correct |
51 ms |
62996 KB |
Output is correct |
5 |
Correct |
52 ms |
63124 KB |
Output is correct |
6 |
Correct |
51 ms |
63124 KB |
Output is correct |
7 |
Correct |
52 ms |
63124 KB |
Output is correct |
8 |
Correct |
51 ms |
63136 KB |
Output is correct |
9 |
Correct |
51 ms |
63204 KB |
Output is correct |
10 |
Correct |
51 ms |
63204 KB |
Output is correct |
11 |
Correct |
52 ms |
63212 KB |
Output is correct |
12 |
Correct |
52 ms |
63212 KB |
Output is correct |
13 |
Correct |
51 ms |
63212 KB |
Output is correct |
14 |
Correct |
52 ms |
63212 KB |
Output is correct |
15 |
Correct |
52 ms |
63212 KB |
Output is correct |
16 |
Correct |
57 ms |
63212 KB |
Output is correct |
17 |
Correct |
51 ms |
63220 KB |
Output is correct |
18 |
Correct |
51 ms |
63220 KB |
Output is correct |
19 |
Correct |
53 ms |
63220 KB |
Output is correct |
20 |
Correct |
50 ms |
63220 KB |
Output is correct |
21 |
Correct |
52 ms |
63220 KB |
Output is correct |
22 |
Correct |
52 ms |
63220 KB |
Output is correct |
23 |
Correct |
53 ms |
63468 KB |
Output is correct |
24 |
Correct |
52 ms |
63468 KB |
Output is correct |
25 |
Correct |
52 ms |
63468 KB |
Output is correct |
26 |
Correct |
51 ms |
63468 KB |
Output is correct |
27 |
Correct |
49 ms |
63468 KB |
Output is correct |
28 |
Correct |
52 ms |
63468 KB |
Output is correct |
29 |
Correct |
52 ms |
63468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
62968 KB |
Output is correct |
2 |
Correct |
51 ms |
62968 KB |
Output is correct |
3 |
Correct |
51 ms |
62996 KB |
Output is correct |
4 |
Correct |
51 ms |
62996 KB |
Output is correct |
5 |
Correct |
52 ms |
63124 KB |
Output is correct |
6 |
Correct |
51 ms |
63124 KB |
Output is correct |
7 |
Correct |
52 ms |
63124 KB |
Output is correct |
8 |
Correct |
51 ms |
63136 KB |
Output is correct |
9 |
Correct |
51 ms |
63204 KB |
Output is correct |
10 |
Correct |
51 ms |
63204 KB |
Output is correct |
11 |
Correct |
52 ms |
63212 KB |
Output is correct |
12 |
Correct |
52 ms |
63212 KB |
Output is correct |
13 |
Correct |
51 ms |
63212 KB |
Output is correct |
14 |
Correct |
52 ms |
63212 KB |
Output is correct |
15 |
Correct |
52 ms |
63212 KB |
Output is correct |
16 |
Correct |
57 ms |
63212 KB |
Output is correct |
17 |
Correct |
51 ms |
63220 KB |
Output is correct |
18 |
Correct |
51 ms |
63220 KB |
Output is correct |
19 |
Correct |
53 ms |
63220 KB |
Output is correct |
20 |
Correct |
50 ms |
63220 KB |
Output is correct |
21 |
Correct |
52 ms |
63220 KB |
Output is correct |
22 |
Correct |
52 ms |
63220 KB |
Output is correct |
23 |
Correct |
53 ms |
63468 KB |
Output is correct |
24 |
Correct |
52 ms |
63468 KB |
Output is correct |
25 |
Correct |
52 ms |
63468 KB |
Output is correct |
26 |
Correct |
51 ms |
63468 KB |
Output is correct |
27 |
Correct |
49 ms |
63468 KB |
Output is correct |
28 |
Correct |
52 ms |
63468 KB |
Output is correct |
29 |
Correct |
52 ms |
63468 KB |
Output is correct |
30 |
Correct |
665 ms |
86636 KB |
Output is correct |
31 |
Correct |
680 ms |
86764 KB |
Output is correct |
32 |
Correct |
253 ms |
86764 KB |
Output is correct |
33 |
Correct |
790 ms |
134640 KB |
Output is correct |
34 |
Correct |
780 ms |
134668 KB |
Output is correct |
35 |
Correct |
817 ms |
134832 KB |
Output is correct |
36 |
Correct |
879 ms |
134832 KB |
Output is correct |
37 |
Correct |
1211 ms |
134832 KB |
Output is correct |
38 |
Correct |
721 ms |
134832 KB |
Output is correct |
39 |
Correct |
582 ms |
134832 KB |
Output is correct |
40 |
Correct |
351 ms |
134832 KB |
Output is correct |
41 |
Correct |
436 ms |
134832 KB |
Output is correct |
42 |
Correct |
401 ms |
134832 KB |
Output is correct |
43 |
Correct |
249 ms |
134832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
134832 KB |
Output is correct |
2 |
Correct |
51 ms |
134832 KB |
Output is correct |
3 |
Correct |
91 ms |
134832 KB |
Output is correct |
4 |
Correct |
226 ms |
134832 KB |
Output is correct |
5 |
Correct |
245 ms |
134832 KB |
Output is correct |
6 |
Correct |
51 ms |
134832 KB |
Output is correct |
7 |
Correct |
50 ms |
134832 KB |
Output is correct |
8 |
Correct |
50 ms |
134832 KB |
Output is correct |
9 |
Correct |
50 ms |
134832 KB |
Output is correct |
10 |
Correct |
51 ms |
134832 KB |
Output is correct |
11 |
Correct |
206 ms |
134832 KB |
Output is correct |
12 |
Correct |
197 ms |
134832 KB |
Output is correct |
13 |
Correct |
70 ms |
134832 KB |
Output is correct |
14 |
Correct |
66 ms |
134832 KB |
Output is correct |
15 |
Correct |
53 ms |
134832 KB |
Output is correct |
16 |
Correct |
52 ms |
134832 KB |
Output is correct |
17 |
Correct |
143 ms |
134832 KB |
Output is correct |
18 |
Correct |
127 ms |
134832 KB |
Output is correct |
19 |
Correct |
76 ms |
134832 KB |
Output is correct |
20 |
Correct |
50 ms |
134832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
62968 KB |
Output is correct |
2 |
Correct |
51 ms |
62968 KB |
Output is correct |
3 |
Correct |
51 ms |
62996 KB |
Output is correct |
4 |
Correct |
51 ms |
62996 KB |
Output is correct |
5 |
Correct |
52 ms |
63124 KB |
Output is correct |
6 |
Correct |
51 ms |
63124 KB |
Output is correct |
7 |
Correct |
52 ms |
63124 KB |
Output is correct |
8 |
Correct |
51 ms |
63136 KB |
Output is correct |
9 |
Correct |
51 ms |
63204 KB |
Output is correct |
10 |
Correct |
51 ms |
63204 KB |
Output is correct |
11 |
Correct |
52 ms |
63212 KB |
Output is correct |
12 |
Correct |
52 ms |
63212 KB |
Output is correct |
13 |
Correct |
51 ms |
63212 KB |
Output is correct |
14 |
Correct |
52 ms |
63212 KB |
Output is correct |
15 |
Correct |
52 ms |
63212 KB |
Output is correct |
16 |
Correct |
57 ms |
63212 KB |
Output is correct |
17 |
Correct |
51 ms |
63220 KB |
Output is correct |
18 |
Correct |
51 ms |
63220 KB |
Output is correct |
19 |
Correct |
53 ms |
63220 KB |
Output is correct |
20 |
Correct |
50 ms |
63220 KB |
Output is correct |
21 |
Correct |
52 ms |
63220 KB |
Output is correct |
22 |
Correct |
52 ms |
63220 KB |
Output is correct |
23 |
Correct |
53 ms |
63468 KB |
Output is correct |
24 |
Correct |
52 ms |
63468 KB |
Output is correct |
25 |
Correct |
52 ms |
63468 KB |
Output is correct |
26 |
Correct |
51 ms |
63468 KB |
Output is correct |
27 |
Correct |
49 ms |
63468 KB |
Output is correct |
28 |
Correct |
52 ms |
63468 KB |
Output is correct |
29 |
Correct |
52 ms |
63468 KB |
Output is correct |
30 |
Correct |
665 ms |
86636 KB |
Output is correct |
31 |
Correct |
680 ms |
86764 KB |
Output is correct |
32 |
Correct |
253 ms |
86764 KB |
Output is correct |
33 |
Correct |
790 ms |
134640 KB |
Output is correct |
34 |
Correct |
780 ms |
134668 KB |
Output is correct |
35 |
Correct |
817 ms |
134832 KB |
Output is correct |
36 |
Correct |
879 ms |
134832 KB |
Output is correct |
37 |
Correct |
1211 ms |
134832 KB |
Output is correct |
38 |
Correct |
721 ms |
134832 KB |
Output is correct |
39 |
Correct |
582 ms |
134832 KB |
Output is correct |
40 |
Correct |
351 ms |
134832 KB |
Output is correct |
41 |
Correct |
436 ms |
134832 KB |
Output is correct |
42 |
Correct |
401 ms |
134832 KB |
Output is correct |
43 |
Correct |
249 ms |
134832 KB |
Output is correct |
44 |
Correct |
106 ms |
134832 KB |
Output is correct |
45 |
Correct |
51 ms |
134832 KB |
Output is correct |
46 |
Correct |
91 ms |
134832 KB |
Output is correct |
47 |
Correct |
226 ms |
134832 KB |
Output is correct |
48 |
Correct |
245 ms |
134832 KB |
Output is correct |
49 |
Correct |
51 ms |
134832 KB |
Output is correct |
50 |
Correct |
50 ms |
134832 KB |
Output is correct |
51 |
Correct |
50 ms |
134832 KB |
Output is correct |
52 |
Correct |
50 ms |
134832 KB |
Output is correct |
53 |
Correct |
51 ms |
134832 KB |
Output is correct |
54 |
Correct |
206 ms |
134832 KB |
Output is correct |
55 |
Correct |
197 ms |
134832 KB |
Output is correct |
56 |
Correct |
70 ms |
134832 KB |
Output is correct |
57 |
Correct |
66 ms |
134832 KB |
Output is correct |
58 |
Correct |
53 ms |
134832 KB |
Output is correct |
59 |
Correct |
52 ms |
134832 KB |
Output is correct |
60 |
Correct |
143 ms |
134832 KB |
Output is correct |
61 |
Correct |
127 ms |
134832 KB |
Output is correct |
62 |
Correct |
76 ms |
134832 KB |
Output is correct |
63 |
Correct |
50 ms |
134832 KB |
Output is correct |
64 |
Correct |
1441 ms |
143280 KB |
Output is correct |
65 |
Execution timed out |
2061 ms |
161440 KB |
Time limit exceeded |
66 |
Halted |
0 ms |
0 KB |
- |