Submission #1013420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013420		hotboy2703	Shortcut (IOI16_shortcut)	C++17	100 / 100	1330 ms	61476 KiB

shortcut

#include "shortcut.h"

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))

const ll MAXN = 1e6+100;
const ll INF = 1e18;
ll x[MAXN];
ll d[MAXN];
ll c;
ll n;
bool check(ll k){
    ll suml,sumr,difl,difr;
    suml = difl = -INF;
    sumr = difr = +INF;
    ll msum,mdif;
    msum = -INF,mdif=INF;
    deque <ll> dq;
    for (ll i = 0;i < n;i ++){
        if (i && x[i] + d[i] - mdif > k){
//            if (k==50)cout<<"SUS"<<endl;
            while (sz(dq) && -(x[dq.front()] - d[dq.front()]) + x[i] + d[i] > k){
                msum = max(msum,x[dq.front()] + d[dq.front()]);
                dq.pop_front();
            }
            suml = max(suml,x[i]+d[i]+msum+c-k);
            sumr = min(sumr,x[i]-d[i]+mdif+k-c);
            difl = max(difl,x[i]+d[i]-mdif+c-k);
            difr = min(difr,x[i]-d[i]-msum+k-c);
        }
        mdif = min(mdif,x[i]-d[i]);
        while (sz(dq) && x[dq.back()] - d[dq.back()] >= x[i] - d[i])dq.pop_back();
        dq.push_back(i);
    }
//    if (k==50)cout<<suml<<' '<<sumr<<' '<<difl<<' '<<difr<<endl;
    ll Ls,Rs,Ld,Rd;
    Ls = n - 1,Rs = n - 1;
    Ld = 0,Rd = 0;
    for (ll i = 0;i < n;i ++){
        while (Ls && x[Ls] + x[i] >= suml)Ls--;
        while (Rs && x[Rs] + x[i] > sumr)Rs--;
        //Ls + 1 -> Rs
        while (Ld < n && x[Ld] - x[i] < difl)Ld++;
        while (Rd < n && x[Rd] - x[i] <= difr)Rd++;
        //Ld -> Rd - 1
        //z > y
        if (max({Ld,Ls+1,i+1}) <= min({Rs,Rd-1}))return 1;
    }
    return 0;
}
long long find_shortcut(int N, std::vector<int> L, std::vector<int> D, int C)
{
    n=N;
    c = C;
    for (ll i = 0;i < n;i ++)d[i] = D[i];
    x[0] = 0;
    for (ll i = 1;i < n;i ++)x[i] = x[i-1] + L[i-1];
    ll l = 0;
    ll r = 1e17;
    while (l <= r){
        ll mid = (l + r) >> 1;
        if (check(mid)){
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return l;
}

• 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