Submission #969198

#	Time	Username	Problem	Language	Result	Execution time	Memory
969198		happypotato	Overtaking (IOI23_overtaking)	C++17	19 / 100	3513 ms	2136 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, pll> ans[1001];
void debugmp(int ptr) {
	cerr << "Outputting map " << ptr << endl;
	for (pair<ll, pll> cur : ans[ptr]) {
		cerr << "[" << cur.ff << ", " << cur.ss.ff << "] -> " << cur.ss.ss << endl;
	}
	cerr << "End of map " << ptr << endl << endl;
}
void init(int L_, int N, vector<long long> T, vector<int> W, int X, int m, vector<int> s) {
	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]});
	}

	map<ll, pll> tmp;
	auto discretise = [&](int ptr) {
		tmp.clear();
		ll prev = -1; pll range = {-1e9, -1e9};
		for (map<ll, pll>::iterator it = ans[ptr].begin(); it != ans[ptr].end(); ++it) {
			if (it->ss.ss == prev) {
				tmp[range.ff].ff = it->ss.ff;
				range.ss = it->ss.ff;
				continue;
			}
			tmp[it->ff] = it->ss;
			prev = it->ss.ss;
		}
		ans[ptr] = tmp;
	};

	for (int i = 1; i < m; i++) {
		sort(blocks.begin(), blocks.end(), [&](const pll &lhs, const pll &rhs) {
			if (lhs.ff != rhs.ff) return lhs.ff < rhs.ff;
			return lhs.ss > rhs.ss;
		});
		ll dt = s[i] - s[i - 1];
		map<ll, ll> mp;
		for (auto& [t, w] : blocks) {
			map<ll, ll>::iterator it = mp.upper_bound(t);
			if (it != mp.begin() && (--it)->ss >= t + w * dt) {
				if (it->ff < t) t = it->ss;
				else t += w * dt;
				continue;
			}
			mp[t] = t + w * dt;
			t += w * dt;
		}
		// for (auto &[t, w] : blocks) cerr << t << ' ' << w << endl;
		for (map<ll, ll>::iterator it = mp.begin(); it != mp.end(); ++it) {
			// cerr << it->ff << ' ' << it->ss << endl;
			ll st = it->ff + 1, en = it->ss - speed * dt;
			map<ll, ll>::iterator it2 = it; ++it2;
			if (it2 != mp.end()) en = min(en, it2->ff);
			ans[i][st] = {en, it->ss};
		}
		discretise(i);
		// debugmp(i);
	}

	auto merge = [&](int l, int r) {
		int mid = (l + r) >> 1;
		int pl = l, pr = mid + 1;
		// cerr << l << ' ' << r << ' ' << pl << ' ' << pr << endl;
		// debugmp(pl); debugmp(pr);
		for (map<ll, pll>::iterator it = ans[pl].begin(); it != ans[pl].end(); ++it) {
			ll oldv = it->ss.ss;
			it->ss.ss += speed * (s[r] - s[mid]);
			map<ll, pll>::iterator it2 = ans[pr].upper_bound(oldv);
			if (it2 != ans[pr].begin()) {
				--it2;
				if (it2->ff <= oldv && oldv <= it2->ss.ff) {
					it->ss.ss = it2->ss.ss;
				}
			}
		}
		discretise(pl);
		// cerr << "RESULT 1:" << endl; debugmp(pl);
		for (map<ll, pll>::iterator it = ans[pr].begin(); it != ans[pr].end(); ++it) {
			ll tl = it->ff, tr = it->ss.ff;
			tl -= speed * (s[mid] - s[l - 1]);
			tr -= speed * (s[mid] - s[l - 1]);
			// cerr << tl << ' ' << tr << ' ' << it->ss.ss << endl;
			bool checked = false;
			while (true) {
				map<ll, pll>::iterator it2 = ans[pl].lower_bound(tl);
				if (!checked) {
					checked = true;
					if (it2 == ans[pl].begin()) continue;
					--it2;
				}
				if (it2 == ans[pl].end()) break;
				// cerr << it2->ff << ' ' << it2->ss.ff << ' ' << it2->ss.ss << endl;
				if (it2->ff > tr) break;
				if (it2->ss.ff < tl) continue;
				// have intersection
				// cerr << "CHECKING:\n";
				// cerr << tl << ' ' << tr << ' ' << it->ss.ss << endl;
				// cerr << it2->ff << ' ' << it2->ss.ff << ' ' << it2->ss.ss << endl;
				if (it2->ss.ss <= it->ss.ss) {
					if (it2->ss.ss < it->ss.ss) {
						it2->ss.ff = tl - 1;
					} else {
						tl = min(tl, it2->ff);
						tr = max(tr, it2->ss.ff);
						ans[pl].erase(it2);
					}
				} else {
					tr = min(tr, it2->ff - 1);
					break;
				}
			}
			// cerr << tl << ' ' << tr << endl;
			if (tl <= tr) {
				ans[pl][tl] = {tr, it->ss.ss};
			}
		}
		discretise(pl);
		// cerr << "RESULT 2:" << endl; debugmp(pl);
	};
	auto recur = [&](auto&& self, int l, int r) {
		if (l == r) return;
		int mid = (l + r) >> 1;
		self(self, l, mid); self(self, mid + 1, r);
		merge(l, r);
	};

	recur(recur, 1, m - 1);

	cerr << "FINAL:" << endl; debugmp(1);
	cerr << "END OF FINAL" << endl;
	return;
}

long long arrival_time(long long x) {
	map<ll, pll>::iterator it = ans[1].upper_bound(x);
	if (it != ans[1].begin()) {
		--it;
		if (it->ff <= x && x <= it->ss.ff) return it->ss.ss;
	}
	return x + L * speed;
}

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