Submission #863046

#	Time	Username	Problem	Language	Result	Execution time	Memory
863046		faustaadp	Overtaking (IOI23_overtaking)	C++17	0 / 100	693 ms	14048 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll NN = 2e5 + 5;
ll n, m, x;
ll a[NN], b[NN], jar[NN], sam[2020][2020];
vector<pair<ll, pll> > v[NN];
vector<ll> hai;
vector<pll> oi, oi2;
long long arrival_timee(long long Y);
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    n = N;
    m = M;
    x = X;
    for(ll i = 0; i < n; i++)
    {
        a[i] = T[i];
        b[i] = W[i];
        // cout << a[i] << "dan" << b[i] << "ui\n";
    }
    for(ll i = 0; i < m; i++)
        jar[i] = S[i];
    for(ll i = 0; i < n; i++)
        sam[0][i] = a[i];
    for(ll i = 1; i < m; i++)
    {
        for(ll j = 0; j < n; j++)
        {
            v[i].pb(mp(sam[i - 1][j], mp(b[j], j)));
        }
        sort(v[i].begin(), v[i].end());
        ll lst = 0;
        for(auto z : v[i])
        {
            sam[i][z.se.se] = max(lst, sam[i - 1][z.se.se] + (jar[i] - jar[i - 1]) * z.se.fi);
            lst = sam[i][z.se.se];
        }
    }
    ll lst = 0;
    for(ll i = 1; i <= 20000; i++)
    {
        ll o = arrival_timee(lst);
        ll L = lst, R = 1e18, kan = lst;
        while(L <= R)
        {
            ll C = (L + R) / 2;
            if(arrival_timee(C) == o)
            {
                kan = C;
                L = C + 1;
            }
            else
                R = C - 1;
        }
        // cout << kan << " " << o << "\n";
        oi.pb(mp(kan, o));
        lst = kan + 1;
    }
    lst = 1e18;
     for(ll i = 1; i <= 20000; i++)
    {
        ll o = arrival_timee(lst);
        ll L = 0, R = lst, kir = R;
        while(L <= R)
        {
            ll C = (L + R) / 2;
            if(arrival_timee(C) == o)
            {
                kir = C;
                R = C - 1;
            }
            else
                L = C + 1;
        }
        // cout << kir << " " << o << "\n";
        oi2.pb(mp(kir, o));
        lst = kir - 1;
    }
    // for(ll i = 0; i <= 500; i++)
    {
        // if(i == 0 || arrival_time(i) != arrival_time(i - 1))
            // cout << i << " " << arrival_time(i) << "\n";
    }
    return;
}

long long arrival_timee(long long Y)
{
    for(ll i = 1; i < m; i++)
    {
        pair<ll, pll> ban = mp(Y, mp(x, n));
        ll L = 0, R = v[i].size() - 1;
        ll lst = -1;
        while(L <= R)
        {
            ll C = (L + R) / 2;
            if(v[i][C] < ban)
            {
                lst = C;
                L = C + 1;
            }
            else
                R = C - 1;
        }
        if(lst >= 0)
            Y = max(sam[i][v[i][lst].se.se], Y + (jar[i] - jar[i - 1]) * ban.se.fi);
        else
            Y = Y + (jar[i] - jar[i - 1]) * ban.se.fi;
        // sort(v.begin(), v.end());
        // ll lst = 0;
        // for(auto z : v)
        // {
        //     // cout << "(" << i << "," << z.fi << ") " << sam[z.se.se] << " + " << (jar[i] - jar[i - 1]) << "*" << z.se.fi << "@\n";
        //     sam[z.se.se] = max(lst, sam[z.se.se] + (jar[i] - jar[i - 1]) * z.se.fi);
        //     lst = sam[z.se.se];
        // }
    }
    return Y;
}
long long arrival_time(long long Y)
{
    ll ret = -1, L = 0, R = oi.size() - 1;
    while(L <= R)
    {
        ll C = (L + R) / 2;
        if(oi[C].fi >= Y)
        {
            ret = oi[C].se;
            R = C - 1;
        }
        else
            L = C + 1;
    }
    if(ret != -1)
        return ret;
    L = 0, R = oi2.size() - 1;
    while(L <= R)
    {
        ll C = (L + R) / 2;
        if(oi2[C].fi <= Y)
        {
            ret = oi2[C].se;
            L = C + 1;
        }
        else
            R = C - 1;
    }
    if(ret != -1)
        return ret;
    return oi.back().se + Y - oi.back().fi;
}

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