Submission #436495

#	Time	Username	Problem	Language	Result	Execution time	Memory
436495		79brue	Shortcut (IOI16_shortcut)	C++14	97 / 100	2088 ms	47280 KiB

shortcut

#include <algorithm>
#include "shortcut.h"

using namespace std;

typedef long long ll;

ll minCost(vector<int> &v){
    auto it = min_element(v.begin(), v.end());
    ll t1 = (it == v.begin() ? 1e18 : *min_element(v.begin(), it));
    ll t2 = (it == prev(v.end()) ? 1e18 : *min_element(next(it), v.end()));
    return *it + min(t1, t2);
}

inline ll min(ll x, ll y){
    return x < y ? x : y;
}

inline ll max(ll x, ll y){
    return x > y ? x : y;
}

int n;
ll cost;
ll arr[1000002];
ll loc[1000002];

ll vec[1000002];
ll vec2[1000002];
ll maxXpd, maxXpd2;

inline bool able(ll);

ll find_shortcut(int N, vector<int> l, vector<int> d, int C){
    n = N;
    for(int i=1; i<=n; i++) arr[i] = d[i-1];
    for(int i=2; i<=n; i++) loc[i] = loc[i-1] + l[i-2];
    cost = C;

    for(int i=1; i<=n; i++) vec[i] = vec2[i] = i;
    sort(vec+1, vec+n+1, [&](int a, int b){
        return arr[a] + loc[a] > arr[b] + loc[b];
    });
    sort(vec2+1, vec2+n+1, [&](int a, int b){
        return loc[a] - arr[a] > loc[b] - arr[b];
    });
    maxXpd = arr[vec[1]] + loc[vec[1]];
    maxXpd2 = arr[vec[2]] + loc[vec[2]];

    ll MIN = minCost(d), MAX = 1e18, ANS = 1e18;
    while(MIN <= MAX){
        ll MID = (MIN + MAX) / 2;
        if(able(MID)){
            ANS = MID;
            MAX = MID-1;
        }
        else MIN = MID+1;
    }
    return ANS;
}

inline bool able(ll X){
    ll minPlus = -1e18, maxPlus = 1e18;
    ll minMinus = -1e18, maxMinus = 1e18;

    int pnt = 1;
    ll minXmd = 1e18, minXmd2 = 1e18;
    int minXmdLoc = -1;
    for(int i=1; i<=n; i++){
        int x = vec2[i];
        while(pnt <= n && arr[vec[pnt]] + loc[vec[pnt]] > X + loc[x] - arr[x]){
            ll tmp = loc[vec[pnt]] - arr[vec[pnt]];
            if(minXmd2 > tmp){
                minXmd2 = tmp;
                if(minXmd > minXmd2){
                    swap(minXmd, minXmd2);
                    minXmdLoc = vec[pnt];
                }
            }
            pnt++;
        }

        if(pnt==1 || (pnt==2 && x==vec[1])) continue;
        ll tMax = (x==vec[1] ? maxXpd2 : maxXpd);
        ll tMin = (x==minXmdLoc ? minXmd2 : minXmd);
        maxPlus = min(maxPlus, loc[x] - arr[x] + X + tMin - cost);
        minPlus = max(minPlus, loc[x] + arr[x] - X + tMax + cost);
        maxMinus = min(maxMinus, -loc[x] - arr[x] + X + tMin - cost);
        minMinus = max(minMinus, -loc[x] + arr[x] - X + tMax + cost);
    }

    if(minPlus > maxPlus || minMinus > maxMinus) return false;

    pnt = 1;
    for(int i=1; i<=n; i++){
        ll llim = max(minPlus - loc[i], loc[i] - maxMinus);
        ll rlim = min(maxPlus - loc[i], loc[i] - minMinus);
        while(pnt <= n && llim > loc[pnt]) pnt++;
        while(pnt > 1 && llim <= loc[pnt-1]) pnt--;
        if(pnt <= n && loc[pnt] <= rlim) return true;
    }
    return false;
}

• 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