#include "books.h"
#include<bits/stdc++.h>
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);
}
int sl,sr;
{
vector<pair<int,int>> seg=wide;
sort(all(seg));
vector<pair<int,int>> re={seg[0]};
rng(i,1,seg.size()){
if(seg[i].first<=re.back().second){
re.back().second=max(re.back().second,seg[i].second);
}
else{
re.emplace_back(seg[i]);
}
}
rep(i,re.size()-1){
ans+=2*(re[i+1].first-re[i].second);
}
for(auto i:re){
if(i.first<=s&&s<=i.second){
sl=i.first;
sr=i.second;
break;
}
}
}
vector<int> dist(cnt,INF);
dist[vis[s]]=0;
SegTree seg(n);
rng(i,sl,sr+1){
if(vis[i]!=-1)seg.set(i,{i,i});
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<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]!=dis)continue;
int lf,ri;
tie(lf,ri)=wide[pos];
while(true){
int nxt=seg.prod(lf+1,ri).first;
if(nxt>n)break;
seg.set(nxt,seg.e());
if(dist[vis[nxt]]>dis){
dist[vis[nxt]]=dis;
pq.push({dist[vis[nxt]],vis[nxt]});
}
}
int nxt;
nxt=seg.prod(0,lf).second;
if(0<=nxt){
if(dist[vis[nxt]]>dis+abs(nxt-ri)){
dist[vis[nxt]]=dis+abs(nxt-lf);
pq.push({dist[vis[nxt]],vis[nxt]});
}
}
nxt=seg.prod(ri+1,n).first;
if(nxt<n){
if(dist[vis[nxt]]>dis+abs(nxt-ri)){
dist[vis[nxt]]=dis+abs(nxt-lf);
pq.push({dist[vis[nxt]],vis[nxt]});
}
}
}
rep(i,cnt){
if(wide[i].first==sl)ans+=dist[i]*2;
}
return ans;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define rng(i,l,r) for(int i=(l); i<(r); i++)
| ^
books.cpp:79:3: note: in expansion of macro 'rng'
79 | rng(i,1,seg.size()){
| ^~~
books.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define rep(i,n) for(int i=0; i<(n); i++)
| ^
books.cpp:87:3: note: in expansion of macro 'rep'
87 | rep(i,re.size()-1){
| ^~~
books.cpp:5:36: warning: 'sr' may be used uninitialized in this function [-Wmaybe-uninitialized]
5 | #define rng(i,l,r) for(int i=(l); i<(r); i++)
| ^
books.cpp:74:9: note: 'sr' was declared here
74 | int sl,sr;
| ^~
books.cpp:74:6: warning: 'sl' may be used uninitialized in this function [-Wmaybe-uninitialized]
74 | int sl,sr;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
856 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
600 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
856 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
600 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
600 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
432 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
856 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
600 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
600 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
432 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
102 ms |
34384 KB |
Output is correct |
31 |
Correct |
100 ms |
34420 KB |
Output is correct |
32 |
Correct |
73 ms |
34372 KB |
Output is correct |
33 |
Correct |
90 ms |
36844 KB |
Output is correct |
34 |
Correct |
90 ms |
36588 KB |
Output is correct |
35 |
Correct |
96 ms |
37032 KB |
Output is correct |
36 |
Correct |
85 ms |
36312 KB |
Output is correct |
37 |
Correct |
85 ms |
34824 KB |
Output is correct |
38 |
Correct |
85 ms |
34644 KB |
Output is correct |
39 |
Correct |
80 ms |
34412 KB |
Output is correct |
40 |
Correct |
80 ms |
34388 KB |
Output is correct |
41 |
Correct |
123 ms |
34528 KB |
Output is correct |
42 |
Correct |
99 ms |
34388 KB |
Output is correct |
43 |
Correct |
89 ms |
37420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2147486390' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
856 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
600 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
600 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
432 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
102 ms |
34384 KB |
Output is correct |
31 |
Correct |
100 ms |
34420 KB |
Output is correct |
32 |
Correct |
73 ms |
34372 KB |
Output is correct |
33 |
Correct |
90 ms |
36844 KB |
Output is correct |
34 |
Correct |
90 ms |
36588 KB |
Output is correct |
35 |
Correct |
96 ms |
37032 KB |
Output is correct |
36 |
Correct |
85 ms |
36312 KB |
Output is correct |
37 |
Correct |
85 ms |
34824 KB |
Output is correct |
38 |
Correct |
85 ms |
34644 KB |
Output is correct |
39 |
Correct |
80 ms |
34412 KB |
Output is correct |
40 |
Correct |
80 ms |
34388 KB |
Output is correct |
41 |
Correct |
123 ms |
34528 KB |
Output is correct |
42 |
Correct |
99 ms |
34388 KB |
Output is correct |
43 |
Correct |
89 ms |
37420 KB |
Output is correct |
44 |
Incorrect |
0 ms |
348 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2147486390' |
45 |
Halted |
0 ms |
0 KB |
- |