Submission #637251

#	Time	Username	Problem	Language	Result	Execution time	Memory
637251		ggoh	Shortcut (IOI16_shortcut)	C++14	97 / 100	2039 ms	111896 KiB

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<int> D, int c)
{
    vector<lint>d;
    for(int i=0;i<n;i++)d.push_back(D[i]);
    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;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 22 / 22
• Subtask 7: 4 / 4
• Subtask 8: 0 / 3