Submission #1124675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124675		blackslex	Overtaking (IOI23_overtaking)	C++17	100 / 100	1825 ms	105544 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using tp = tuple<ll, ll, ll>;

const int N = 1005;
ll l, n, m, x;
vector<ll> w, s;
vector<ll> t;
vector<vector<ll>> e, ct;
bool qrm;

struct blackslex {
    struct info {
        ll l, r, val;
        info(ll l, ll r, ll val) : l(l), r(r), val(val) {}
        friend bool operator < (const info &a, const info &b) {
            return (qrm ? a.val < b.val : a.r < b.r);
        }
    };
    ll lz;
    multiset<info> ms;
    void upd (ll l, ll r, ll val) {
        val -= lz;
        auto it = ms.lower_bound(info(0, l, 0));
        if (it != ms.end() && it->l < l) {
            auto cval = *it; it = ms.erase(it);
            // cval->l < l <= cval->r
            // split to [cval->l, l) and [l, cval->r]
            ms.emplace(cval.l, l - 1, cval.val);
            // ms.emplace(l, cval.r, cval.val);
        }
        // !!!
        for (; it != ms.end() && it->r <= r;) it = ms.erase(it);
        // it->l <= r < it->r
        // r < it->l
        if (it != ms.end() && it->l <= r) {
            auto cval = *it; ms.erase(it);
            // ms.emplace(cval.l, r, cval.val);
            ms.emplace(r + 1, cval.r, cval.val);
        }
        ms.emplace(l, r, val);
    }
    ll bs (ll rval) {
        rval -= lz;
        qrm = 1; auto it = ms.lower_bound(info(0, 0, rval)); qrm = 0;
        // rval <= it->l
        // f(x) = x -> f(rval) = rval
        return (it == ms.end() ? rval : min(rval, it->l));
    }
    ll qr (ll x) {
        auto it = ms.lower_bound(info(0, x, 0));
        // x <= it->r
        return (it == ms.end() || it->l > x ? x : it->val) + lz;
    }
} oo;

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S){
    l = L; n = N; t = T; x = X; m = M;
    w.resize(n); s.resize(m);
    for (int i = 0; i < n; i++) w[i] = W[i];
    for (int i = 0; i < m; i++) s[i] = S[i];
    e = vector<vector<ll>>(n, vector<ll>(m));
    ct = vector<vector<ll>>(n, vector<ll>(m));
    for (int i = 0; i < n; i++) ct[i][0] = t[i];
    for (int j = 1; j < m; j++) {
        map<ll, vector<ll>> mp;
        ll cmx = 0;
        for (int i = 0; i < n; i++) {
            e[i][j] = ct[i][j - 1] + w[i] * (s[j] - s[j - 1]);
            mp[ct[i][j - 1]].emplace_back(i);
        }
        for (auto &[x, y]: mp) {
            for (auto &E: y) ct[E][j] = max(e[E][j], cmx);
            for (auto &E: y) cmx = max(cmx, e[E][j]);
        }
        vector<tp> c;
        // transition f_{j-1}(t) to f_j(t)
        for (int i = 0; i < n; i++) {
            ll st = ct[i][j - 1], ed = ct[i][j];
            ll mx = ed - x * (s[j] - s[j - 1]);
            ll mn = st + 1;
            if (mx < mn) continue;
            // start at t \in [tl, tr] -> oo.qr(t) \in [mn, mx]
            // t + speed * dist
            // auto bs = [&] (ll rval) {
            //     ll l = 0, r = 1e18;
            //     while (l < r) {
            //         ll mid = (l + r) >> 1LL;
            //         auto ck = [&] (ll val) {
            //             return oo.qr(val) >= rval;
            //         };
            //         if (ck(mid)) r = mid;
            //         else l = mid + 1;
            //     }
            //     return l;
            // };
            ll tl = oo.bs(mn), tr = oo.bs(mx + 1) - 1;
            if (tl > tr) continue;
            c.emplace_back(tl, tr, ed);
        }
        oo.lz += x * (s[j] - s[j - 1]);
        sort(c.begin(), c.end(), [&] (const tp &a, const tp &b) {
            return (get<2>(a) < get<2>(b));
        });
        for (auto &[x, y, z]: c) oo.upd(x, y, z);
    }
    return;
}

long long arrival_time(long long Y){
    return oo.qr(Y);
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 35 / 35