Submission #848387

#	Time	Username	Problem	Language	Result	Execution time	Memory
848387		math_rabbit_1028	Overtaking (IOI23_overtaking)	C++17	65 / 100	3516 ms	177496 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int l, n, x, m;
vector<ll> t;
vector<int> w, s;

ll est[1010][1010], arr[1010][1010];
pll range[1010][1010];

struct seg {
    int sz;
    vector<ll> vals;
    ll tree[8080], lazy[8080];
    void init(int v, int st, int ed) {
        if (st == ed) {
            tree[v] = -1;
            lazy[v] = -1;
            return;
        }
        int mid = (st + ed) / 2;
        init(2 * v, st, mid);
        init(2 * v + 1, mid + 1, ed);
        tree[v] = max(tree[2 * v], tree[2 * v + 1]);
        lazy[v] = -1;
    }
    void propagate(int v, int st, int ed) {
        tree[v] = max(tree[v], lazy[v]);
        if (st != ed) {
            lazy[2 * v] = max(lazy[2 * v], lazy[v]);
            lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]);
        }
    }
    void update(int v, int st, int ed, int lt, int rt, ll val) {
        propagate(v, st, ed);
        if (lt > ed || rt < st) return;
        if (lt <= st && ed <= rt) {
            lazy[v] = max(lazy[v], val);
            propagate(v, st, ed);
            return;
        }
        int mid = (st + ed) / 2;
        update(2 * v, st, mid, lt, rt, val);
        update(2 * v + 1, mid + 1, ed, lt, rt, val);
        tree[v] = max(tree[2 * v], tree[2 * v + 1]);
    }
    ll get(int v, int st, int ed, int idx) {
        propagate(v, st, ed);
        if (st > idx || ed < idx) return -1;
        if (st == idx && ed == idx) return tree[v];
        int mid = (st + ed) / 2;
        return max(get(2 * v, st, mid, idx), get(2 * v + 1, mid + 1, ed, idx));
    }
} sg[1010];

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
    l = L; n = N; t = T; w = W; x = X; m = M; s = S;

    for (int i = 0; i < n; i++) arr[0][i] = t[i];
    for (int j = 1; j < m; j++) {
        for (int i = 0; i < n; i++) est[j][i] = arr[j - 1][i] + (ll)w[i] * (s[j] - s[j - 1]);

        vector<pll> tlist;
        for (int i = 0; i < n; i++) tlist.push_back({arr[j - 1][i], i});
        sort(tlist.begin(), tlist.end());

        ll last = 0, p = 0;
        for (int i = 0; i < n; i++) {
            while (tlist[p].first < tlist[i].first) {
                last = max(last, est[j][tlist[p].second]);
                p++;
            }
            arr[j][tlist[i].second] = max(last, est[j][tlist[i].second]);
        }
    }

    for (int j = 0; j < m - 1; j++) {
        for (int i = 0; i < n; i++) {
            if (w[i] > x) {
                range[j][i] = {arr[j][i] + 1, arr[j][i] + (ll)(w[i] - x) * (s[j + 1] - s[j])};
                sg[j].vals.push_back(range[j][i].first);
                sg[j].vals.push_back(range[j][i].second);
            }
        }
        sort(sg[j].vals.begin(), sg[j].vals.end());
        sg[j].vals.erase(unique(sg[j].vals.begin(), sg[j].vals.end()), sg[j].vals.end());
        sg[j].sz = sg[j].vals.size();
        sg[j].init(1, 0, sg[j].sz);
        for (int i = 0; i < n; i++) {
            if (w[i] > x) {
                int s = lower_bound(sg[j].vals.begin(), sg[j].vals.end(), range[j][i].first)
                      - sg[j].vals.begin() + 1;
                int e = lower_bound(sg[j].vals.begin(), sg[j].vals.end(), range[j][i].second)
                      - sg[j].vals.begin() + 1;
                sg[j].update(1, 0, sg[j].sz, s, e - 1, arr[j + 1][i]);
            }
        }
    }
    return;
}

ll arrival_time(ll Y) {
    ll y = Y;
    for (int j = 0; j < m - 1; j++) {
        int idx = upper_bound(sg[j].vals.begin(), sg[j].vals.end(), y)
                - sg[j].vals.begin();
        ll next = sg[j].get(1, 0, sg[j].sz, idx);
        if (next >= 0) y = next;
        else y = y + (ll)x * (s[j + 1] - s[j]);
        //cout << y << "\n";
    }
    return y;
}

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