Submission #1047464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047464		0npata	Overtaking (IOI23_overtaking)	C++17	100 / 100	515 ms	66904 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define vec vector

struct Bus {
	int t;
	int w;

	bool operator<(const Bus& other) {
		return t == other.t ? (w < other.w) : (t < other.t);
	}
};

int N, M, X, L;
vec<int32_t> S;

const int MXM = 1'005;
const int MXN = 1'005;
const int MXQ = 1'000'005;

vec<Bus> buses_arvs[MXM];
int arrival_mem[MXM][MXN];

int arrival(int i, int y) {
	if(i == M-1) {
		//cerr << "HERE: " << y << '\n';
		return y;
	}

	Bus b{y, 0};

	auto it = lower_bound(buses_arvs[i].begin(), buses_arvs[i].end(), b);
	int blow_i = (it-buses_arvs[i].begin())-1;
	//cerr << blow_i << '\n';
	if(blow_i == -1) {
		return y;
	}

	int l = i+1;
	int r = M;
	while(l < r) {
		int j = (l+r-1)/2;

		if(b < buses_arvs[j][blow_i]) {
			r = j+1;
			if(l + 1 == r) break;
		}
		else {
			l = j+1;
		}
	}
	if(l == M) {
		assert(l==r);
		return y;
	}
	int j = l;
	//cerr << "J: " << j << '\n';
	if(arrival_mem[j][blow_i] == -1) {
		arrival_mem[j][blow_i] = arrival(j, buses_arvs[j][blow_i].t);
	}
	return arrival_mem[j][blow_i];
}

void init(int32_t L, int32_t N, std::vector<long long> T, std::vector<int32_t> W, int32_t X, int32_t M, std::vector<int32_t> S)
{
	memset(arrival_mem, -1, sizeof(arrival_mem));
	::L = L; ::N = N; ::M = M; ::X = X; ::S = S;

	buses_arvs[0] = vec<Bus>(0);
	for(int i = 0; i<N; i++) {
		if(W[i] > X) {
			buses_arvs[0].push_back({T[i], W[i]-X});
		}
	}
	N = buses_arvs[0].size();

	sort(buses_arvs[0].begin(), buses_arvs[0].end());
	for(int i = 1; i<M; i++) {
		int mxt = 0;
		buses_arvs[i] = vec<Bus>(N);
		for(int j = 0; j<N; j++) {
			mxt = max(buses_arvs[i-1][j].t + buses_arvs[i-1][j].w * (S[i]-S[i-1]), mxt);
			buses_arvs[i][j] = {mxt, buses_arvs[i-1][j].w};
		}
		sort(buses_arvs[i].begin(), buses_arvs[i].end());
	}

    return;
}

long long arrival_time(long long Y)
{
	return arrival(0, Y) + L*X;
}

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