//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
#include "books.h"
int ans=0;
int n;
vector<int> adj[1000001];
int vis[1000001];
//pair<int,int> cot[1000001];
int par[1000001];
/*int find(int no){
if(par[no]==no){
return no;
}
par[no]=find(par[no]);
return par[no];
}*/
vector<int> ss;
void dfs(int no){
vis[no]=1;
ss.pb(no);
for(auto j:adj[no]){
if(vis[j]==0){
dfs(j);
}
}
}
//vector<int> adj2[1000001];
int ind[1000001];
pair<int,int> pp;
vector<pair<int,int>> tt;
vector<pair<int,int>> pre2[1000001];
vector<pair<int,int>> pre3[1000001];
//int dp[1001][1001];
pair<int,int> rr2[1000001];
pair<int,int> rr[1000001];
/*void dfs2(int no,int par=-1){
pp.a=min(pp.a,tt[no].a);
pp.b=max(pp.b,tt[no].b);
vis[no]=1;
for(auto j:adj2[no]){
if(vis[j]==0){
dfs2(j);
}
}
}*/
vector<int> kk[1000001];
int tree[4*1000001];
void update(int no,int l,int r,int i,int j){
if(l==r){
tree[no]=min(tree[no],j);
}
else{
int mid=(l+r)/2;
if(i<=mid){
update(no*2+1,l,mid,i,j);
}
else{
update(no*2+2,mid+1,r,i,j);
}
tree[no]=min(tree[no*2+1],tree[no*2+2]);
}
}
int query(int no,int l,int r,int aa,int bb){
if(r<aa or l>bb){
return n;
}
if(aa<=l and r<=bb){
return tree[no];
}
else{
int mid=(l+r)/2;
return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
}
int tree2[4*1000001];
void update2(int no,int l,int r,int i,int j){
if(l==r){
tree2[no]=max(tree2[no],j);
}
else{
int mid=(l+r)/2;
if(i<=mid){
update2(no*2+1,l,mid,i,j);
}
else{
update2(no*2+2,mid+1,r,i,j);
}
tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
}
}
int query2(int no,int l,int r,int aa,int bb){
if(r<aa or l>bb){
return 0;
}
if(aa<=l and r<=bb){
return tree2[no];
}
else{
int mid=(l+r)/2;
return max(query2(no*2+1,l,mid,aa,bb),query2(no*2+2,mid+1,r,aa,bb));
}
}
long long minimum_walk(std::vector<int> p, int s) {
while(p.size()){
if(p.back()+1==p.size()){
p.pop_back();
}
else{
break;
}
}
llo stt=0;
while(stt<p.size()){
if(p[stt]==stt){
stt++;
}
else{
break;
}
}
vector<int> it;
for(int j=stt;j<p.size();j++){
it.pb(p[j]-stt);
}
p=it;
n=p.size();
if(n==0){
return 0;
}
for(int i=0;i<n;i++){
adj[i].pb(p[i]);
}
//int co=0;
llo ans=0;
vector<vector<int>> zz5;
for(int i=0;i<n;i++){
if(vis[i]==0){
ss.clear();
dfs(i);
int mi=ss[0];
int ma=ss[0];
for(auto j:ss){
mi=min(mi,j);
ma=max(ma,j);
}
/*for(auto j:ss){
cot[j]={mi,ma};
}*/
int zz=tt.size();
for(auto j:ss){
ind[j]=tt.size();
}
rr2[tt.size()]={mi,ma};
tt.pb({mi,ma});
for(int j=0;j+1<ss.size();j++){
ans+=(llo)abs(ss[j]-ss[j+1]);
}
zz5.pb(ss);
ans+=(llo)(abs(ss[0]-ss.back()));
sort(ss.begin(),ss.end());
for(int j=0;j+1<ss.size();j++){
pre2[ss[j+1]].pb({ss[j],zz});
}
for(int j=0;j+1<ss.size();j++){
pre3[ss[j]].pb({ss[j+1],zz});
}
}
}
for(int i=0;i<4*n;i++){
tree[i]=4*n;
}
for(int i=0;i<n;i++){
for(auto j:pre2[i]){
int x=query(0,0,n-1,j.a,i-1);
rr2[j.b].a=min(rr2[j.b].a,x);
update(0,0,n-1,i,rr2[j.b].a);
}
}
for(int i=0;i<4*n;i++){
tree2[i]=0;
}
for(int i=n-1;i>=0;i--){
for(auto j:pre3[i]){
int x=query2(0,0,n-1,i+1,j.a);
rr2[j.b].b=max(rr2[j.b].b,x);
update2(0,0,n-1,i,rr2[j.b].b);
}
}
for(int i=0;i<tt.size();i++){
for(auto j:zz5[i]){
rr[j]=rr2[i];
}
}
//cout<<ans<<":"<<endl;
pair<int,int> cur3={rr[s].a,rr[s].b};
while(cur3.a>0 or cur3.b<n-1){
if(cur3.b==n-1){
ans+=2;
cur3={rr[cur3.a-1].a,max(cur3.b,rr[cur3.a-1].b)};
continue;
}
else if(cur3.a==0){
ans+=2;
cur3={min(rr[cur3.b+1].a,cur3.a),rr[cur3.b+1].b};
continue;
}
else{
if(rr[cur3.a-1].b>cur3.b){
ans+=2;
cur3={rr[cur3.a-1].a,max(cur3.b,rr[cur3.a-1].b)};
continue;
}
else if(rr[cur3.b+1].a<cur3.a){
ans+=2;
cur3={min(rr[cur3.b+1].a,cur3.a),rr[cur3.b+1].b};
continue;
}
vector<pair<int,int>> aa;
vector<pair<int,int>> bb;
pair<int,int> cur4=cur3;
pair<int,int> cur5=cur3;
int st=-1;
while(cur4.a>0 or cur5.b<n-1){
if(cur4.a>0){
if(rr[cur4.a-1].b>cur3.b){
st=0;
break;
}
}
if(cur5.b<n-1){
if(rr[cur5.b+1].a<cur3.a){
st=1;
break;
}
}
if(cur4.a>0){
cur4={rr[cur4.a-1].a,max(cur4.b,rr[cur4.a-1].b)};
aa.pb(cur4);
}
if(cur5.b<n-1){
cur5={min(rr[cur5.b+1].a,cur5.a),rr[cur5.b+1].b};
bb.pb(cur5);
}
}
llo xx2=aa.size();
llo yy2=bb.size();
if(st==-1){
ans+=2*xx2+2*yy2;
break;
}
if(st==0){
cur3=aa.back();
ans+=2*xx2;
}
else{
cur3=bb.back();
ans+=2*yy2;
}
}
}
return ans;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:122:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | if(p.back()+1==p.size()){
| ~~~~~~~~~~^~~~~~~~~~
books.cpp:130:11: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | while(stt<p.size()){
| ~~~^~~~~~~~~
books.cpp:139:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for(int j=stt;j<p.size();j++){
| ~^~~~~~~~~
books.cpp:174:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for(int j=0;j+1<ss.size();j++){
| ~~~^~~~~~~~~~
books.cpp:181:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | for(int j=0;j+1<ss.size();j++){
| ~~~^~~~~~~~~~
books.cpp:184:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | for(int j=0;j+1<ss.size();j++){
| ~~~^~~~~~~~~~
books.cpp:212:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
212 | for(int i=0;i<tt.size();i++){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
94316 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 |
64 ms |
94316 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 |
64 ms |
94316 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 |
Correct |
65 ms |
94444 KB |
Output is correct |
| 2 |
Correct |
64 ms |
94444 KB |
Output is correct |
| 3 |
Correct |
64 ms |
94444 KB |
Output is correct |
| 4 |
Correct |
65 ms |
94444 KB |
Output is correct |
| 5 |
Correct |
65 ms |
94444 KB |
Output is correct |
| 6 |
Correct |
65 ms |
94536 KB |
Output is correct |
| 7 |
Correct |
70 ms |
94444 KB |
Output is correct |
| 8 |
Correct |
66 ms |
94444 KB |
Output is correct |
| 9 |
Correct |
65 ms |
94484 KB |
Output is correct |
| 10 |
Correct |
65 ms |
94316 KB |
Output is correct |
| 11 |
Correct |
65 ms |
94444 KB |
Output is correct |
| 12 |
Correct |
64 ms |
94444 KB |
Output is correct |
| 13 |
Correct |
64 ms |
94444 KB |
Output is correct |
| 14 |
Correct |
75 ms |
94444 KB |
Output is correct |
| 15 |
Correct |
66 ms |
94464 KB |
Output is correct |
| 16 |
Correct |
66 ms |
94644 KB |
Output is correct |
| 17 |
Correct |
65 ms |
94572 KB |
Output is correct |
| 18 |
Correct |
65 ms |
94444 KB |
Output is correct |
| 19 |
Correct |
65 ms |
94444 KB |
Output is correct |
| 20 |
Correct |
65 ms |
94444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
94316 KB |
3rd lines differ - on the 1st token, expected: '6', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
