Submission #843293

#	Time	Username	Problem	Language	Result	Execution time	Memory
843293		SHZhang	Overtaking (IOI23_overtaking)	C++17	65 / 100	3532 ms	63396 KiB

overtaking

#include "overtaking.h"

#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <cstdio>

using namespace std;

#define ll long long

ll arrtime[1005][1005];
set<pair<ll, ll> > intvs[1005];

vector<pair<ll, ll> > buses;
int l, n, x, m;
vector<int> s;

void addintv(int span, ll l, ll r)
{
    intvs[span].insert(make_pair(-l, -r));
}

ll find_max_right(int span, ll entertime)
{
    auto iter = intvs[span].lower_bound(make_pair(-entertime + 1, -9000000000000000000LL));
    if (iter == intvs[span].end() || -iter->second < entertime) {
        return entertime;
    }
    return -iter->second;
}

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    l = L;
    n = N;
    x = X;
    m = M;
    s = S;
    for (int i = 0; i < N; i++) {
        buses.push_back(make_pair(W[i], T[i]));
    }
    sort(buses.begin(), buses.end());
    reverse(buses.begin(), buses.end());
    for (int i = 0; i < N; i++) {
        ll ctime = buses[i].second;
        ll ispeed = buses[i].first;
        //printf("Bus departing at %lld, %lld secs/km:\n", ctime, ispeed);
        for (int j = 0; j < M - 1; j++) {
            ll ntime = max(find_max_right(j, ctime), ctime + ispeed * (ll)(S[j+1]-S[j]));
            addintv(j, ctime, ntime);
            ctime = ntime;
            //printf("Span %d done at time %lld\n", j, ctime);
        }
    }
}

long long arrival_time(long long Y)
{
    ll ctime = Y;
    for (int j = 0; j < m - 1; j++) {
        ctime = max(find_max_right(j, ctime), ctime + x * (ll)(s[j+1]-s[j]));
    }
    return ctime;
}

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