Submission #502939

#	Time	Username	Problem	Language	Result	Execution time	Memory
502939		doowey	Shortcut (IOI16_shortcut)	C++14	100 / 100	1546 ms	154496 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)1e6 + 10;

int n;
ll X[N];
vector<ll> W;
ll L;
vector<pii> A,B;
pii P0[N], P1[N];
pii M0[N], M1[N];

bool check(ll k){
    ll mx = 0;
    for(int i = 0 ; i < n; i ++ ){
        if(W[i] + mx > k) return false;
        mx = max(mx, W[i]);
    }
    ll lowplus = -(ll)1e18;
    ll highplus = (ll)1e18;
    ll lowminus = -(ll)1e18;
    ll highminus = (ll)1e18;
    /*
    for(int i = 0 ; i < n; i ++ ){
        for(int j = 0; j < n; j ++ ){
            if(i == j) continue;
            if(X[j] + W[j] - (X[i] - W[i]) <= k) continue; // no one cares
            lowplus = max(lowplus, -k + X[i] + X[j] + L + W[i] + W[j]);
            highplus = min(highplus, k + X[i] + X[j] - L - W[i] - W[j]);
            lowminus = max(lowminus, -k + X[i] - X[j] + L + W[i] + W[j]);
            highminus = min(highminus, k + X[i] - X[j] - L - W[i] - W[j]);
        }
    }
    */
    int pi = -1;
    int i,j;
    ll extra;
    ll Y[2];
    int las;
    for(int ii = 0 ; ii < n; ii ++ ){
        j = A[ii].se;
        while(pi + 1 < n && A[ii].fi - B[pi + 1].fi > k){
            pi ++ ;
        }
        if(pi >= 0){
            if(j == P0[pi].se) Y[0] = P1[pi].fi;
            else Y[0] = P0[pi].fi;
            if(j == M0[pi].se) Y[1] = M1[pi].fi;
            else Y[1] = M0[pi].fi;
            lowplus = max(lowplus, -k + Y[0] + X[j] + L  + W[j]);
            highplus = min(highplus, k + Y[1] + X[j] - L - W[j]);
            lowminus = max(lowminus, -k + Y[0] - X[j] + L + W[j]);
            highminus = min(highminus, k + Y[1] - X[j] - L - W[j]);
        }


    }
    int i0 = n - 1, j0 = n - 1;
    int i1 = 0, j1 = 0;
    int tl, tr;
    for(int i = 0 ; i < n; i ++ ){
        while(i0 >= 0 && X[i] + X[i0] > highplus){
            i0 -- ;
        }
        while(j0 > 0 && X[i] + X[j0 - 1] >= lowplus){
            j0 -- ;
        }
        while(i1 < n && X[i] - X[i1] > highminus){
            i1 ++ ;
        }
        while(j1 + 1 < n && X[i] - X[j1 + 1] >= lowminus){
            j1 ++ ;
        }
        tl = i + 1;
        tr = n - 1;
        tl = max(tl, j0);
        tr = min(tr, i0);
        tl = max(tl, i1);
        tr = min(tr, j1);
        if(tl <= tr){
            return true;
        }
    }
    return false;

}

ll find_shortcut(int _n, vector<int> l, vector<int> _d, int _c){
    n = _n;
    for(int i = 1; i < n; i ++ ){
        X[i] = X[i - 1] + l[i - 1];
    }
    for(auto x : _d)
        W.push_back(x);
    for(int i = 0 ; i < n; i ++ ){
        A.push_back(mp(X[i] + W[i], i));
        B.push_back(mp(X[i] - W[i] ,i));
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    pii PP0 = mp(-(ll)1e18, -1);
    pii PP1 = mp(-(ll)1e18, -1);
    pii MM0 = mp(+(ll)1e18, -1);
    pii MM1 = mp(+(ll)1e18, -1);
    int i;
    for(int ii = 0 ; ii < n; ii ++ ){
        i = B[ii].se;
        if(mp(X[i] + W[i], i) > PP0){
            PP1 = PP0;
            PP0 = mp(X[i] + W[i], i);
        }
        else if(mp(X[i] + W[i], i) > PP1){
            PP1 = mp(X[i] + W[i], i);
        }
        if(mp(X[i] - W[i], i) < MM0){
            MM1 = MM0;
            MM0 = mp(X[i] - W[i], i);
        }
        else if(mp(X[i] - W[i], i) < MM1){
            MM1 = mp(X[i] - W[i], i);
        }
        P0[ii] = PP0;
        P1[ii] = PP1;
        M0[ii] = MM0;
        M1[ii] = MM1;
    }

    L = _c;
    ll li = 0;
    ll ri = (ll)2e15;
    ll mid;
    while(li < ri){
        mid = (li + ri) / 2;
        if(check(mid)){
            ri = mid;
        }
        else{
            li = mid + 1;
        }
    }
    return li;
}

Compilation message (stderr)

shortcut.cpp: In function 'bool check(ll)':
shortcut.cpp:46:9: warning: unused variable 'i' [-Wunused-variable]
   46 |     int i,j;
      |         ^
shortcut.cpp:47:8: warning: unused variable 'extra' [-Wunused-variable]
   47 |     ll extra;
      |        ^~~~~
shortcut.cpp:49:9: warning: unused variable 'las' [-Wunused-variable]
   49 |     int las;
      |         ^~~

• 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