Submission #901526

#TimeUsernameProblemLanguageResultExecution timeMemory
901526abcvuitunggioShortcut (IOI16_shortcut)C++17
93 / 100
2047 ms43196 KiB
#include "shortcut.h" #include <bits/stdc++.h> #define T pair <long long, long long> using namespace std; const long long INF=1LL<<51; const int mxn=1000001; long long s[mxn]; int d[mxn],idx[mxn],order[mxn]; T st[mxn*4]; vector <long long> v; T operator +(T a, T b){ return {max(a.first,b.first),min(a.second,b.second)}; } void update(int node, int l, int r, int i){ if (l==r){ st[node]={s[l]+d[l],s[l]-d[l]}; return; } int mid=(l+r)>>1; if (mid<i) update(node<<1|1,mid+1,r,i); else update(node<<1,l,mid,i); st[node]=st[node<<1]+st[node<<1|1]; } T get(int node, int l, int r, int u, int v){ if (l>v||r<u||l>r||u>v||!node) return {-INF,INF}; if (l>=u&&r<=v) return st[node]; int mid=(l+r)>>1; return get(node<<1,l,mid,u,v)+get(node<<1|1,mid+1,r,u,v); } long long find_shortcut(int n, vector <int> l, vector <int> D, int c){ for (int i=0;i<n;i++) d[i]=D[i]; for (int i=1;i<n;i++){ s[i]=s[i-1]+l[i-1]; v.push_back(s[i]); } s[n]=INF; sort(v.begin(),v.end()); iota(idx,idx+n,0); iota(order,order+n,0); sort(idx,idx+n,[](int i, int j){return s[i]+d[i]>s[j]+d[j];}); sort(order,order+n,[](int i, int j){return s[i]-d[i]>s[j]-d[j];}); long long lo=0,hi=INF,kq=-1; while (lo<=hi){ long long mid=(lo+hi)>>1,ch=0,mnx=-INF,mxx=INF,mny=-INF,mxy=INF; int pos=0; for (int i=1;i<=n*4;i++) st[i]={-INF,INF}; for (int j=0;j<n;j++){ int i=order[j]; while (pos<n&&s[idx[pos]]+d[idx[pos]]>s[i]-d[i]+mid){ update(1,0,n-1,idx[pos]); pos++; } T t=get(1,0,n-1,i+1,n-1); mnx=max(mnx,s[i]+d[i]+c-mid+t.first); mxx=min(mxx,s[i]-d[i]-c+mid+t.second); mny=max(mny,s[i]+d[i]+c-mid-t.second); mxy=min(mxy,s[i]-d[i]-c+mid-t.first); } int tmp=0,j=n; for (int i=0;i<n;i++){ long long l=max(mnx-s[i],s[i]-mxy),r=min(mxx-s[i],s[i]-mny); 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]<=r){ 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...