Submission #1296528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296528		Namnamseo	Shortcut (IOI16_shortcut)	C++17	93 / 100	2093 ms	46828 KiB

shortcut

#include <algorithm>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
using ll=long long;
using pll=pair<ll,ll>;

const int maxn = int(1e6) + 10;
const ll inf = ll(4e15);

int n; ll L;
ll P[maxn], D[maxn], A[maxn], B[maxn];

const int M = 1048576;

pll sortedBwithIdx[maxn];
ll sortedB[maxn];
int sortedBrev[maxn];

pll emax(pll a, pll b) { return {max(a.first, b.first), max(a.second, b.second)}; }

pll tree[M<<1];
char timestamp[M<<1]; char nowt;
pll range_max(int l, int r) {
    pll ans(-inf, -inf);
    for (l+=M, r+=M; l<=r; l/=2, r/=2) {
        if (l%2 == 1) {
            if (timestamp[l] == nowt) ans = emax(ans, tree[l]);
            ++l;
        }
        if (r%2 == 0) {
            if (timestamp[r] == nowt) ans = emax(ans, tree[r]);
            --r;
        }
    }
    return ans;
}

bool can_satisfy(ll V) {
    ll plus_min = -inf, plus_max = inf;
    ll minus_min = -inf, minus_max = inf;

    ++nowt;
    for (int j=0; j<n; ++j) {
        auto [maxAi, maxBi] = range_max(
            int(upper_bound(sortedB, sortedB+n, V-A[j])-sortedB),
            n-1);

        plus_min = max(plus_min, maxAi + A[j] - V + L);
        plus_max = min(plus_max, V - L - maxBi - B[j]);
        minus_min = max(minus_min, maxAi + B[j] - V + L);
        minus_max = min(minus_max, V - L - maxBi - A[j]);

        { int p = M+sortedBrev[j]; tree[p] = {A[j], B[j]}; timestamp[p] = nowt;
        for (p/=2; p; p/=2) {
            if (timestamp[p*2] != nowt) tree[p*2] = {-inf, -inf}, timestamp[p*2] = nowt;
            if (timestamp[p*2+1] != nowt) tree[p*2+1] = {-inf, -inf}, timestamp[p*2+1] = nowt;
            tree[p] = emax(tree[p*2], tree[p*2+1]);
            timestamp[p] = nowt;
        } }
    }

    set<ll> px;
    for (int y=0; y<n; ++y) {
        ll pxmin = max(plus_min - P[y], minus_min + P[y]);
        ll pxmax = min(plus_max - P[y], minus_max + P[y]);
        auto it = px.lower_bound(pxmin);
        if (it != px.end() && (*it) <= pxmax) return true;
        px.insert(P[y]);
    }

    return false;
}

void prepare() {
    for (int i=0; i<n; ++i) sortedBwithIdx[i] = {B[i], i};
    sort(sortedBwithIdx, sortedBwithIdx+n);
    for (int i=0; i<n; ++i) {
        sortedBrev[sortedBwithIdx[i].second] = i;
        sortedB[i] = sortedBwithIdx[i].first;
    }
}

ll find_shortcut(int n_, vector<int> l, vector<int> d, int c) {
    n = n_; L = c;
    copy(d.begin(), d.end(), D);
    for (int i=1; i<n; ++i) P[i] = P[i-1] + l[i-1];
    for (int i=0; i<n; ++i) A[i] = D[i] + P[i], B[i] = D[i] - P[i];

    prepare();

    ll left = 0, right = inf;
    while (left + 1 < right) {
        ll md = (left + right) / 2;
        (can_satisfy(md) ? right : left) = md;
    }

    return right;
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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: 0 / 4
• Subtask 8: 0 / 3