Submission #969756

#	Time	Username	Problem	Language	Result	Execution time	Memory
969756		happypotato	Overtaking (IOI23_overtaking)	C++17	19 / 100	22 ms	3160 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) {
	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]});
	}

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

	map<ll, ll> mp;
	for (int i = 1; i < m; i++) {
		ans[i].clear();
		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;
		});
		mp.clear();
		ll dt = s[i] - s[i - 1];
		for (int j = 0; j < (int)(blocks.size()); j++) {
			ll t = blocks[j].ff, w = blocks[j].ss;
			map<ll, ll>::iterator it = mp.upper_bound(t);
			if (it != mp.begin()) {
				--it;
				if (it->ss >= t + w * dt) {
					if (it->ff < t) t = it->ss;
					else t += w * dt;
					blocks[j].ff = t;
					continue;
				}
			}
			mp[t] = t + w * dt;
			t += w * dt;
			blocks[j].ff = t;
		}
		// 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);
			if (st <= en) 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 nx = it->ss.ss + speed * (s[r] - s[mid]);
			map<ll, pll>::iterator it2 = ans[pr].upper_bound(it->ss.ss);
			if (it2 != ans[pr].begin()) {
				--it2;
				if (it2->ff <= it->ss.ss && it->ss.ss <= it2->ss.ff) {
					nx = it2->ss.ss;
				}
			}
			it->ss.ss = nx;
		}
		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->ss.ss > it->ss.ss) {
						tl = 0; tr = -1; break;
					}
					if (it2->ss.ff + 1 < tl) continue;
				}
				if (it2 == ans[pl].end()) break;
				// cerr << it2->ff << ' ' << it2->ss.ff << ' ' << it2->ss.ss << endl;
				if (it2->ff > tr + 1) break;
				// 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) {
						if (it2->ss.ff >= tl) exit(1);
						it2->ss.ff = min(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