Submission #1019801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019801		huutuan	Shortcut (IOI16_shortcut)	C++14	0 / 100	5 ms	600 KiB

shortcut

#include "shortcut.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

mt19937 rng(69420);

int rand(int l, int r){
   return uniform_int_distribution<int>(l, r)(rng);
}

const int N=4000, inf=1e18, LG=12;
int n, c, pf[N], w[N], d[N];
pair<int, int> st1[LG][N], st2[LG][N];

pair<int, int> get1(int l, int r){
   if (l>r) return {-inf, -1};
   int lg=__lg(r-l+1);
   return max(st1[lg][l], st1[lg][r-(1<<lg)+1]);
}

pair<int, int> get2(int l, int r){
   if (l>r) return {-inf, -1};
   int lg=__lg(r-l+1);
   return max(st2[lg][l], st2[lg][r-(1<<lg)+1]);
}

long long find_shortcut(int32_t _n, vector<int32_t> _l, vector<int32_t> _d, int32_t _c)
{
   n=_n, c=_c;
   for (int i=0; i<n-1; ++i) w[i]=_l[i];
   for (int i=0; i<n; ++i) d[i]=_d[i];
   for (int i=1; i<n; ++i) pf[i]=pf[i-1]+w[i-1];
   for (int i=0; i<n; ++i) st1[0][i]={d[i]+pf[i], i};
   for (int i=0; i<n; ++i) st2[0][i]={d[i]-pf[i], i};
   for (int k=1; k<LG; ++k) for (int i=0; i+(1<<k)-1<n; ++i){
      st1[k][i]=max(st1[k-1][i], st1[k-1][i+(1<<(k-1))]);
      st2[k][i]=max(st2[k-1][i], st2[k-1][i+(1<<(k-1))]);
   }
   int mxd=*max_element(d, d+n);
   int ans=inf;
   for (int i=0; i<n; ++i){
      for (int j=i, mid1=i, mid2=i; j<n; ++j){
         while (mid1<=j && (pf[mid1]-pf[i])*2<c+pf[j]-pf[i]) ++mid1;
         while (mid2<=j && (pf[j]-pf[mid2])*2>=c+pf[j]-pf[i]) ++mid2;
         auto find_dist=[&](int u){
            pair<int, int> mx={0, u}, tmp;
            if (0<=u && u<i){
               tmp=get2(0, u-1); tmp.first+=d[u]+pf[u];
               mx=max(mx, tmp);
               tmp=get1(u+1, mid1-1); tmp.first+=d[u]-pf[u];
               mx=max(mx, tmp);
               tmp=get2(mid1, j); tmp.first+=d[u]+pf[i]-pf[u]+c+pf[j];
               mx=max(mx, tmp);
               tmp=get1(j+1, n-1); tmp.first+=d[u]-pf[u]+min(0ll, c-(pf[j]-pf[i]));
               mx=max(mx, tmp);
            }else if (i<=u && u<=j){
               tmp=get2(0, i-1); tmp.first+=d[u]+pf[i]+min(pf[j]-pf[u]+c, pf[u]-pf[i]);
               mx=max(mx, tmp);
               tmp=get1(j+1, n-1); tmp.first+=d[u]-pf[j]+min(pf[j]-pf[u], pf[u]-pf[i]+c);
               mx=max(mx, tmp);
               int l1=pf[u]-pf[i]; int l2=pf[j]-pf[u];
               int sum=pf[j]-pf[i]+c;
               if (l1*2<=c){
                  tmp=get2(i, u-1); tmp.first+=d[u]+pf[u];
                  mx=max(mx, tmp);
               }else{
                  int l=i, r=u-1;
                  while (l<=r){
                     int mid=(l+r)>>1;
                     if ((pf[u]-pf[mid])*2>sum) l=mid+1;
                     else r=mid-1;
                  }
                  tmp=get2(l, u-1); tmp.first+=d[u]+pf[u];
                  mx=max(mx, tmp);
                  tmp=get1(i, r); tmp.first+=d[u]+pf[j]-pf[u]+c-pf[i];
                  mx=max(mx, tmp);
               }
               if (l2*2<=c){
                  tmp=get1(u+1, j); tmp.first+=d[u]-pf[u];
                  mx=max(mx, tmp);
               }else{
                  int l=u+1, r=j;
                  while (l<=r){
                     int mid=(l+r)>>1;
                     if ((pf[mid]-pf[u])*2>sum) r=mid-1;
                     else l=mid+1;
                  }
                  tmp=get1(u+1, r); tmp.first+=d[u]-pf[u];
                  mx=max(mx, tmp);
                  tmp=get2(l, j); tmp.first+=d[u]+pf[u]-pf[i]+c+pf[j];
                  mx=max(mx, tmp);
               }
            }else{
               tmp=get2(0, i); tmp.first+=d[u]+pf[u]+min(0ll, c-(pf[j]-pf[i]));
               mx=max(mx, tmp);
               tmp=get1(i, mid2-1); tmp.first+=d[u]+pf[u]-pf[j]+c-pf[i];
               mx=max(mx, tmp);
               tmp=get2(mid2, u-1); tmp.first+=d[u]+pf[u];
               mx=max(mx, tmp);
               tmp=get1(u+1, n-1); tmp.first+=d[u]-pf[u];
               mx=max(mx, tmp);
            }
            return mx;
         };
         int u=0;
         int cur=0;
         for (int i=0; i<10; ++i){
            u=rand(0, n-1);
            for (int i=0; i<2; ++i){
               auto t=find_dist(u);
               cur=max(cur, t.first);
               u=t.second;
            }
         }
         ans=min(ans, max(cur, mxd));
      }
   }
   return ans;
}

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