Submission #972066

#	Time	Username	Problem	Language	Result	Execution time	Memory
972066		happypotato	Overtaking (IOI23_overtaking)	C++17	100 / 100	1293 ms	107156 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
ll L;
ll speed;
map<ll, ll> ans; // (l, r]
void DebugMap() {
	cerr << "DEBUG MAP:" << endl;
	for (pll cur : ans) {
		cerr << cur.ff << ' ' << cur.ss << endl;
	}
	cerr << "END" << endl << endl;
}
void AddRange(ll l, ll r) {
	// cerr << "ADDING " << l << ' ' << r << endl;
	map<ll, ll>::iterator it;
	// find extension
	it = ans.lower_bound(r);
	if (it != ans.begin()) {
		--it;
		r = max(r, it->ss);
	}
	// check if being contained
	it = ans.upper_bound(l);
	if (it != ans.begin()) {
		--it;
		if (it->ff <= l && r <= it->ss) return;
	}
	// remove all that are contained
	while (true) {
		it = ans.lower_bound(l);
		if (it == ans.end()) break;
		if (l <= it->ff && it->ss <= r) {
			ans.erase(it);
		} else break;
	}
	ans[l] = r;
	// DebugMap();
}
void init(int L_, int n, vector<long long> T, vector<int> W, int X, int m, vector<int> S) {
	vector<ll> s(m);
	for (int i = 0; i < m; i++) s[i] = S[i];
	L = L_; speed = X;
	vector<pll> blocks;
	for (int i = 0; i < n; i++) {
		if (W[i] <= speed) continue;
		blocks.pb({T[i], W[i]});
	}
	n = blocks.size();
	ll times[m][n];
	for (int i = 0; i < n; i++) times[0][i] = blocks[i].ff;
	for (int i = 1; i < m; i++) {
		vector<pair<pll, int>> range;
		ll dt = s[i] - s[i - 1];
		for (int j = 0; j < n; j++) {
			range.pb({{times[i - 1][j], times[i - 1][j] + blocks[j].ss * dt}, j});
		}
		sort(range.begin(), range.end());
		ll mx = -1e18;
		for (int j = 0; j < n; j++) {
			mx = max(mx, range[j].ff.ss);
			times[i][range[j].ss] = mx;
		}
	}

	// for (int i = 0; i < m; i++) {
	// 	for (int j = 0; j < n; j++) {
	// 		cerr << times[i][j] << ' ';
	// 	}
	// 	cerr << endl;
	// }
	// cerr << endl;

	for (int i = m - 1; i >= 1; i--) {
		vector<pll> range;
		for (int j = 0; j < n; j++) {
			ll st = times[i - 1][j] - speed * s[i - 1];
			ll en = times[i][j] - speed * s[i];
			range.pb({st, en});
		}
		sort(range.begin(), range.end());
		for (pll cur : range) {
			AddRange(cur.ff, cur.ss);
		}
	}
}

long long arrival_time(long long x) {
	ll res = x + L * speed;
	if (ans.empty()) return res;
	map<ll, ll>::iterator it = ans.lower_bound(x);
	if (it != ans.begin()) {
		--it;
		res = max(res, it->ss + L * speed);
	}
	return res;
}

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