Submission #502917

#	Time	Username	Problem	Language	Result	Execution time	Memory
502917		doowey	Shortcut (IOI16_shortcut)	C++14	71 / 100	2062 ms	7008 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 Q[4][2];
void upd(int id, int mode, pii V){
    if(mode == false){ // max
        if(Q[id][0] < V){
            Q[id][1] = Q[id][0];
            Q[id][0] = V;
        }
        else if(Q[id][1] < V){
            Q[id][1] = V;
        }
    }
    else{
        if(Q[id][0] > V){
            Q[id][1] = Q[id][0];
            Q[id][0] = V;
        }
        else{
            Q[id][1] = V;
        }
    }
}

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]);
        }
    }
    */
    Q[0][0] = Q[0][1] = mp(-(ll)1e18, -1);
    Q[1][0] = Q[1][1] = mp((ll)1e18, -1);
    Q[2][0] = Q[2][1] = mp(-(ll)1e18, -1);
    Q[3][0] = Q[3][1] = mp((ll)1e18, -1);
    int pi = 0;
    int i,j;
    ll extra;
    ll H[4];
    for(int ii = 0 ; ii < n; ii ++ ){
        H[0] =  -(ll)1e18;
        H[1] = (ll)1e18;
        H[2] = -(ll)1e18;
        H[3] = (ll)1e18;
        j = A[ii].se;
        for(int jj = 0 ; jj < n; jj ++ ){
            if(A[ii].fi - B[jj].fi <= k) break;
            if(A[ii].se == B[jj].se) continue;
            i = B[jj].se;
            H[0] = max(H[0], X[i] + W[i]);
            H[1] = min(H[1], X[i] - W[i]);
            H[2] = max(H[2], X[i] + W[i]);
            H[3] = min(H[3], X[i] - W[i]);
        }
        lowplus = max(lowplus, -k + H[0] + X[j] + L  + W[j]);
        highplus = min(highplus, k + H[1] + X[j] - L - W[j]);
        lowminus = max(lowminus, -k + H[0] - X[j] + L + W[j]);
        highminus = min(highminus, k + H[1] - X[j] - L - W[j]);
        /*
        while(pi < n && A[i].fi - B[pi].fi > k){
            upd(0, false, mp(X[B[pi].se] + W[B[pi].se], B[pi].se));
            upd(1, true,  mp(X[B[pi].se] - W[B[pi].se], B[pi].se));
            upd(2, false, mp(X[B[pi].se] + W[B[pi].se], B[pi].se));
            upd(3, true,  mp(X[B[pi].se] - W[B[pi].se], B[pi].se));
            pi ++ ;
        }
        j = A[i].se;

        if(j == Q[0][0].se) extra = Q[0][1].fi;
        else extra = Q[0][0].fi;
        lowplus = max(lowplus, -k + X[j] + L + W[j] + extra);

        if(j == Q[1][0].se) extra = Q[1][1].fi;
        else extra = Q[1][0].fi;
        highplus = min(highplus, k + X[j] - L - W[j] + extra);

        if(j == Q[2][0].se) extra = Q[2][1].fi;
        else extra = Q[2][0].fi;
        lowminus = max(lowminus, -k - X[j] + L + W[j] + extra);

        if(j == Q[3][0].se) extra = Q[3][1].fi;
        else extra = Q[3][0].fi;
        highminus = min(highminus, k - X[j] - L - W[j] + extra);
        */

    }
    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());
    L = _c;
    ll li = 0;
    ll ri = (ll)1e16;
    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:69:9: warning: unused variable 'pi' [-Wunused-variable]
   69 |     int pi = 0;
      |         ^~
shortcut.cpp:71:8: warning: unused variable 'extra' [-Wunused-variable]
   71 |     ll extra;
      |        ^~~~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3