Submission #242029

#	Time	Username	Problem	Language	Result	Execution time	Memory
242029		lyc	Shortcut (IOI16_shortcut)	C++14	97 / 100	2088 ms	57356 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
using ll=long long;

const int mxN = 1e6+5;
const ll mxX = 1e17;

int N, C, D[mxN];
ll X[mxN];
int id1[mxN], id2[mxN];

bool check(ll k) {
    int i = 1;
    ll b[] = { -mxX, mxX, -mxX, mxX };  // min/max y+z, min/max y-z
    ll v[] = { -mxX, -mxX, mxX, mxX };  // max X[I]+D[i], min X[I]-D[I]
    int s[] = { -1, -1, -1, -1 };       // ids for v
    FOR(j,1,N){
        int I = id1[i], J = id2[j];
        while (i <= N && (X[J]+D[J])-(X[I]-D[I]) > k) {
            if (X[I]+D[I] > v[0]) v[0] = X[I]+D[I], s[0] = I;
            if (v[0] > v[1]) swap(v[0],v[1]), swap(s[0],s[1]);
            if (X[I]-D[I] < v[2]) v[2] = X[I]-D[I], s[2] = I;
            if (v[2] < v[3]) swap(v[2],v[3]), swap(s[2],s[3]);
            I = id1[++i];
        }
        b[0] = max(b[0], -k+C+(X[J]+D[J])+(J==s[1]?v[0]:v[1]));
        b[1] = min(b[1],  k-C+(X[J]-D[J])+(J==s[3]?v[2]:v[3]));
        b[2] = max(b[2], -k+C-(X[J]-D[J])+(J==s[1]?v[0]:v[1]));
        b[3] = min(b[3],  k-C-(X[J]+D[J])+(J==s[3]?v[2]:v[3]));
    }
    int l = 1, r = 0; // move only O(N) times
    FOR(i,1,N){
        while (l > 1 && X[l-1] >= max(b[0]-X[i],b[2]+X[i])) --l;
        while (r < N && X[r+1] <= min(b[1]-X[i],b[3]+X[i])) ++r;
        while (l <= N && X[l] < max(b[0]-X[i],b[2]+X[i])) ++l;
        while (r >= 1 && X[r] > min(b[1]-X[i],b[3]+X[i])) --r;
        if (l <= r) return 1; // found a shortcut
    }
    return 0;
}

ll find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    N = n, C = c;
    X[1] = 0;
    FOR(i,2,N) X[i] = X[i-1] + l[i-2];
    int mx = 0, smx = 0;
    FOR(i,1,N){
        D[i] = d[i-1];
        if (D[i] > smx) smx = D[i];
        if (smx > mx) swap(smx,mx);
    }

    FOR(i,1,N) id1[i] = id2[i] = i;
    sort(id1+1,id1+1+N,[](int a, int b){
            ll p = X[a]-D[a], q = X[b]-D[b];
            return (p == q ? a < b : p < q);
            });
    sort(id2+1,id2+1+N,[](int a, int b){
            ll p = X[a]+D[a], q = X[b]+D[b];
            return (p == q ? a < b : p < q);
            });
    ll lo = mx+smx-1, hi = mxX;
    while (hi-lo > 1){ 
        ll mid = (lo+hi)/2;
        if (check(mid)) hi = mid;
        else lo = mid;
    }
    return hi;
}

• 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