Submission #1296499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296499		Namnamseo	Shortcut (IOI16_shortcut)	C++17	93 / 100	2096 ms	28452 KiB

shortcut

#include <cstdio>
#include <map>
#include <set>
#include <vector>
using namespace std;
using ll=long long;

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

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

void insert_downstair(map<ll,ll> &m, ll x, ll y) {
    auto it = m.lower_bound(x);
    if (it != m.end() && y <= it->second) return;
    if (it->first == x) it->second = y;
    else it = m.insert(it, pair<ll,ll>{x, y});
    while (it != m.begin()) {
        auto pr = prev(it);
        if (pr->second <= y) m.erase(pr);
        else break;
    }
}

ll get_max_y_where_x_geq(map<ll,ll> &m, ll xmin) {
    auto it = m.lower_bound(xmin);
    if (it == m.end()) return -inf;
    return it->second;
}

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

    map<ll,ll> setA, setB;
    for (int i=n-1; 0<=i; --i) {
        ll maxAj = get_max_y_where_x_geq(setA, V-B[i]+1),
           maxBj = get_max_y_where_x_geq(setB, V-B[i]+1);

        plus_min = max(plus_min, A[i]+maxAj-V+L);
        plus_max = min(plus_max, V-L-B[i]-maxBj);
        minus_min = max(minus_min, A[i]+maxBj-V+L);
        minus_max = min(minus_max, V-L-B[i]-maxAj);

        insert_downstair(setA, A[i], A[i]);
        insert_downstair(setB, A[i], B[i]);
    }
    setA.clear(); setB.clear();

    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;
}

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];

    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