Submission #1213503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213503		Nelt	Overtaking (IOI23_overtaking)	C++17	65 / 100	3593 ms	49940 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 1005, inf = 9e18;
pair<ll, ll> mx[N][N];
vector<pair<ll, ll>> tmp[N];
set<array<ll, 3>> st;
ll dp[N][N];
ll t[N][N];
ll v[N], s[N];
ll n, m, X;
void add(ll l, ll r, ll x)
{
    set<array<ll, 3>>::iterator it;
    while ((it = st.lower_bound({l, -1, -1})) != st.end() and it->operator[](1) <= r)
        st.erase(it);
    if (it != st.end() and it->operator[](0) <= r)
    {
        auto [l1, r1, x1] = *it;
        st.erase(it);
        st.insert({r + 1, r1, x1});
    }
    it = st.lower_bound({l, -1, -1});
    if (it != st.begin())
    {
        it--;
        if (it->operator[](1) >= l)
        {
            auto [l1, r1, x1] = *it;
            st.erase(it);
            st.insert({l1, l - 1, x1});
        }
    }
    st.insert({l, r, x});
}
ll getpoint(ll x)
{
    auto it = st.upper_bound({x, inf, inf});
    if (it != st.begin())
    {
        it--;
        if (it->operator[](1) >= x)
            return it->operator[](2);
    }
    return -1;
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int x_, int M, std::vector<int> S)
{
    X = x_;
    n = N, m = M;
    for (ll i = 0; i < n; i++)
        t[i][0] = T[i];
    for (ll i = 0; i < n; i++)
        v[i] = W[i];
    v[n] = X;
    for (ll i = 0; i < m; i++)
        s[i] = S[i];
    for (ll i = 0; i < n; i++)
        tmp[0].push_back(make_pair(t[i][0], i));
    sort(tmp[0].begin(), tmp[0].end());
    for (ll i = 1; i < m; i++)
    {
        for (ll x = 0; x < n; x++)
        {
            ll j = tmp[i - 1][x].second;
            t[j][i] = t[j][i - 1] + v[j] * (s[i] - s[i - 1]);
            mx[i][x] = max(x > 0 ? mx[i][x - 1] : make_pair(0ll, 0ll), make_pair(t[j][i], j));
            ll pos = 0ll + lower_bound(tmp[i - 1].begin(), tmp[i - 1].end(), make_pair(t[j][i - 1], -1ll)) - tmp[i - 1].begin() - 1;
            if (pos >= 0)
                t[j][i] = max(t[j][i], mx[i][pos].first);
        }
        for (ll j = 0; j < n; j++)
            tmp[i].push_back(make_pair(t[j][i], j));
        sort(tmp[i].begin(), tmp[i].end());
    }
    for (ll i = m - 1; i >= 0; i--)
    {
        for (ll j = 0, pt, last, pos; j < n; j++)
        {
            pt = getpoint(t[i][j]);
            if (pt == -1)
                dp[i][j] = t[i][j] + (L - s[i]) * X;
            else
            {
                last = t[i][j] + (s[pt - 1] - s[i]) * X;
                pos = lower_bound(tmp[pt - 1].begin(), tmp[pt - 1].end(), make_pair(last, -1ll)) - tmp[pt - 1].begin();
                if (pos >= 0)
                    dp[i][j] = dp[pt][mx[pt][pos].second];
                else
                    assert(0 == 1);
            }
        }
        if (i)
            for (ll j = 0; j < n; j++)
                add(t[i - 1][j] - s[i - 1] * X + 1, t[i][j] - s[i] * X, i);
    }
    // for (auto [l, r, x] : st) cout << l << " " << r << " " << x << endl;
}

long long arrival_time(long long cur)
{
    // ll pt = getpoint(cur);
    // if (pt == -1)
    //     return cur + s[m - 1] * X;
    // ll last = cur + s[pt - 1] * X;
    // ll pos = lower_bound(tmp[pt - 1].begin(), tmp[pt - 1].end(), make_pair(last, -1ll)) - tmp[pt - 1].begin();
    // if (pos >= 0)
    //     return dp[pt][mx[pt][pos].second];
    // assert(0);
    for (ll i = 1; i < m; i++) 
    {
        ll pos = lower_bound(tmp[i - 1].begin(), tmp[i - 1].end(), make_pair(cur, -1ll)) - tmp[i - 1].begin() - 1;
        cur += v[n] * (s[i] - s[i - 1]);
        if (pos >= 0) cur = max(cur, mx[i][pos].first);
    }
    return cur;
}

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