#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl;
#define ll long long
const ll maxn = 1e6 + 10;
bool marc[maxn], especial[maxn];
queue<int> seg[4*maxn];
queue<int> fila;
void update( int pos, int ini, int fim, int ki, int kf ){
if( ki > fim || ini > kf ) return;
if( ki <= ini && fim <= kf ){ seg[pos].push(ki); return; }
int mid = (ini + fim)/2;
update( 2*pos, ini, mid, ki, kf ); update( 2*pos + 1, mid + 1, fim, ki, kf );
}
void activate( int pos, int ini, int fim, int id ){
while( !seg[pos].empty() ){
if( !marc[seg[pos].front()] ){
marc[seg[pos].front()] = true;
fila.push(seg[pos].front());
}
seg[pos].pop();
}
if( ini == fim ) return;
int mid = (ini + fim)/2;
if( id <= mid ) activate( 2*pos, ini, mid, id );
else activate( 2*pos + 1, mid + 1, fim, id );
}
long long minimum_walk(vector<int> p, int s) {
if( is_sorted( p.begin(), p.end() ) ) return 0;
ll n = (ll)p.size();
ll resp = 0;
for( ll i = 0; i < (ll)p.size(); i++ ) resp += (ll)abs(p[i] - i);
int maxi = -1;
bool contido = false;
for( ll i = 0; i < n; i++ ) if( !marc[i] && p[i] != i ){
if( i > maxi ){
if( maxi != -1 ) resp += 2LL*(i - maxi);
fila.push(i);
}
int cur = p[i], maior = i;
while( cur != i ){
maxi = max( maxi, cur );
maior = max( maior, cur );
cur = p[cur];
}
update( 1, 0, n - 1, i, maior );
if( i <= s && s <= maxi ) contido = true;
}
while( !fila.empty() ){
int cur = fila.front(); fila.pop();
marc[cur] = true;
while( !especial[cur] ){
especial[cur] = true;
activate( 1, 0, n - 1, cur );
cur = p[cur];
}
}
ll l = s, r = s;
while( l >= 0 && !especial[l] ) l--;
while( r < n && !especial[r] ) r++;
if( contido ) resp += 2LL*min( s - l, r - s );
else{
if( l == -1 ) resp += 2LL*(r - s);
else if( r == n ) resp += 2LL*(s - l);
}
return resp;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
348 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
348 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
348 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
350 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
348 ms |
1048576 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |