Submission #842509

#	Time	Username	Problem	Language	Result	Execution time	Memory
842509		CodePlatina	Overtaking (IOI23_overtaking)	C++17	100 / 100	968 ms	58212 KiB

overtaking

#include "overtaking.h"
#include <algorithm>
#include <iostream>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ff first
#define ss second
using namespace std;
const long long INF = (long long)2e18 + 17;

int X;
vector<int> S;
vector<pll> A;
vector<vector<pll>> B;
vector<vector<long long>> MX;
int nxt[1'000'005];

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
    ::X = X;
    ::S = S;
    for(int i = 0; i < N; ++i) if(W[i] > X) A.push_back({ T[i], W[i] });
    N = A.size();
    sort(A.begin(), A.end());

    B.push_back(A);
    for(int i = 1; i < M; ++i)
    {
        int t = S[i] - S[i - 1];
        vector<pll> C;
        vector<long long> D;
        long long mx = -INF;
        long long prmx = -INF;
        for(int j = 0; j < N; ++j)
        {
            if(j && B.back()[j - 1].ff < B.back()[j].ff)
                mx = max(mx, prmx), prmx = -INF;
            D.push_back(mx);
            long long cur = B.back()[j].ff + B.back()[j].ss * t;
            C.push_back({ max(mx, cur), B.back()[j].ss });
            prmx = max(prmx, cur);
        }
        D.push_back(max(mx, prmx));
        sort(C.begin(), C.end());
        B.push_back(C);
        MX.push_back(D);
    }

    for(int i = 0; i < M; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            int cur = i * N + j;
            int s = i, e = M;
            while(s + 1 < e)
            {
                int mid = s + e >> 1;
                if(j == 0 || B[mid][j - 1].ff < B[i][j].ff + 1ll * X * (S[mid] - S[i])) s = mid;
                else e = mid;
            }
            if(e < M)
                nxt[cur] = e * N + (lower_bound(B[e].begin(), B[e].end(), pll{MX[s][j], -INF}) - B[e].begin());
            else nxt[cur] = cur;
        }
    }

    for(int i = N * M - 1; i >= 0; --i) nxt[i] = nxt[nxt[i]];
}

long long arrival_time(long long Y)
{
    int M = B.size(), N = B[0].size();
    
    int ind = lower_bound(B[0].begin(), B[0].end(), pll{Y, -INF}) - B[0].begin();
    int s = 0, e = M;
    while(s + 1 < e)
    {
        int mid = s + e >> 1;
        if(ind == 0 || B[mid][ind - 1].ff < Y + 1ll * X * S[mid]) s = mid;
        else e = mid;
    }
    if(e == M) return Y + 1ll * X * S.back();

    // cout << e << endl;

    ind = e * N + (lower_bound(B[e].begin(), B[e].end(), pll{MX[s][ind], -INF}) - B[e].begin());
    ind = nxt[ind];

    int i = ind / N, j = ind % N;
    // cout << i << ' ' << j << endl;
    return B[i][j].ff + 1ll * X * (S.back() - S[i]);
}

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:57:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |                 int mid = s + e >> 1;
      |                           ~~^~~
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:78:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |         int mid = s + e >> 1;
      |                   ~~^~~

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