Submission #1256306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256306		biank	Shortcut (IOI16_shortcut)	C++20	100 / 100	1244 ms	39528 KiB

shortcut

#include <bits/stdc++.h>

using namespace std;

#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;

#define fst first
#define snd second

#define pb push_back
#define eb emplace_back

const ll INF = 1e18;

const int MAX_N = 1e6 + 9;

ll x[MAX_N], d[MAX_N];
int n, c;

int order[2][MAX_N];

ll val(int i, int t) {
    if (i == -1) return -INF;
    if (t == 0) return x[i] + d[i];
    if (t == 1) return -x[i] + d[i];
    assert(false);
}

pll intersection(pll a, pll b) {
    return pll{max(a.fst, b.fst), min(a.snd, b.snd)};
}

void upd(ii &a, int i, int t) {
    if (val(i, t) > val(a.fst, t)) {
        a.snd = a.fst;
        a.fst = i;
    } else if (val(i, t) > val(a.snd, t)) {
        a.snd = i;
    }
}

bool check(ll R) {
    int idx = n - 1;
    ii best[2] = {{-1, -1}, {-1, -1}};
    pll rangeSum = {-INF, INF}, rangeDiff = {-INF, INF};
    auto consider = [&](int i, int j) {
        if (i > j) swap(i, j);
        if (i == -1) return;
        ll v = R - c - d[i] - d[j];
        rangeSum = intersection(rangeSum, make_pair(x[i] + x[j] - v, 
                                                    x[i] + x[j] + v));
        rangeDiff = intersection(rangeDiff, make_pair(x[j] - x[i] - v,
                                                      x[j] - x[i] + v));
    };
    forn(i, n) {
        while (idx >= 0 && val(order[1][idx], 1) > R - val(order[0][i], 0)) {
            forn(j, 2) upd(best[j], order[1][idx], j);
            idx--;
        }
        forn(j, 2) {
            int k = best[j].fst;
            if (k == order[0][i]) k = best[j].snd;
            consider(order[0][i], k); 
        }
    }
    if (rangeDiff.fst > rangeDiff.snd || rangeSum.fst > rangeSum.snd) return false;
    int j = n, k = 0;
    forn(i, n) {
        while (j > 0 && x[i] + x[j - 1] >= rangeSum.fst) j--;
        while (k < n && x[k] - x[i] < rangeDiff.fst) k++;
        int candidate = max({j, k, i + 1});
        if (candidate < n && rangeDiff.fst <= x[candidate] - x[i] && x[candidate] - x[i] <= rangeDiff.snd &&
            rangeSum.fst <= x[i] + x[candidate] && x[i] + x[candidate] <= rangeSum.snd) {
            return true;
        }
    }
    return false;
}

ll find_shortcut(int _n, vi l, vi _d, int _c) {
    n = _n, c = _c;
    x[0] = 0LL;
    forn(i, n - 1) x[i + 1] = x[i] + l[i];
    forn(i, n) d[i] = _d[i];
    forn(j, 2) forn(i, n) order[j][i] = i;
    forn(j, 2) sort(order[j], order[j] + n, [&](const int &lhs, const int &rhs) {
        return val(lhs, j) < val(rhs, j);
    });
    ll lo = 0, hi = x[n - 1] + int(2e9 + 20);
    while (hi - lo > 1) {
        ll mid = (lo + hi) / 2;
        if (check(mid)) hi = mid;
        else lo = mid;
    }
    return hi;
}

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