Submission #637249

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
637249	2022-09-01T07:18:46 Z	ggoh	Shortcut (IOI16_shortcut)	C++14	Compilation error	0 ms	0 KB

shortcut

#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

/usr/bin/ld: /tmp/ccEKPcoA.o: in function `main':
grader.cpp:(.text.startup+0x124): undefined reference to `find_shortcut(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int)'
collect2: error: ld returned 1 exit status