Submission #879870

#	Time	Username	Problem	Language	Result	Execution time	Memory
879870		SanguineChameleon	Overtaking (IOI23_overtaking)	C++17	100 / 100	820 ms	134476 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;

long long off = 0;
vector<pair<pair<long long, long long>, long long>> ranges2;

void init(int len, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) {
	vector<pair<long long, int>> cur_T;
	for (int i = 0; i < N; i++) {
		if (W[i] > X) {
			cur_T.emplace_back(T[i], W[i]);
		}
	}
	vector<pair<long long, long long>> queries;
	for (int i = 0; i < M - 1; i++) {
		sort(cur_T.begin(), cur_T.end());
		vector<pair<long long, int>> nxt_T(cur_T.size());
		int start = 0;
		long long mx = 0;
		int dist = S[i + 1] - S[i];
		for (int j = 0; j < (int)cur_T.size(); j++) {
			if (j > 0 && cur_T[j].first != cur_T[j - 1].first) {
				for (int k = start; k < j; k++) {
					mx = max(mx, nxt_T[k].first);
				}
				start = j;
			}
			nxt_T[j] = {max(mx, cur_T[j].first + 1LL * cur_T[j].second * dist), cur_T[j].second};
		}
		for (int j = (int)cur_T.size() - 1; j >= 0; j--) {
			queries.emplace_back(cur_T[j].first - off, nxt_T[j].first - off - 1LL * X * dist);
		}
		off += 1LL * X * dist;
		cur_T.swap(nxt_T);
	}
	set<pair<long long, pair<long long, long long>>> ranges1;
	for (auto [A, B]: queries) {
		A++;
		B--;
		if (A > B) {
			continue;
		}
		auto it = ranges1.lower_bound({A, {-1, -1}});
		if (it == ranges1.end()) {
			ranges1.emplace(B + 1, make_pair(A, B));
			continue;
		}
		long long L = min(it->second.first, A);
		long long R = min(B, it->second.first - 1);
		while (it->first <= B) {
			R = it->second.second;
			it = ranges1.erase(it);
			if (it == ranges1.end()) {
				R = B;
				break;
			}
			if (R < B) {
				R = min(B, it->second.first - 1);
			}
		}
		if (L <= R) {
			ranges1.emplace(B + 1, make_pair(L, R));
		}
	}
	for (auto [val, pos]: ranges1) {
		ranges2.emplace_back(make_pair(pos.second, pos.first), val);
	}
}

long long arrival_time(long long Y) {
	auto it = lower_bound(ranges2.begin(), ranges2.end(), make_pair(make_pair(Y, -1LL), -1LL));
	if (it != ranges2.end() && it->first.second <= Y) {
		Y = it->second;
	}
	Y += off;
	return Y;
}

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