Submission #1218472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218472		vanea	Overtaking (IOI23_overtaking)	C++20	0 / 100	0 ms	580 KiB

overtaking

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

const int mxN = 1e3+10;
const ll INF = 1e18+10;
int l, n;vector<ll> t; vector<int> w; int x; int m; vector<int> s;
array<ll, 2> st[mxN][4*mxN];

void upd(int v, int node, int l, int r, int k, ll t, ll w) {
    if(l == r && l == k) {
        st[v][node] = {t, w};
        return ;
    }
    if(l > k || r < k) return ;
    int mid = (l+r)/2;
    upd(v, node*2, l, mid, k, t, w);
    upd(v, node*2+1, mid+1, r, k, t, w);
    st[v][node] = max(st[v][node*2], st[v][node*2+1]);
}

array<ll, 2> comb(array<ll, 2> a, array<ll, 2> b) {
    return {a[0]+b[0], a[1]+b[1]};
}

array<ll, 2> qry(int v, int node, int l, int r, int k) {
    if(l == r && l == k) return st[v][node];
    if(l > k || r < k) return {0, 0};
    int mid = (l+r)/2;
    return comb(qry(v, node*2, l, mid, k), qry(v, node*2+1, mid+1, r, k));
}

int qry1(int v, int node, int l, int r, ll x) {
    if(l == r) return l;
    int mid = (l+r)/2;
    if(st[v][node*2][0] >= x) return qry1(v, node*2, l, mid, x);
    else return qry1(v, node*2+1, mid+1, r, x);

}

ll qry2(int v, int node, int l, int r, int l1, int r1) {
    if(l1 <= l && r <= r1) return st[v][node][0];
    if(l1 > r || r1 < l) return 0;
    int mid = (l+r)/2;
    return max(qry2(v, node*2, l, mid, l1, r1),
               qry2(v, node*2+1, mid+1, r, l1, r1));
}

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);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        if(t[a] == t[b]) return w[a] < w[b];
        return t[a] < t[b];
    });
    for(int i = 0; i < n; i++) {
        upd(0, 1, 0, n-1, i, t[ord[i]], w[ord[i]]);
    }
    for(int j = 1; j < m; j++) {
        set<array<ll, 2>> buses;
        for(int i = 0; i < n; i++) {
            array<ll, 2> now = qry(j-1, 1, 0, n-1, i);
            ll f = now[0] + now[1] * (s[j] - s[j-1]);
            ll s;
            if(buses.empty()) s = 0;
            else {
                s = (*prev(buses.end()))[0];
            }
            ll now_val = max(f, s);
            buses.insert({now_val, now[1]});
        }
        int i = 0;
        for(auto [it, k] : buses) {
            upd(j, 1, 0, n-1, i++, it, k);
        }
    }
}

ll calculate_arrival_time(ll Y) {
    ll last_cnt = (Y > st[0][1][0] ? n : qry1(0, 1, 0, n-1, Y));
    ll last_time = Y;
    ll ans = 0;
    for(int j = 1; j < m; j++) {
        ll f = last_time + x * (s[j] - s[j-1]);
        ll s = qry2(j, 1, 0, n-1, 0, last_cnt-1);
        last_time = max(f, s);
        last_cnt = last_time > st[j][1][0] ? n : qry1(j, 1, 0, n-1, last_time);
        if(j == m-1) ans = last_time;
    }
    return ans;
}

ll arrival_time(ll Y) {
    return calculate_arrival_time(Y);
}

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