Submission #502927

#	Time	Username	Problem	Language	Result	Execution time	Memory
502927		doowey	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	332 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;

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 = 0;
    int i,j;
    ll extra;
    ll H[2];
    pii P0, P1;
    P0 = P1 = mp(-(ll)1e18, -1);
    pii M0, M1;
    M0 = M1 = mp((ll)1e18, -1);
    for(int ii = 0 ; ii < n; ii ++ ){
        //H[0] =  -(ll)1e18;
        //H[1] = (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]);
        }

        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){
            i = B[pi].se;
            if(mp(X[i] + W[i], i) > P0){
                P1 = P0;
                P0 = mp(X[i] + W[i], i);
            }
            else if(mp(X[i] + W[i], i) > P1){
                P1 = mp(X[i] + W[i], i);
            }
            if(mp(X[i] - W[i], i) < M0){
                M1 = M0;
                M0 = mp(X[i] - W[i], i);
            }
            else if(mp(X[i] - W[i], i) < M1){
                M1 = mp(X[i] - W[i], i);
            }
            pi ++ ;
        }
        if(j == P0.se) i = P1.se;
        else i = P0.se;
        if(i != -1){
            lowplus = max(lowplus, -k + X[i] + W[i] + X[j] + L  + W[j]);
            lowminus = max(lowminus, -k + X[i] + W[i] - X[j] + L + W[j]);
        }
        if(j == M0.se) i = M1.se;
        else i = M0.se;
        if(i != -1){
            highplus = min(highplus, k + X[i] - W[i] + X[j] - L - W[j]);
            highminus = min(highminus, k + X[i] - W[i] - 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());
    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:45:8: warning: unused variable 'extra' [-Wunused-variable]
   45 |     ll extra;
      |        ^~~~~
shortcut.cpp:46:8: warning: unused variable 'H' [-Wunused-variable]
   46 |     ll H[2];
      |        ^
shortcut.cpp:70:28: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |         while(pi < n && A[i].fi - B[pi].fi > k){
      |                            ^

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