Submission #817872

#TimeUsernameProblemLanguageResultExecution timeMemory
817872mosiashvililukaShortcut (IOI16_shortcut)C++14
71 / 100
2053 ms21352 KiB
#include<bits/stdc++.h> #include "shortcut.h" using namespace std; const int ZM=/*1000009*/100009; const long long N=999999999999999999LL; long long a,b,c,d,e,i,j,ii,jj,zx,xc,dis[ZM],JM[ZM],C,pas,PR[ZM],SF[ZM],rmqC[ZM][22],k[ZM],rmqD[ZM][22],lef,rig,mid; long long ansPR[ZM],ansSF[ZM]; /*long long dista(int j, int i){ c=JM[i]-JM[j]+dis[i]+dis[j]; d=JM[j]-JM[q]+C+JM[w]-JM[i]+dis[i]+dis[j]; }*/ long long askC(long long q, long long w){ long long qw=k[w-q+1]; return max(rmqC[q][qw],rmqC[w-(1<<qw)+1][qw]); } long long askD(long long q, long long w){ long long qw=k[w-q+1]; return max(rmqD[q][qw],rmqD[w-(1<<qw)+1][qw]); } pair <pair <long long, long long>, long long> DO(int q, int w){ long long Qw=dis[q],We=dis[w]; long long pas1=0,pas2=0; /*dis[q]=max(dis[q],JM[q]); dis[w]=max(dis[w],JM[a]-JM[w]);*/ dis[q]=PR[q]+JM[q]; dis[w]=SF[w]-JM[w]; // long long i,j,zx,c,d,jj; jj=q; for(i=q+1; i<=w; i++){ zx=0; /*for(j=q; j<i; j++){ c=JM[i]-JM[j]+dis[i]+dis[j]; d=JM[j]-JM[q]+C+JM[w]-JM[i]+dis[i]+dis[j]; zx=max(zx,min(c,d)); }*/ while(jj<i){ j=jj; c=JM[i]-JM[j]+dis[i]+dis[j]; d=JM[j]-JM[q]+C+JM[w]-JM[i]+dis[i]+dis[j]; if(d<=c){ jj++; }else{ break; } } //jj-dan i-1s chatvlit pirdapir midixar(c) da q-dan jj-1is chatvlit shemovlit (d) //c jj->i-1 if(jj<=i-1){ e=JM[i]+dis[i]; zx=max(zx,askC(jj,i-1)+e); } if(q<=jj-1){ e=C+JM[w]-JM[q]-JM[i]+dis[i]; zx=max(zx,askD(q,jj-1)+e); } j=q; c=JM[i]-JM[j]+dis[i]+dis[j]; d=JM[j]-JM[q]+C+JM[w]-JM[i]+dis[i]+dis[j]; zx=max(zx,min(c,d)); if(i<w){ pas1=max(pas1,zx); }else{ pas2=max(pas2,zx); } } pas2=max(pas2,ansSF[w]); // dis[q]=Qw;dis[w]=We; return {{pas1,pas2},ansPR[q]}; //return /*ragac*/; } long long find_shortcut(int Nn, std::vector<int> Ll, std::vector<int> Dd, int Cc) { a=Nn;C=Cc;pas=N; JM[1]=0; for(i=1; i<=a; i++){ dis[i]=Dd[i-1]; if(i<a){ JM[i+1]=JM[i]+Ll[i-1]; } } for(i=1; i<=a; i++){ PR[i]=dis[i]-JM[i]; if(i!=1) PR[i]=max(PR[i],PR[i-1]); } for(i=a; i>=1; i--){ SF[i]=dis[i]+JM[i]; if(i!=a) SF[i]=max(SF[i],SF[i+1]); } // for(i=1; i<=a; i++){ rmqC[i][0]=dis[i]-JM[i]; rmqD[i][0]=dis[i]+JM[i]; } for(j=1; j<=20; j++){ for(i=1; i<=a; i++){ if(i+(1<<j)-1>a) break; rmqC[i][j]=max(rmqC[i][j-1],rmqC[i+(1<<(j-1))][j-1]); rmqD[i][j]=max(rmqD[i][j-1],rmqD[i+(1<<(j-1))][j-1]); } } k[0]=0;k[1]=0; for(i=1; i<=a+3; i++){ k[i]=k[i-1]; if((1<<k[i])*2<i) k[i]++; } // for(i=2; i<=a; i++){ ansPR[i]=ansPR[i-1]; for(j=1; j<i; j++){ zx=JM[i]-JM[j]+dis[i]+dis[j]; ansPR[i]=max(ansPR[i],zx); } } for(i=a-1; i>=1; i--){ ansSF[i]=ansSF[i+1]; for(j=a; j>i; j--){ zx=JM[j]-JM[i]+dis[i]+dis[j]; ansSF[i]=max(ansSF[i],zx); } } for(i=1; i<=a; i++){ /*for(j=i+1; j<=a; j++){ pair <pair <long long, long long>, long long> P=DO(i,j); //cout<<i<<" "<<j<<" "<<P.first.first<<" "<<P.first.second<<"\n"; pas=min(pas,max(max(P.first.first,P.first.second),P.second)); }*/ lef=i;rig=a+1; while(1){ if(lef+1>=rig) break; mid=(lef+rig)/2; j=mid; pair <pair <long long, long long>, long long> P=DO(i,j); pas=min(pas,max(max(P.first.first,P.first.second),P.second)); if(P.first.first<=P.first.second){ lef=mid; }else{ rig=mid; } } } return pas; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...