Submission #1218512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218512		vanea	Overtaking (IOI23_overtaking)	C++20	100 / 100	1284 ms	105448 KiB

overtaking

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

const int mxN = 1e3+10;

int l, x, m, n;
vector<ll> t;
vector<int> w, s;
ll buses[mxN][mxN];
vector<int> tot_ord[mxN];
int pos[mxN][mxN];
map<ll, ll> mp;
ll shift = 0;

ll query(ll x) {
    x += shift;
    auto it = mp.upper_bound(x);
    if(it != mp.begin()) x = max(x, prev(it)->second);
    return x;
}

void uni(ll x, ll y) {
    x += shift;
    auto it = mp.upper_bound(x);
    if(it != mp.begin() && prev(it)->second >= y) return ;
    mp[x] = y;
    it = mp.find(x);
    while(next(it) != mp.end() && next(it)->second <= y) mp.erase(next(it));
}

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;
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    for(int i = 0; i < n; i++) {
        buses[i][0] = t[i];
    }
    for(int j = 1; j < m; j++) {
        sort(ord.begin(), ord.end(), [&](int a, int b) {
            if(buses[a][j-1] != buses[b][j-1]) return buses[a][j-1] < buses[b][j-1];
            return w[a] < w[b];
        });
        tot_ord[j-1] = ord;
        ll tim = -1;
        for(int it = 0; it < n; it++) {
            int i = ord[it];
            pos[j-1][i] = it;
            buses[i][j] = buses[i][j-1] + 1LL * w[i] * (s[j] - s[j-1]);
            buses[i][j] = max(tim, buses[i][j]);
            tim = max(tim, buses[i][j]);
        }
        if(j == m-1) {
            sort(ord.begin(), ord.end(), [&](int a, int b) {
                if(buses[a][j-1] != buses[b][j-1]) return buses[a][j-1] < buses[b][j-1];
                return w[a] < w[b];
            });
            tot_ord[j] = ord;
            for(int it = 0; it < n; it++) {
                int i = ord[it];
                pos[j][i] = it;
            }
        }
    }
    for(int i = m-2; i >= 0; i--) {
        vector<array<ll, 2>> a;
        for(int it = 0; it < n; it++) {
            ll e1 = buses[it][i], e2 = buses[it][i+1];
            a.push_back({e1, query(e2)});
        }
        shift += 1LL * x * (s[i+1] - s[i]);
        for(auto [x, y] : a) {
            uni(x+1, y);
        }
    }
}


ll arrival_time(ll Y) {
    return query(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