Submission #842507

#	Time	Username	Problem	Language	Result	Execution time	Memory
842507		CodePlatina	Overtaking (IOI23_overtaking)	C++17	100 / 100	1238 ms	136268 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 sp[1'000'005][21];

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)
                sp[cur][0] = e * N + (lower_bound(B[e].begin(), B[e].end(), pll{MX[s][j], -INF}) - B[e].begin());
            else sp[cur][0] = cur;
        }
    }

    for(int j = 1; j <= 20; ++j) for(int i = 0; i < N * M; ++i)
        sp[i][j] = sp[sp[i][j - 1]][j - 1];

    // for(auto i : B)
    // {
    //     for(auto j : i) cout << "(" << j.ff << ", " << j.ss << ")" << ' ';
    //     cout << endl;
    // } 
}

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 = sp[ind][20];

    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:85:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |         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