Submission #892984

#TimeUsernameProblemLanguageResultExecution timeMemory
892984alexander707070Bitaro's travel (JOI23_travel)C++14
15 / 100
3077 ms3960 KiB
#include<bits/stdc++.h> #define MAXN 200007 using namespace std; const long long inf=1e15; long long n,t[MAXN],q,s; long long solve(long long s,int from,int to){ int l=from,r=to; long long res=0; while(l!=0 or r!=n+1){ if(l>=1 and s-t[l]<=t[r]-s){ int ll=0,rr=l,mid; while(ll+1<rr){ mid=(ll+rr)/2; if(s-t[mid]<2*(s-t[l])){ rr=mid; }else{ ll=mid; } } res+=s-t[rr]; l=rr-1; s=t[rr]; }else if(r<=n and t[r]-s<=s-t[l]){ int ll=r,rr=n+1,mid; while(ll+1<rr){ mid=(ll+rr)/2; if(t[mid]-s<2*(t[r]-s)){ ll=mid; }else{ rr=mid; } } res+=t[ll]-s; r=ll+1; s=t[ll]; }else{ exit(0); } } return res; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>t[i]; } t[n+1]=inf; t[0]=-inf; cin>>q; for(int i=1;i<=q;i++){ cin>>s; int l=0,r=n+1,mid; while(l+1<r){ mid=(l+r)/2; if(t[mid]<=s){ l=mid; }else{ r=mid; } } cout<<solve(s,l,l+1)<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...