#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<lint,lint> pii;
lint INF=2e15,L[1000003];
int u[1000003];
int ch;
lint p,q,h,maxi[1000003][2],mini[1000003][2],mx,mn;
lint find_shortcut(int n, vector<int> l, vector<lint> d, int c)
{
for(int i=1;i<n;i++)L[i]=L[i-1]+l[i-1];
vector<pair<lint,int>>S,T;
for(int i=0;i<n;i++){
S.push_back({d[i]-L[i],i});
T.push_back({d[i]+L[i],i});
}
sort(S.begin(),S.end());
sort(T.begin(),T.end());
p=q=0;
h=-INF;
for(int i=0;i<n;i++)
{
q=max(q,d[i]+L[i]+h);
h=max(h,d[i]-L[i]);
}
while(p!=q-1)
{
h=(p+q)/2;
ch=0;
pii x={-INF,INF},y={-INF,INF};
int ind=n;
for(int i=0;i<n;i++)
{
while(ind-1>=0 && h-T[i].first<S[ind-1].first)ind--;
u[T[i].second]=ind;
}
maxi[n][0]=maxi[n][1]=n;
mini[n][0]=mini[n][1]=n;
d.push_back(-INF)//d[n]=-INF
for(int k=n-1;k>=0;k--)
{
int i=S[k].second;
maxi[k][0]=maxi[k+1][0];
maxi[k][1]=maxi[k+1][1];
if(L[maxi[k][0]]+d[maxi[k][0]]<=L[i]+d[i])
{
maxi[k][1]=maxi[k][0];
maxi[k][0]=i;
}
else if(L[maxi[k][1]]+d[maxi[k][1]]<L[i]+d[i])
{
maxi[k][1]=i;
}
mini[k][0]=mini[k+1][0];
mini[k][1]=mini[k+1][1];
if(L[mini[k][0]]-d[mini[k][0]]>=L[i]-d[i])
{
mini[k][1]=mini[k][0];
mini[k][0]=i;
}
else if(L[mini[k][1]]-d[mini[k][1]]>L[i]-d[i])
{
mini[k][1]=i;
}
}
for(int j=0;j<n;j++)
{
if(j!=maxi[u[j]][0])mx=L[maxi[u[j]][0]]+d[maxi[u[j]][0]];
else mx=L[maxi[u[j]][1]]+d[maxi[u[j]][1]];
if(j!=mini[u[j]][0])mn=L[mini[u[j]][0]]-d[mini[u[j]][0]];
else mn=L[mini[u[j]][1]]-d[mini[u[j]][1]];
x.first=max(x.first,mx-h+d[j]+c-L[j]);
x.second=min(x.second,mn+h-d[j]-c-L[j]);
y.first=max(y.first,mx-h+d[j]+c+L[j]);
y.second=min(y.second,mn+h-d[j]-c+L[j]);
if(x.first>x.second || y.first>y.second)break;
}
if(x.first<=x.second && y.first<=y.second){
int x0=0,x1=-1,y0=n,y1=n-1;
for(int j=0;j<n;j++)
{
while(x0<n && x.first+L[j]>L[x0])x0++;
while(x1+1<n && x.second+L[j]>=L[x1+1])x1++;
while(y0-1>=0 && y.first-L[j]<=L[y0-1])y0--;
while(y1>=0 && y.second-L[j]<L[y1])y1--;
if(x0<=x1 && y0<=y1 && x1<j && y1<j && !(x0>y1 || y0>x1))ch=1;
}
}
if(ch)q=h;
else p=h;
}
return q;
}
Compilation message
shortcut.cpp: In function 'lint find_shortcut(int, std::vector<int>, std::vector<long long int>, int)':
shortcut.cpp:42:24: error: expected ';' before 'for'
42 | d.push_back(-INF)//d[n]=-INF
| ^
| ;
43 | for(int k=n-1;k>=0;k--)
| ~~~
shortcut.cpp:43:21: error: 'k' was not declared in this scope
43 | for(int k=n-1;k>=0;k--)
| ^
