Submission #20799

#	Time	Username	Problem	Language	Result	Execution time	Memory
20799		ainta	Shortcut (IOI16_shortcut)	C++14	100 / 100	1756 ms	88584 KiB

shortcut

#include "shortcut.h"
#include<stdio.h>
#include<algorithm>
#include<cstdlib>
#include<vector>
#define N_ 1010000
using namespace std;
int n, be[N_], ed[N_];
long long S[N_], P[N_], TL;
struct point{
    long long a, b;
    int num;
    bool operator<(const point &p)const{
        return a<p.a;
    }
}AA[N_], BB[N_];
bool Pos(long long d){
    int pv, i;
    long long b1 = -1e18, e1 = 1e18, b2 = -1e18, e2 = 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(AA[i].num == pv1) b1 = max(b1, AA[i].a + Mx2 + TL - d);
        else b1 = max(b1, AA[i].a + Mx1 + TL - d);
        if(pv <= n){
            if(AA[i].num == BB[n].num){
                if(pv < n) e1 = min(e1, -(AA[i].b + BB[n-1].a) + d - TL);
            }
            else e1 = min(e1, -(AA[i].b + BB[n].a) + d - TL);
        }
        if(AA[i].num == pv1) b2 = max(b2, AA[i].b + Mx2 + TL - d);
        else b2 = max(b2, AA[i].b + Mx1 + TL - d);
        if(pv <= n){
            if(AA[i].num == BB[n].num){
                if(pv < n) e2 = min(e2, -(AA[i].a + BB[n-1].a) + d - TL);
            }
            else e2 = min(e2, -(AA[i].a + BB[n].a) + d - TL);
        }
    }
    if(b1>e1 || b2>e2)return false;
    pv1 = n+1, pv2 = 1;
    for(i=1;i<=n;i++){
        while(pv1 > 1 && b1-S[i] <= S[pv1-1])pv1--;
        while(pv2 <= n && S[i]+b2 > S[pv2])pv2++;
        be[i] = max(pv2,pv1);
    }
    pv1 = n, pv2 = 0;
    for(i=1;i<=n;i++){
        while(pv1 && e1-S[i] < S[pv1])pv1--;
        while(pv2 < n && S[i]+e2 >= S[pv2+1])pv2++;
        ed[i] = min(pv2,pv1);
        if(ed[i] >= be[i] && (ed[i]!=i || be[i]!=i))return true;
    }
    return false;
}
long long find_shortcut(int N, vector<int> l, vector<int> d, int c)
{
    TL = c;
    n = N;
    int i;
    long long mx = 0;
    long long b = 0, e = 0, mid, res = 0;
    for(i=1;i<=n;i++){
        if(i!=1)S[i] = S[i-1] + l[i-2];
        P[i] = d[i-1];
        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;
        if(b<mx+P[i])b=mx+P[i];
        mx = max(mx,P[i]);
    }
    sort(AA+1,AA+n+1);
    sort(BB+1,BB+n+1);
    e = b+S[n];
    while(b<=e){
        mid = (b+e)/2;
        if(Pos(mid)){
            res = mid;
            e = mid - 1;
        }
        else b = mid + 1;
    }
    return res;
}

• 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: 3 / 3