Submission #1115748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115748		jerzyk	Overtaking (IOI23_overtaking)	C++17	0 / 100	3 ms	764 KiB

overtaking

#include <bits/stdc++.h>
#include "overtaking.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1'007;
int n, m, V;
ll dis[N], vel[N];
vector<pair<ll, int>> sta[N];
set<pair<ll, pair<ll, ll>>> ran;
set<pair<ll, pair<ll, ll>>>::iterator it;
vector<pair<pair<ll, ll>, ll>> interv;
ll ofs = 0LL;

void DoSta()
{
    for(int i = 1; i < m; ++i)
    {
        sort(sta[i].begin(), sta[i].end());
        ll curma = 0LL, am = 0LL;
        for(int j = 0; j < n; ++j)
        {
            ll na = sta[i][j].st + (dis[i + 1] - dis[i]) * vel[sta[i][j].nd];
            na = max(na, curma);
            sta[i + 1].pb(make_pair(na, sta[i][j].nd));
            am = max(na, am);
            if(j == n - 1 || sta[i][j].st != sta[i][j + 1].st)
                curma = max(curma, am);
            //cout << i << " Sta " << sta[i][j].nd << " " << sta[i][j].st << " " << na << "\n";
        }
    }
    for(int i = 1; i <= m; ++i)
    {
        vector<pair<ll, int>> nw;
        nw.pb(make_pair(-1LL, -1LL));
        for(int j = 0; j < n; ++j)
        {
            if(vel[sta[i][j].nd] <= V) continue;
            if(nw.size() == 0 || (nw.back().st != sta[i][j].st))
                nw.pb(sta[i][j]);
            else if(vel[nw.back().nd] < vel[sta[i][j].nd])
                nw.back() = sta[i][j];
        }
        sta[i] = nw;
    }
    if((int)sta[1].size() == 1) return;
    for(int i = 1; i < (int)sta[1].size(); ++i)
    {
        //cerr << "I: " << sta[1][i].st << "\n";
        ran.insert(make_pair(sta[1][i].st, make_pair(sta[1][i].st, sta[1][i].st)));
    }

    for(int i = 2; i <= m; ++i)
    {
        ll dod = (dis[i] - dis[i - 1]) * V;
        for(int j = sta[i].size() - 1; j >= 1; --j)
        {
            ll x = sta[i][j].st - (dis[i] - dis[i - 1]) * vel[sta[i][j].nd];
            ll y = sta[i][j].st - (dis[i] - dis[i - 1]) * V;
            ll p = I + 10000LL, k = sta[i][j].st - dis[i] * V;
            it = ran.lower_bound(make_pair(x - ofs, make_pair(-1LL, -1LL)));
            if(it != ran.end())
                p = (*it).nd.nd + 1LL;
            it = ran.lower_bound(make_pair(x - ofs + 1LL, make_pair(-1LL, -1LL)));
            while(it != ran.end() && (*it).st + ofs <= y)
            {
                p = min(p, (*it).nd.st);
                ran.erase(*it);
                it = ran.lower_bound(make_pair(x - ofs + 1LL, make_pair(-1LL, -1LL)));
            }
            if(it != ran.end())
                k = min(k, (*it).nd.st - 1LL);
            //cerr << i << " " << j << " " << sta[i][j].st << " " << sta[i][j].nd << " x,y:  " << x << " " << y << " p,k: " << p << " " << k << " " << "\n";
            if(p <= k)
                ran.insert(make_pair(sta[i][j].st - ofs - dod, make_pair(p, k)));
        }
        //cout << "\n";
        ofs += dod;
    }
    for(it = ran.begin(); it != ran.end(); ++it)
        interv.pb(make_pair((*it).nd, (*it).st + ofs));
}

void init(int _L, int _N, vector<ll> _T, vector<int> _W, int _X, int _M, vector<int> _S)
{
    n = _N; m = _M; V = _X;
    for(int i = 1; i <= m; ++i)
        dis[i] = _S[i - 1];
    for(int i = 1; i <= n; ++i)
    {
        vel[i] = _W[i - 1];
        sta[1].pb(make_pair(_T[i - 1], i));
    }
    DoSta();
}

long long arrival_time(ll _Y)
{
    ll tim = _Y;
    ll ans = tim + dis[m] * V;
    int p = (upper_bound(interv.begin(), interv.end(), make_pair(make_pair(tim, -1LL), -1LL)) - interv.begin()) - 1;
    if(interv[p].st.st <= tim && interv[p].st.nd >= tim)
        ans = interv[p].nd;
    return ans;
}

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