Submission #637236

#	Time	Username	Problem	Language	Result	Execution time	Memory
637236		ggoh	Shortcut (IOI16_shortcut)	C++14	97 / 100	2036 ms	92532 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],fenmax[1000003],B;
int to[1000003],u[1000003];
int ch;
lint getmax(int i){
  lint ans=-INF;
  while(i>0)
  {
    ans=max(ans,fenmax[i]);
    i -= (i & -i);
  }
  return ans;
}
void update(int i, lint v) {
    while (i <= B) {
        fenmax[i] =max(fenmax[i],v);
        i += (i & -i);
    }
}

lint find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
    for(int i=1;i<n;i++)L[i]=L[i-1]+l[i-1];
    lint p,q,h,maxi,mini;
    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());
    for(int i=0;i<n;i++){
      to[S[i].second]=i;
    }
    B=n;

    p=q=0;
    maxi=-INF;
    mini=-INF;
    for(int i=0;i<n;i++)
    {
      p=max(p,d[i]+mini);
      q=max(q,d[i]+L[i]+maxi);
      maxi=max(maxi,d[i]-L[i]);
      if(mini<d[i])mini=d[i];
    }
    while(p!=q-1)
    {
      h=(p+q)/2;
      ch=0;
      pii x={-INF,INF},y={-INF,INF};
      for(int i=1;i<=n;i++)fenmax[i]=-INF;
      int maxind=-1,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;
      }
      for(int j=0;j<n;j++)
      {
        int i=u[j];
        if(i<=maxind)
        {
          maxi=getmax(n-i)-h+d[j]+c;
          mini=-S[maxind].first+h-d[j]-c;
          x.first=max(x.first,maxi-L[j]);
          x.second=min(x.second,mini-L[j]);
          y.first=max(y.first,maxi+L[j]);
          y.second=min(y.second,mini+L[j]);
          if(x.first>x.second || y.first>y.second)break;
        }
        update(n-to[j],L[j]+d[j]);
        maxind=max(maxind,to[j]);
      }
      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<j && x.first+L[j]>L[x0])x0++;
          while(x1+1<j && 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