Submission #850171

#	Time	Username	Problem	Language	Result	Execution time	Memory
850171		PurpleCrayon	Overtaking (IOI23_overtaking)	C++17	100 / 100	1492 ms	176568 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int K = 1e3+10;
const ll INF = 1e18+10;

struct Set {
    set<pair<ll, ll>> s;
    void emplace_back(ll x, ll y) {
        {
            auto it = s.upper_bound({x, INF});
            if (it != s.begin() && prev(it)->second >= y) {
                return;
            }
        }

        auto it = s.lower_bound({x, -1});
        while (it != s.end() && it->second <= y) {
            it = s.erase(it);
            // it = s.lower_bound({x, -1});
        }

        s.insert({x, y});
    }

    ll qry(ll x) {
        auto it = s.lower_bound({x, -1});
        if (it != s.begin()) return prev(it)->second;
        return -INF;
    }
};

int M, X;
vector<int> S;
Set worst[K]; // for each start time care about the max end time, sorted by start time
vector<ll> store[K];

ll delta = 0;
set<pair<ll, ll>> pts;
vector<pair<ll, ll>> bld;

void shift(ll k) {
    delta += k;
}

ll qry(ll x) {
    return prev(pts.upper_bound({x - delta, INF}))->second;
}

void build() {
    bld = vector<pair<ll, ll>>(pts.begin(), pts.end());
}

ll qry_end(ll x) {
    return (upper_bound(bld.begin(), bld.end(), make_pair(x - delta, INF)) - 1)->second;
}

void set_range(ll L, ll R, ll x) {
    // cerr << "upd: " << L << ' ' << R << ' ' << x << endl;
    pts.insert({R+1 - delta, qry(R+1)});
    auto it = pts.lower_bound({L - delta, -INF});
    while (it != pts.end() && it->first + delta <= R) {
        it = pts.erase(it);
        // it = pts.lower_bound({L - delta, -INF});
    }
    pts.insert({L - delta, x});
}


void init(int L, int N, vector<long long> T, vector<int> W, int _X, int _M, vector<int> _S) {
    X = _X, M = _M, S = _S;
    vector<int> ord(N); iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) { // slowest buses first
        return W[x] > W[y];
    });

    while (sz(ord) && W[ord.back()] <= X) ord.pop_back();
    for (int x : ord) {
        ll cur = T[x]; // cur time at station
        for (int i = 0; i < M-1; i++) {
            ll want = cur + (long long) W[x] * (S[i+1] - S[i]);
            ll get = worst[i].qry(cur);
            if (get > want) want = get;
            else worst[i].emplace_back(cur, want);
            cur = want;
        }
    }

    pts.insert({-2 * INF, -1});
    for (int i = M-2; i >= 0; i--) {
        int k = 0;
        const vector<pair<ll, ll>>& v = vector<pair<ll, ll>>(worst[i].s.begin(), worst[i].s.end());

        store[i].resize(sz(v));
        for (auto [st, en] : v) {
            store[i][k] = qry(en);
            if (store[i][k] == -1) store[i][k] = en + (long long) X * (L - S[i+1]);
            // cerr << S[i] << ' ' << S[i+1] << ' ' << st << ' ' << en << ' ' << store[i][k] << endl;
            k++;
        }

        shift(-(long long) X * (S[i+1] - S[i]));
        k = 0;
        for (auto [st, en] : v) {
            ll L = st + 1, R = en - (long long) X * (S[i+1] - S[i]);
            if (L <= R)
                set_range(L, R, store[i][k]);
            k++;
        }
    }
    build();
}

long long arrival_time(long long Y) {
    ll ans = qry_end(Y);
    if (ans == -1) ans = Y + (long long) X * S.back();
    return ans;
}

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