Submission #421778

#	Time	Username	Problem	Language	Result	Execution time	Memory
421778		KoD	Shortcut (IOI16_shortcut)	C++17	93 / 100	2078 ms	24620 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
 
template <class T>
using Vec = std::vector<T>;
using ll = long long;
 
constexpr ll INF = std::numeric_limits<ll>::max() / 2;
 
template <class T> void setmin(T& lhs, const T& rhs) {
    if (lhs > rhs) {
        lhs = rhs;
    }
}
 
template <class T> void setmax(T& lhs, const T& rhs) {
    if (lhs < rhs) {
        lhs = rhs;
    }
}
 
template <class T> struct RMQ {
    int size;
    Vec<T> min;
    RMQ(const int n): size(n), min(2 * n, std::numeric_limits<T>::max()) {}
    void chmin(int i, const T& x) {
        i += size;
        setmin(min[i], x);
        while (i > 1) {
            i >>= 1;
            setmin(min[i], min[2 * i]);
            setmin(min[i], min[2 * i + 1]);
        }
    }
    T fold(int l, int r) const {
        l += size;
        r += size;
        T ret = std::numeric_limits<T>::max();
        while (l < r) {
            if (l & 1) setmin(ret, min[l++]);
            if (r & 1) setmin(ret, min[--r]);
            l >>= 1;
            r >>= 1;
        }
        return ret;
    }
};
 
ll find_shortcut(int n, Vec<int> l, Vec<int> d, int c) {
    Vec<ll> x(n);
    for (int i = 1; i < n; ++i) {
        x[i] = x[i - 1] + l[i - 1];
    }
    Vec<ll> cmp(n);
    for (int i = 0; i < n; ++i) {
        cmp[i] = d[i] - x[i];
    }
    std::sort(cmp.begin(), cmp.end());
    cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
    Vec<int> idx(n);
    for (int i = 0; i < n; ++i) {
        idx[i] = std::lower_bound(cmp.begin(), cmp.end(), d[i] - x[i]) - cmp.begin();
    }
    const int len = (int) cmp.size();
    const auto check = [&](const ll threshold) -> bool {
        ll sum_min = -INF, sum_max = INF;
        ll dif_min = -INF, dif_max = INF;
        RMQ<ll> min1(len), min2(len);
        for (int i = 0; i < n; ++i) {
            const int pos = std::upper_bound(cmp.begin(), cmp.end(), threshold - (x[i] + d[i])) - cmp.begin();
            const ll a = min1.fold(pos, len);
            const ll b = min2.fold(pos, len);
            if (a != std::numeric_limits<ll>::max()) {
                setmin(sum_max, a + (x[i] - d[i]) + threshold - c);
                setmax(sum_min, -b + (x[i] + d[i]) + c - threshold);
                setmin(dif_max, b + (x[i] - d[i]) + threshold - c);
                setmax(dif_min, -a + (x[i] + d[i]) + c - threshold);
            }
            min1.chmin(idx[i], x[i] - d[i]);
            min2.chmin(idx[i], -(x[i] + d[i]));
        } 
        if (sum_min > sum_max or dif_min > dif_max)  {
            return false;
        }
        for (int i = 0; i < n; ++i) {
            int j1 = i + 1;
            setmax(j1, (int) (std::lower_bound(x.begin(), x.end(), sum_min - x[i]) - x.begin()));
            setmax(j1, (int) (std::lower_bound(x.begin(), x.end(), dif_min + x[i]) - x.begin()));
            int j2 = n - 1;
            setmin(j2, (int) (std::upper_bound(x.begin(), x.end(), sum_max - x[i]) - x.begin()) - 1);
            setmin(j2, (int) (std::upper_bound(x.begin(), x.end(), dif_max + x[i]) - x.begin()) - 1);
            if (j1 <= j2) {
                return true;
            }
        }
        return false;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (sum_min <= x[i] + x[j] and x[i] + x[j] <= sum_max and dif_min <= x[j] - x[i] and x[j] - x[i] <= dif_max) {
                    return true;
                }
            }
        }
        return false;
    };
    ll ok = INF, ng = 0;
    while (ok - ng > 1) {
        const auto md = (ok + ng) / 2;
        (check(md) ? ok : ng) = md;
    }
    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