Submission #697416

#	Time	Username	Problem	Language	Result	Execution time	Memory
697416		qwerasdfzxcl	Shortcut (IOI16_shortcut)	C++17	100 / 100	1832 ms	95084 KiB

shortcut

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

using namespace std;
typedef long long ll;
constexpr ll INF = 1e17;
struct Square{
    ll lm, um, lp, up;

    Square(){lm = lp = -INF, um = -1, up = INF;}

    void update(ll x, ll y, ll r){
        lm = max(lm, x-y-r);
        um = min(um, x-y+r);
        lp = max(lp, x+y-r);
        up = min(up, x+y+r);
    }
    void update(ll x, ll r, Square &S){
        lm = max(lm, x-r + S.lm);
        um = min(um, x+r + S.um);
        lp = max(lp, x-r + S.lp);
        up = min(up, x+r + S.up);
    }

    bool valid(){return lm <= um && lp <= up;}
};

int n, I1[1001000], I2[1001000], chk[1001000];
ll X[1001000], a[1001000], c[1001000], d;
vector<int> L, R;
vector<pair<ll, ll>> ran;

bool ok(ll MX){
    fill(chk, chk+n+1, 0);

    ll mx = -INF;
    L.clear(); R.clear();

    for (int i=1;i<=n;i++){
        if (mx + X[i] + c[i] > MX) chk[i] |= 2;
        mx = max(mx, - X[i] + c[i]);
    }
    mx = -INF;
    for (int i=n;i;i--){
        if (mx - X[i] + c[i] > MX) chk[i] |= 1;
        if (chk[i]==3) return 0;
        mx = max(mx, X[i] + c[i]);
    }

    for (int i=1;i<=n;i++) if (chk[I1[i]]&1) L.push_back(I1[i]);
    for (int i=1;i<=n;i++) if (chk[I2[i]]&2) R.push_back(I2[i]);

    if (L.empty()) return 1;
    int b = *max_element(L.begin(), L.end());

    for (auto &i:L) a[i] = c[i] + (X[b] - X[i]);
    for (auto &j:R) a[j] = c[j] + (X[j] - X[b]);

    int pt = 0;
    Square s, js;

    for (auto &i:L){
        while(pt<(int)R.size() && a[i] + a[R[pt]] > MX){
            js.update(0, X[R[pt]], -c[R[pt]]);
            pt++;
        }

        s.update(X[i], MX - c[i] - d, js);
        if (!s.valid()) return 0;
    }

    ran.clear();
    for (int i=1;i<=n;i++){
        ran.emplace_back(max(s.lp-X[i], X[i]-s.um), min(s.up-X[i], X[i]-s.lm));
        if (ran.back().first > ran.back().second) ran.pop_back();
    }
    if (ran.empty()) return 0;

    for (int i=0;i<(int)ran.size();i++) if ((i==(int)ran.size()-1) || ran[i].first < ran[i+1].first){
        reverse(ran.begin(), ran.begin()+i+1);
        inplace_merge(ran.begin(), ran.begin()+i+1, ran.end());
        break;
    }

    ll ss = 0, ee = 0;
    pt = 2;
    for (auto &[l, r]:ran){
        if (l <= ee) {ee = max(ee, r); continue;}
        while(pt<=n && X[pt] <= ee){
            if (X[pt] >= ss) return 1;
            ++pt;
        }

        ss = l, ee = r;
    }
    while(pt<=n && X[pt] <= ee){
        if (X[pt] >= ss) return 1;
        ++pt;
    }

    return 0;
}

bool cmp1(int i, int j){return -X[i]+c[i] < -X[j]+c[j];}
bool cmp2(int i, int j){return X[i]+c[i] > X[j]+c[j];}

ll naive(int N, std::vector<int> L, std::vector<int> D, int C){
    ll ans = INF;
    for (int i=1;i<N;i++) X[i] = X[i-1] + L[i-1];
    for (int i=0;i<N;i++){
        for (int j=i+1;j<N;j++){
            ll mx = *max_element(D.begin(), D.end());
            for (int s=0;s<N;s++){
                for (int e=s+1;e<N;e++){
                    mx = max(mx, min(X[e] - X[s], min(abs(X[j]-X[e]) + abs(X[i]-X[s]) + C, abs(X[j]-X[s]) + abs(X[i] - X[e]) + C)) + D[s] + D[e]);
                }
            }

            ans = min(ans, mx);
        }
    }
    return ans;
}

long long find_shortcut(int N, std::vector<int> L, std::vector<int> D, int C){
    //ll rans = naive(N, L, D, C);
    L.reserve(N+100);
    R.reserve(N+100);
    ran.reserve(N+100);

    n = N;
    X[1] = 0;
    for (int i=1;i<=n;i++) c[i] = D[i-1];
    for (int i=2;i<=n;i++) X[i] = X[i-1] + L[i-2];
    d = C;

    for (int i=1;i<=n;i++) I1[i] = i, I2[i] = i;
    sort(I1+1, I1+n+1, cmp1);
    sort(I2+1, I2+n+1, cmp2);

    ll l = *max_element(c+1, c+n+1), r = 1e15 + 100, ans = 1e15 + 100;
    while(l<=r){
        ll mid = (l+r)/2;
        if (ok(mid)) r = mid-1, ans = mid;
        else l = mid+1;
    }

    //printf("Answer: %lld\n", rans);
    //printf("Output: %lld\n", ans);
    //assert(ans == rans);
    return ans;
}

• 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