Submission #417164

#	Time	Username	Problem	Language	Result	Execution time	Memory
417164		yuto1115	Shortcut (IOI16_shortcut)	C++17	93 / 100	2071 ms	19044 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int inf = 1001001001;
const ll linf = 1001001001001001001;

class segtree {
    int n;
    vl v;
public:
    segtree(int _n) {
        n = 1;
        while (n < _n) n *= 2;
        v.assign(2 * n, linf);
    }
    
    void update(int x, ll val) {
        assert(0 <= x and x < n);
        x += n;
        chmin(v[x], val);
        x >>= 1;
        while (x >= 1) {
            v[x] = min(v[2 * x], v[2 * x + 1]);
            x >>= 1;
        }
    }
    
    ll prod(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        ll res = linf;
        while (l < r) {
            if (l & 1) chmin(res, v[l++]);
            if (r & 1) chmin(res, v[--r]);
            l >>= 1, r >>= 1;
        }
        return res;
    }
};

ll find_shortcut(int n, vi l, vi d, int c) {
    vl L(n);
    rep(i, n - 1) L[i + 1] = L[i] + l[i];
    ll ok = linf, ng = 0;
    vl zip;
    rep(i, n) zip.pb(L[i] + d[i]);
    sort(all(zip));
    zip.erase(unique(all(zip)), zip.end());
    int sz = zip.size();
    vi pos(n);
    rep(i, n) pos[i] = lower_bound(all(zip), L[i] + d[i]) - zip.begin();
    auto f = [&](ll x) -> bool {
        ll p = -linf, q = linf, r = -linf, s = linf;
        segtree st(sz);
        int mx_pos = -1;
        rrep(a, n) {
            int ub = upper_bound(all(zip), x + L[a] - d[a]) - zip.begin();;
            if (mx_pos < ub) {
                st.update(pos[a], L[a] - d[a]);
                chmax(mx_pos, pos[a]);
                continue;
            }
            ll tmp = st.prod(ub, sz);
            chmax(p, L[a] + d[a] + c - x + zip[mx_pos]);
            chmin(q, L[a] - d[a] - c + x + tmp);
            chmax(r, -L[a] + d[a] + c - x + zip[mx_pos]);
            chmin(s, -L[a] - d[a] - c + x + tmp);
            st.update(pos[a], L[a] - d[a]);
            chmax(mx_pos, pos[a]);
        }
        rep(i, n - 1) {
            ll mn = max(p - L[i], r + L[i]);
            ll mx = min(q - L[i], s + L[i]);
            auto it = lower_bound(L.begin() + i + 1, L.end(), mn);
            if (it == L.end()) continue;
            if (*it > mx) continue;
            return true;
        }
        return false;
    };
    while (ok - ng > 1) {
        ll mid = (ok + ng) / 2;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

• 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