Submission #1218588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218588		JooDdae	Shortcut (IOI16_shortcut)	C++20	0 / 100	0 ms	320 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);
    for(int i=0;i<n;i++) P[i] = {p[i]-d[i], i};
    sort(P.begin(), P.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;
            // cout << i << " " << j << "\n";
            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;i<n;i++) {
            auto R = int(lower_bound(P.begin(), P.end(), make_pair(p[i]+d[i]-m, 0)) - P.begin()) - 1;
            if(R < 0) continue;

            diamond(P[0].second, i, m-c);
            if(R) diamond(P[1].second, i, m-c);

            diamond(mx[R][0], i, m-c);
            diamond(mx[R][1], i, m-c);
        }
        
        if(xl > xr || yl > yr) return false;


        for(int i=0, j=0;i<n && j<n;i++) {
            ll L = max(xl-p[i], yl+p[i]), R = min(xr-p[i], yr+p[i]);
            while(j < n && p[j] < L) j++;
            if(j < n && p[j] <= R) 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: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3