#include "books.h"
#include<bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const int INF=INT_MAX>>1;
struct SegTree{
using T=pair<int,int>;
inline T op(T x,T y){
return {min(x.first,y.first),max(x.second,y.second)};
}
inline T e(){
return {INF,-INF};
}
vector<T> tree;
int size;
SegTree(int sz):size(sz){
tree.resize(size*2,e());
}
inline T get(int pos){
return tree[pos+size];
}
inline void set(int pos,T val){
tree[pos+size]=val;
}
T prod(int lf,int ri){
lf+=size;
ri+=size;
T rl=e();
T rr=e();
while(lf<ri){
if(lf&1){
rl=op(rl,tree[lf]);
lf++;
}
if(ri&1){
ri--;
rr=op(tree[ri],rr);
}
lf>>=1;
ri>>=1;
}
return op(rl,rr);
}
};
long long minimum_walk(std::vector<int> p, int s) {
int n=p.size();
vector<int> vis(n,-1);
vector<pair<int,int>> wide;
int cnt=0;
ll ans=0;
rep(i,n){
if(vis[i]>=0)continue;
if(p[i]==i&&i!=s)continue;
int lf=i;
int ri=i;
int pos=i;
while(vis[p[pos]]==-1){
ans+=abs(pos-p[pos]);
pos=p[pos];
vis[pos]=cnt;
lf=min(lf,pos);
ri=max(ri,pos);
}
cnt++;
wide.emplace_back(lf,ri);
}
vector<int> dist(cnt,-1);
SegTree seg(n);
rep(i,n){
if(vis[i]!=-1)seg.set(i,{i,i});
}
priority_queue<pair<int,int>,vector<pair<int,int>>,less<pair<int,int>>> pq;
pq.push({0,vis[s]});
while(!pq.empty()){
int dis,pos;
tie(dis,pos)=pq.top();
pq.pop();
if(dist[pos]!=-1)continue;
dist[pos]=0;
ans+=dis*2;
int lf,ri;
tie(lf,ri)=wide[pos];
rep(i,n){
if(vis[i]==-1)continue;
if(dist[vis[i]]!=-1)continue;
if(i<lf){
pq.push({abs(i-lf),vis[i]});
}
else if(ri<i){
pq.push({abs(i-ri),vis[i]});
}
else{
pq.push({0,vis[i]});
}
}
/*
while(true){
int nxt=seg.prod(lf+1,ri).first;
if(nxt>n)break;
seg.set(nxt,seg.e());
if(dist[vis[nxt]]==-1){
pq.push({0,vis[nxt]});
}
}
int nxt;
nxt=seg.prod(0,lf).second;
if(nxt>=0){
if(dist[vis[nxt]]==-1){
pq.push({abs(nxt-lf),vis[nxt]});
}
}
nxt=seg.prod(ri+1,n).first;
if(nxt<n){
if(dist[vis[nxt]]==-1){
pq.push({abs(nxt-ri),vis[nxt]});
}
}*/
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
984 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '273276' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
