Submission #902548

#TimeUsernameProblemLanguageResultExecution timeMemory
902548abcvuitunggioShortcut (IOI16_shortcut)C++17
0 / 100
1 ms600 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; const long long INF=1LL<<51; const int mxn=1000001; long long s[mxn]; long long find_shortcut(int n, vector <int> l, vector <int> d, int c){ for (int i=1;i<n;i++) s[i]=s[i-1]+l[i-1]; s[n]=INF; long long lo=0,hi=INF,kq=-1; while (lo<=hi){ long long mid=(lo+hi)>>1,mnx=-INF,mxx=INF,mny=-INF,mxy=INF,x=-INF,y=INF; deque <pair <int, int>> q; for (int i=0;i<n;i++){ while (!q.empty()&&s[i]+d[i]-q.front().first>mid){ int i=q.front().second; x=max(x,s[i]+d[i]); y=min(x,s[i]-d[i]); q.pop_front(); } while (!q.empty()&&q.back().first>=s[i]-d[i]) q.pop_back(); q.push_back({s[i]-d[i],i}); mnx=max(mnx,s[i]+d[i]+c-mid+x); mxx=min(mxx,s[i]-d[i]-c+mid+y); mny=max(mny,x+c-mid-s[i]+d[i]); mxy=min(mxy,y-c+mid-s[i]-d[i]); } int tmp=0,j=n,ch=0; for (int i=0;i<n;i++){ long long l=max(mnx-s[i],s[i]-mxy); if (mnx-s[i]<s[i]-mxy&&!tmp){ j=0; tmp=1; } if (tmp) while (j<n&&s[j]<l) j++; else{ while (j>=0&&s[j]>=l) j--; j++; } if (j<n&&s[j]<=min(mxx-s[i],s[i]-mny)){ ch=1; break; } } if (ch){ kq=mid; hi=mid-1; } else lo=mid+1; } return kq; }
#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...