Submission #1009915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009915		boris_mihov	Overtaking (IOI23_overtaking)	C++17	65 / 100	3564 ms	18772 KiB

overtaking

#include "overtaking.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 1000 + 10;
const int MAXQ = 5000 + 10;

int n, m, l, x;
std::vector <int> s;
std::vector <std::pair <llong,int>> buses;
std::vector <std::pair <llong,llong>> t[MAXN];

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;
    s = S;
    x = X;

    for (int i = 0 ; i < n ; ++i)
    {
        buses.push_back({T[i], W[i]});
    }

    for (int i = 0 ; i + 1 < m ; ++i)
    {
        t[i].push_back({-1, 0});
        std::vector <std::pair <llong,int>> newBuses;
        std::sort(buses.begin(), buses.end());
        for (const auto &[time, w] : buses)
        {
            llong arrive = 1LL * (s[i + 1] - s[i]) * w + time;
            if (arrive > t[i].back().second)
            {
                t[i].push_back({time, arrive});
            }

            newBuses.push_back({t[i].back().second, w});
        }

        buses = newBuses;
    }
}

long long arrival_time(llong time)
{
    for (int i = 0 ; i + 1 < m ; ++i)
    {
        int l = 0, r = t[i].size(), mid;
        while (l < r - 1)
        {
            mid = l + r >> 1;
            if (t[i][mid].first < time) l = mid;
            else r = mid;
        }

        time = std::max(time + 1LL * x * (s[i + 1] - s[i]), t[i][l].second);
    }

    return time;
}

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time(llong)':
overtaking.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |             mid = l + r >> 1;
      |                   ~~^~~

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