#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
llint find_shortcut(int in,vector<int>l,vector<int>d,int c){
//まず、要らない人を除く
vector<llint>wa;//場所
vector<llint>di;
llint i,j;
vector<llint>eki(in+2);
wa.pub(-big);
di.pub(0);
llint gebas=0;
eki[0]=-big;
eki[in+1]=big;
for(i=0;i<in;i++){
if(i>0){gebas+=l[i-1];eki[i+1]=gebas;}
while(gebas-wa.back()<=d[i]-di.back()){wa.pob();di.pob();}
if(gebas-wa.back()>di.back()-d[i]){wa.pub(gebas);di.pub(d[i]);}
}
wa.pub(big);
di.pub(0);
llint n=wa.size()-2;
//とりあえずこれでいらないのは消えた
//二分探索!
//n=1だとなんか特別なことになる
//片方をそこに固定して、それをのぞいて適当にする
if(n==1){
//dの最大を探す,そこ出発以外考えなくてよい
//そこのdをぜろにしてもう一度同じこと
//つける相手の駅を全探索
//左と右のでかい側につける
llint saD=1;
for(i=0;i<in;i++){if(d[saD]<d[i]){saD=i;}}
llint mto=d[saD];d[saD]=0;
wa.clear();di.clear();
wa.pub(-mod);di.pub(0);gebas=0;
for(i=0;i<in;i++){
if(i>0){gebas+=l[i-1];}
while(gebas-wa.back()<=d[i]-di.back()){wa.pob();di.pob();}
if(gebas-wa.back()>di.back()-d[i]){wa.pub(gebas);di.pub(d[i]);}
}
wa.pub(big);
di.pub(0);
llint n=wa.size()-2;
llint bmin=0,bmax=big;
vector<llint>iwa;
vector<llint>idi;
vector<llint>ieki;
//左側に一番大きい頂点があるようにうまく変換する
//iwa[0]=0;
//idi[0]=0;
//それ以降はあれ
saD++;
//cerr<<"saD"<<saD<<endl;
if(eki[saD]-wa[1]+di[1]>wa[n]-eki[saD]+di[n]){
//左がでかいから小さくしたい、かえる
bmin=wa[n]-eki[saD]+di[n]-1;
iwa.pub(0);
idi.pub(0);
ieki.pub(0);
int sta=LBI(wa,eki[saD])-1;
wa[sta+1]=eki[saD];
for(i=sta;i>=0;i--){
iwa.pub(iwa.back()+wa[i+1]-wa[i]);
idi.pub(di[i]);
}
for(i=saD-1;i>=0;i--){
ieki.pub(ieki.back()+eki[i+1]-eki[i]);
}
}else{
//右がでかいから小さくしたい
//i<=n+1;
bmin=eki[saD]-wa[1]+di[1]-1;
iwa.pub(0);
idi.pub(0);
ieki.pub(0);
int sta=UBI(wa,eki[saD]);
wa[sta-1]=eki[saD];
for(i=sta;i<di.size();i++){
iwa.pub(iwa.back()+wa[i]-wa[i-1]);
idi.pub(di[i]);
}
for(i=saD+1;i<eki.size();i++){
ieki.pub(ieki.back()+eki[i]-eki[i-1]);
}
}
wa=iwa;eki=ieki;di=idi;
//for(auto it:wa){cout<<it<<" ";}cout<<endl;
//for(auto it:di){cout<<it<<" ";}cout<<endl;
n=wa.size()-2;
//すべての0は遠すぎる駅
//すべてのn+1は番兵
//すべての1~nは考えるべき駅
//bmin+1が答えの下限
bmax=wa[n]-wa[0]+di[n];//自明
while(bmax>bmin+1){
llint bgen=(bmax+bmin)/2;
int stdex=1;
for(i=n;i>0;i--){
if(wa[i]-wa[0]+di[i]>bgen){stdex=i;}
else{break;}
}
llint habig=big/2;
int stchu=LBI(eki,(big+wa[n]+wa[stdex]+di[n]-di[stdex])/2 -habig);
llint stdis=min(eki[stchu]-wa[stdex]+di[stdex],wa[n]-eki[stchu-1]+di[n]);
if(stdis+c<=bgen){bmax=bgen;}else{bmin=bgen;}
}
return mto+bmax;
}
llint bmin=0,bmax=wa[n]-wa[1]+di[n]+di[1];
//for(i=0;i<=n;i++){cerr<<wa[i]<<" "<<di[i]<<endl;}
while(bmax>bmin+1){
llint bgen=(bmax+bmin)/2;
if(di[1]+di[n]+c>bgen){bmin=bgen;continue;}//定数倍
int uedex=1,stdex=n;//uedex右端->どこまでひだり
for(i=1;i<=n;i++){
if(wa[n]-wa[i]+di[n]+di[i]>bgen){uedex=i;}
else{break;}
}
//ここを二分探索にする
for(i=n;i>0;i--){
if(wa[i]-wa[1]+di[1]+di[i]>bgen){stdex=i;}
else{break;}
}
if(stdex==1){stdex=2;}
if(uedex==n){uedex=n-1;}
//uedex,stdexがわかった
if(uedex>=stdex){bmin=bgen;continue;}
//あ
//0 - uedex,stdex - n-1
llint habig=big/2;
int uechu=LBI(eki,(big+wa[uedex]+wa[1]+di[uedex]-di[1])/2 -habig);
llint uedis=min(eki[uechu]-wa[1]+di[1],wa[uedex]-eki[uechu-1]+di[uedex]);
int stchu=LBI(eki,(big+wa[n]+wa[stdex]+di[n]-di[stdex])/2 -habig);
llint stdis=min(eki[stchu]-wa[stdex]+di[stdex],wa[n]-eki[stchu-1]+di[n]);
if(uedis+stdis+c<=bgen){bmax=bgen;}else{bmin=bgen;}
}
return bmax;
}
Compilation message
shortcut.cpp: In function 'llint find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:128:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=sta;i<di.size();i++){
~^~~~~~~~~~
shortcut.cpp:132:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=saD+1;i<eki.size();i++){
~^~~~~~~~~~~
shortcut.cpp:57:10: warning: unused variable 'j' [-Wunused-variable]
llint i,j;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
380 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
440 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
452 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
488 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
488 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
488 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
504 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
560 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
560 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
560 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
3 ms |
560 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
380 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
440 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
452 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
488 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
488 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
488 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
504 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
560 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
560 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
560 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
3 ms |
560 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
380 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
440 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
452 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
488 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
488 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
488 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
504 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
560 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
560 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
560 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
3 ms |
560 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
380 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
440 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
452 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
488 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
488 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
488 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
504 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
560 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
560 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
560 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
3 ms |
560 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
380 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
440 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
452 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
488 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
488 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
488 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
504 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
560 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
560 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
560 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
3 ms |
560 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
380 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
440 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
452 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
488 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
488 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
488 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
504 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
560 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
560 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
560 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
3 ms |
560 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
380 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
440 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
452 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
488 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
488 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
488 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
504 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
560 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
560 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
560 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
3 ms |
560 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
380 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
2 ms |
440 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
2 ms |
452 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
2 ms |
488 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
2 ms |
488 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
2 ms |
488 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
2 ms |
504 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
2 ms |
560 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
2 ms |
560 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
2 ms |
560 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
2 ms |
560 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
3 ms |
560 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |