Submission #20797

#	Time	Username	Problem	Language	Result	Execution time	Memory
20797		ainta	Shortcut (IOI16_shortcut)	C++14	23 / 100	0 ms	431972 KiB

shortcut

#include "shortcut.h"
#include<stdio.h>
#include<algorithm>
#include<cstdlib>
#include<vector>
#define N_ 1010000
#define SZ 1048576
#define pll pair<long long, long long>
using namespace std;
int n, lower[N_];
long long LD[N_], RD[N_], S[N_], P[N_], IT1[N_][20], IT2[N_][20], TL;
long long LT[N_], RT[N_];
long long Max1(int b, int e){
    int t = lower[e-b+1];
    return max(IT1[b][t], IT1[e-(1<<t)+1][t]);
}
long long Max2(int b, int e){
    int t = lower[e-b+1];
    return max(IT2[b][t], IT2[e-(1<<t)+1][t]);
}
long long st[1010000][2];
struct point{
    long long a, b, num;
    bool operator<(const point &p)const{
        return a<p.a;
    }
}AA[N_], BB[N_];
long long LCalc(int b, int e, int mid){
    if(b==1)return 0;
    long long mm = Max1(b,mid);
    if(mid < e) mm = max(mm, Max2(mid+1,e) + TL + S[e] + S[b]);
    return mm + LT[b-1];
}
long long RCalc(int b, int e, int mid){
    if(e==n)return 0;
    long long mm = Max2(mid,e);
    if(mid > b) mm = max(mm, Max1(b,mid-1) + TL - S[e] - S[b]);
    return mm + RT[e+1];
}
bool Pos(long long d){
    if(LD[n]<=d)return true;
    int pv, ppv, i;
    long long ML = 1e18;
    long long Mx1 = -1e18, Mx2 = -1e18;
    int pv1 = -1, pv2 = -1;
    pv = n+1;
    for(i=1;i<=n;i++){
        while(pv>1 && BB[pv-1].a + AA[i].a > d){
            pv--;
            if(Mx1 < BB[pv].b){
                Mx2 = Mx1; pv2 = pv1;
                Mx1 = BB[pv].b, pv1 = BB[pv].num;
            }
            else if(Mx2 < BB[pv].b){
                Mx2 = BB[pv].b, pv2 = BB[pv].num;
            }
        }
        if(pv1 == AA[i].num) ML = min(ML, d - (Mx2 + AA[i].b));
        else ML = min(ML, d - (Mx1 + AA[i].b));
    }
    pv = pv1 = pv2 = 1;
    for(i=1;i<n;i++){
        if(LD[i] > d)return false;
        while(pv+1<=n && S[pv+1]-S[i]+TL <=ML)pv++;
        pv1=max(pv1,i);
        pv2=max(pv2,i);
        while(pv1 < pv && S[pv]-S[i]+TL >= (S[pv1+1]-S[i])*2)pv1++;
        while(pv2 < pv && S[pv]-S[i]+TL < (S[pv]-S[pv2])*2)pv2++;
        if(LCalc(i,pv,pv1) > d)break;
        if(RD[pv] <= d && RCalc(i,pv,pv2) <= d && LT[i] + RT[pv] - (S[pv]-S[i]) + TL <= d)return true;
    }
    for(;i<n;i++){
        if(LD[i]>d)return false;
        if(pv<=i)return false;
        while(pv>i && LCalc(i,pv,pv1)>d){
            pv--;
            if(pv<=i)return false;
            pv1=min(pv1,pv);
            if(pv1>pv)pv1=pv;
            while(pv1 < pv && S[pv]-S[i]+TL >= (S[pv1+1]-S[i])*2)pv1++;
            while(pv1 > i && S[pv]-S[i]+TL < (S[pv1]-S[i])*2)pv1--;
        }
        pv2=min(pv2,pv);
        while(pv2 < pv && S[pv]-S[i]+TL < (S[pv]-S[pv2])*2)pv2++;
        while(pv2 > i && S[pv]-S[i]+TL >= (S[pv]-S[pv2-1])*2)pv2--;
        if(RD[pv] <= d && RCalc(i,pv,pv2) <= d && LT[i] + RT[pv] - (S[pv]-S[i]) + TL <= d)return true;
    }
    return false;
}
long long find_shortcut(int N, vector<int> l, vector<int> d, int c)
{
    TL = c;
    n = N;
    int i, j;
    for(i=1;i<=n;i++){
        lower[i]=lower[i-1];
        if((1<<(lower[i]+1)) <= i)lower[i]++;
    }
    for(i=1;i<=n;i++){
        if(i!=1)S[i] = S[i-1] + l[i-2];
        P[i] = d[i-1];
    }
    long long mx = 0;
    for(i=1;i<=n;i++){
        LD[i] = max(LD[i-1], mx+S[i]+P[i]);
        mx = max(mx, P[i]-S[i]);
        LT[i] = mx;
    }
    mx = S[n];
    for(i=n;i>=1;i--){
        RD[i] = max(RD[i+1], mx-S[i]+P[i]);
        mx = max(mx, P[i]+S[i]);
        RT[i] = mx;
        IT1[i][0] = S[i]+P[i], IT2[i][0] = P[i]-S[i];
    }
    for(i=1;i<=n;i++){
        AA[i].a = S[i]+P[i], AA[i].b = P[i]-S[i], AA[i].num = i;
        BB[i].a = P[i]-S[i], BB[i].b = S[i]+P[i], BB[i].num = i;
    }
    sort(AA+1,AA+n+1);
    sort(BB+1,BB+n+1);
    for(i=0;i<19;i++){
        for(j=1;j<=n;j++){
            if(j+(1<<(i+1)) - 1 > n)continue;
            IT1[j][i+1] = max(IT1[j][i],IT1[j+(1<<i)][i]);
            IT2[j][i+1] = max(IT2[j][i],IT2[j+(1<<i)][i]);
        }
    }
    long long b = 0, e = LD[n], mid, res = 0;
    while(b<=e){
        mid = (b+e)/2;
        if(Pos(mid)){
            res = mid;
            e = mid - 1;
        }
        else b = mid + 1;
    }
    return res;
}

Compilation message (stderr)

shortcut.cpp: In function 'bool Pos(long long int)':
shortcut.cpp:42:13: warning: unused variable 'ppv' [-Wunused-variable]
     int pv, ppv, i;
             ^

• Subtask 1: 9 / 9
• Subtask 2: 14 / 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