Submission #1064221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064221		jer033	Overtaking (IOI23_overtaking)	C++17	65 / 100	3544 ms	49856 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using tlli = tuple<ll, ll, int>;//prev time, next time, index
using tll = tuple<ll, ll>;
const ll INF = 3'123'456'123'456'123'456;

ll L;
int N;
vector<ll> T;
vector<ll> W;
ll X;
int M;
vector<ll> S;
vector<vector<ll>> times;
vector<vector<tll>> range_map;

void init(int L1, int N1, std::vector<long long> T1, std::vector<int> W1, int X1, int M1, std::vector<int> S1)
{
    L = L1;
    N = N1;
    T = T1;
    for (int i: W1)
        W.push_back(i);
    X = X1;
    W.push_back(X);
    M = M1;
    for (int i: S1)
        S.push_back(i);


    times = vector<vector<ll>> (N+1);
    for (int i=0; i<N; i++)
        times[i].push_back(T[i]);
    for (int sorting = 1; sorting<M; sorting++)
    {
        ll length = S[sorting] - S[sorting-1];
        vector<tlli> move;
        for (int i=0; i<N; i++)
        {
            move.push_back({times[i][sorting-1], times[i][sorting-1] + (length*W[i]), i});
        }
        sort(move.begin(), move.end());
        ll running_max = -1;
        for (int j=0; j<N; j++)
        {
            running_max = max(running_max, get<1>(move[j]));
            int i = get<2>(move[j]);
            times[i].push_back(running_max);
        }
    }

    for (int sorting = 1; sorting<M; sorting++)
    {
        vector<tll> rang;
        for (int i=0; i<N; i++)
            rang.push_back({times[i][sorting-1], times[i][sorting]});
        rang.push_back({INF, INF});
        rang.push_back({-1, 0});
        sort(rang.begin(), rang.end());
        range_map.push_back(rang);
    }
}

long long arrival_time(long long Y)
{
    ll curr = Y;
    for (int sorting = 1; sorting<M; sorting++)
    {
        ll expected = ((S[sorting]-S[sorting-1])*X)+curr;
        int lo = 0;
        int hi = N+1;
        while (lo!=hi)
        {
            int mid = (lo+hi)/2;
            if (get<0>(range_map[sorting-1][mid]) >= curr)
                hi = mid;
            else
                lo = mid+1;
        }
        expected = max(expected, get<1>(range_map[sorting-1][lo-1]));
        curr = expected;
    }
    return curr;
}

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