Submission #1218591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218591		JooDdae	Shortcut (IOI16_shortcut)	C++20	100 / 100	912 ms	63048 KiB

shortcut

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;

ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    vector<ll> p(n, 0);
    for(int i=1;i<n;i++) p[i] = p[i-1]+l[i-1];

    vector<pair<ll, int>> P(n), P2(n);
    for(int i=0;i<n;i++) P[i] = {p[i]-d[i], i}, P2[i] = {p[i]+d[i], i};
    sort(P.begin(), P.end()), sort(P2.begin(), P2.end());

    vector<array<int, 2>> mx(n);
    mx[0] = {P[0].second, -1};
    for(int i=1;i<n;i++) {
        int u = P[i].second;
        mx[i] = mx[i-1];
        auto &[f, s] = mx[i];

        if(p[u]+d[u] > p[f]+d[f]) s = f, f = u;
        else if(s == -1 || p[u]+d[u] > p[s]+d[s]) s = u;
    }

    auto solve = [&](ll m) {
        ll xl = -INF, yl = -INF, xr = INF, yr = INF;

        auto diamond = [&](int i, int j, ll m) {
            if(i >= j || i < 0) return;
            ll x = p[i], y1 = p[j]-m+d[i]+d[j], y2 = p[j]+m-d[i]-d[j];
            xl = max(xl, x+y1), yl = max(yl, x-y2);
            xr = min(xr, x+y2), yr = min(yr, x-y1);
        };

        for(int i=0, j=-1;i<n;i++) {
            auto [L, id] = P2[i];
            while(j+1 < n && P[j+1].first < L-m) j++;
            if(j < 0) continue;

            diamond(P[0].second, id, m-c);
            if(j) diamond(P[1].second, id, m-c);
            diamond(mx[j][0], id, m-c);
            diamond(mx[j][1], id, m-c);
        }
        
        if(xl > xr || yl > yr) return false;

        ll PR = -LLONG_MAX;
        bool flag = 0;
        for(int i=0, j=-1;i<n;i++) {
            ll L = max(xl-p[i], yl+p[i]), R = min(xr-p[i], yr+p[i]);
            
            if(!flag && PR > R) flag = 1, j = n-1;
            PR = R;

            if(!flag) while(j+1 < n && p[j+1] <= R) j++;
            if(flag) while(j >= 0 && p[j] > R) j--;
            if(0 <= j && j < n && L <= p[j]) return true;
        }
        return false;
    };

    ll s = 0, e = INF;
    while(s <= e) {
        ll m = (s+e) >> 1;
        if(solve(m)) e = m-1;
        else s = m+1;
    }
    return s;
}

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