#include "books.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ll long long
#define sz(x) (int)x.size();
#define pb push_back
const int N = 1e6+5;
const int mod = 1e9+7;
int n, sz;
int used[N*4][2];
int val[N*4];
int par[N];
void build(int lx, int rx, int x){
//cout<<lx<<" "<<rx<<"\n";
if(lx == rx){
used[x][0] = lx, used[x][1] = lx;
val[x] = 0;
return;
}
int m = (lx + rx)>>1;
build(lx, m, x*2);
build(m+1, rx, x*2+1);
if(val[x*2] <= val[x*2+1]){
val[x] = val[x*2];
used[x][0] = used[x*2][0];
}
else {
val[x] = val[x*2+1];
used[x][0] = used[x*2+1][0];
}
if(val[x*2] >= val[x*2+1]){
val[x] = val[x*2+1];
used[x][1] = used[x*2+1][1];
}
else {
val[x] = val[x*2];
used[x][1] = used[x*2][1];
}
}
int findl(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return mod;
if(lx >= l && rx <= r) return (!val[x] ? used[x][0] : mod);
int m = (lx + rx)>>1;
int res1 = findl(l, r, lx, m, x*2);
int res2 = findl(l, r, m+1, rx, x*2+1);
return min(res1, res2);
}
int findr(int l, int r, int lx, int rx, int x){
//cout<<lx<<" "<<rx<<" "<<l<<" "<<r<<"\n";
if(lx > r || rx < l) return 0;
if(lx >= l && rx <= r) return (!val[x] ? used[x][1] : 0);
int m = (lx + rx)>>1;
int res1 = findr(l, r, lx, m, x*2);
int res2 = findr(l, r, m+1, rx, x*2+1);
return max(res1, res2);
}
void sett(int i, int v, int lx, int rx, int x){
//cout<<lx<<" "<<rx<<" "<<i<<" "<<v<<"\n";
if(lx == rx){
val[x] = 1;
return;
}int m = (lx + rx)>>1;
if(i <= m) sett(i, v, lx, m, x*2);
else sett(i, v, m+1, rx, x*2+1);
if(val[x*2] <= val[x*2+1]){
val[x] = val[x*2];
used[x][0] = used[x*2][0];
}
else {
val[x] = val[x*2+1];
used[x][0] = used[x*2+1][0];
}
if(val[x*2] >= val[x*2+1]){
val[x] = val[x*2+1];
used[x][1] = used[x*2+1][1];
}
else {
val[x] = val[x*2];
used[x][1] = used[x*2][1];
}
}
bool check(int x){
return val[x+sz-1];
}
ll dfs(int u, ll sum){
//cout<<u<<" ";
if(check(u)) return sum;
sett(u, 1, 1, sz, 1);
return dfs(par[u], sum+abs(par[u] - u));
}
/*
4 0
0 2 3 1
*/
ll minimum_walk(vector<int> p, int s) {
s++, n = sz(p);
sz = 1;
while(sz < n) sz <<= 1;
build(1, sz, 1);
for(int i=0;i<n;i++){
if(i == p[i]){
//cout<<i+1<<"\n";
sett(i+1, 1, 1, sz, 1);
continue;
}par[i+1] = p[i]+1;
}
//for(int i=1;i<2*sz;i++) cout<<val[i]<<" ";
//cout<<"\n";
//cout<<"here";
int l = findl(s, sz, 1, sz, 1);
//cout<<"here";
int r = findr(1, s, 1, sz, 1);
//cout<<"here";
int cur = s;
ll sum = 0;
while(l != mod || r){
//cout<<l<<" "<<r<<endl;
if(l == mod){
ll res = dfs(r, 0);
cur = r, sum += res;
}
else if(r == 0){
ll res = dfs(l, 0);
cur = l, sum += res;
}
else{
if(l - cur <= r - cur){
ll res = dfs(l, 0);
cur = l, sum += res;
}else{
ll res = dfs(r, 0);
cur = r, sum += res;
}
}
l = findl(cur, sz, 1, sz, 1);
r = findr(1, cur, 1, sz, 1);
}
return sum;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
3rd lines differ - on the 1st token, expected: '6', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
3rd lines differ - on the 1st token, expected: '6', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
3rd lines differ - on the 1st token, expected: '6', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2067 ms |
364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
3rd lines differ - on the 1st token, expected: '6', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
