#include <bits/stdc++.h>
using namespace std;
int parent[1100100];
int v[1100100];
bool done[1100100];
int l[1100100];
int r[1100100];
pair<int,int> expand_range(int l2, int r2, int h){
int l1 = min(l2,h);
int r1 = max(r2,h);
while(l1 != l2 || r1 != r2){
if(l1 != l2){
l2--;
l1 = min(l1,l[parent[l2]]);
r1 = max(r1,r[parent[l2]]);
}
else{
r2++;
l1 = min(l1,l[parent[r2]]);
r1 = max(r1,r[parent[r2]]);
}
}
return {l2,r2};
}
long long minimum_walk(vector<int> p, int s) {
int l1 = s;
int r1 = s;
int l2 = s;
int r2 = s;
long long int some = 0;
int N = p.size();
for(int i = 0; i < N; i++){
done[i] = false;
}
for(int i = 0; i < N; i++){
if(done[i]) continue;
l[i] = i;
r[i] = i;
parent[i] = i;
int j = p[i];
some += abs(i - j);
while(j != i){
int temp = j;
parent[j] = i;
done[j] = true;
r[i] = max(r[i],j);
j = p[j];
some += abs(temp - j);
}
}
l2 = l[parent[s]];
r2 = r[parent[s]];
while(l1 != l2 || r1 != r2){
if(l1 != l2){
l1--;
l2 = min(l2,l[parent[l1]]);
r2 = max(r2,r[parent[l1]]);
}
else{
r1++;
l2 = min(l2,l[parent[r1]]);
r2 = max(r2,r[parent[r1]]);
}
}
int l3l = l1;
int r3l = r1;
int l3r = l1;
int r3r = r1;
while(l1 != 0 || r1 != N - 1){
l3l = l1;
r3l = r1;
l3r = l1;
r3r = r1;
int tcoft = 0;
int coft = 0;
while(!(r1 < r3l && l3r < l1)){
coft += 2;
tcoft += 2;
if(l3l > 0){
pair<int,int> ii = expand_range(l3l,r3l,l3l - 1);
l3l = ii.first;
r3l = ii.second;
tcoft -= 2;
}
if(r3r < N - 1){
pair<int,int> ii = expand_range(l3r,r3r,r3r+1);
l3r = ii.first;
r3r = ii.second;
tcoft -= 2;
}
if(!(r1 < r3l && l3r < l1) && l3l == 0 && r3r == N - 1){
some += tcoft;
break;
}
}
some += coft;
l1 = min(l3l,l1);
l1 = min(l3r,l1);
r1 = max(r3l,r1);
r1 = max(r3r,r1);
}
return some;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Incorrect |
1 ms |
6492 KB |
3rd lines differ - on the 1st token, expected: '4', found: '6' |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Incorrect |
1 ms |
6492 KB |
3rd lines differ - on the 1st token, expected: '4', found: '6' |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Incorrect |
1 ms |
6492 KB |
3rd lines differ - on the 1st token, expected: '4', found: '6' |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
6492 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3506' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Incorrect |
1 ms |
6492 KB |
3rd lines differ - on the 1st token, expected: '4', found: '6' |
6 |
Halted |
0 ms |
0 KB |
- |