Submission #1066938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066938		Gromp15	Overtaking (IOI23_overtaking)	C++17	39 / 100	3556 ms	48812 KiB

overtaking

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#include "overtaking.h"
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

int L, N, X, M;
vector<ll> T;
vector<int> W, S;

vector<vector<ar<ll, 2>>> cars;
vector<vector<ar<ll, 4>>> go;
vector<ar<ll, 4>> tot;

const ll INF = 4e18;

void init(int _L, int _N, std::vector<long long> _T, std::vector<int> _W, int _X, int _M, std::vector<int> _S)
{
	L = _L;
	N = _N;
	T = _T;
	W = _W;
	X = _X;
	M = _M;
	S = _S;
	W.push_back(X);
	vector<ar<ll, 2>> buses;
	for (int i = 0; i < N; i++) if (W[i] > X) buses.push_back({T[i], i});
	cars.resize(M), go.resize(M);
	for (int i = 0; i < M - 1; i++) {
		vector<ar<ll, 3>> ints;
		for (auto [x, y] : buses) {
			ints.push_back({x, x + (ll)W[y] * (S[i+1] - S[i]), y});
		}
		sort(all(ints));
		ll to = 0;
		vector<ar<ll, 2>> buses2;
		vector<ar<ll, 2>> tmp;
		for (auto [l, r, idx] : ints) {
			ckmax(to, r);
			buses2.push_back({to, idx});
			tmp.push_back({l, to});
		}
		swap(buses, buses2);
		cars[i] = tmp;
	}
	for (int i = 0; i < M-1; i++) {
		ll R = -1;
		vector<ar<ll, 2>> nw;
		sort(all(cars[i]), [&](const auto &A, const auto &B) { return A[0] != B[0] ? A[0] < B[0] : A[1] > B[1]; });
		for (auto [l, r] : cars[i]) {
			if (r <= R) continue;
			R = r;
			nw.push_back({l, r});
		}
		swap(cars[i], nw);
	}
	vector<ar<ll, 4>> cur;
	for (int i = M-2; i >= 0; i--) {
		ll cur_dist = (ll)(S[i+1] - S[i]) * X;
		assert(is_sorted(all(cars[i])));
		vector<ar<ll, 3>> ints;
		/*
		cout << "Dist " << cur_dist << '\n';
		cout << "Cars\n";
		for (auto [l, r] : cars[i]) cout << l << " " << r << '\n';
		*/
		for (int j = 0; j < sz(cars[i]); j++) {
			ll nxt = j+1 < sz(cars[i]) ? cars[i][j+1][0] : cars[i][j][1];
			ll right = min(cars[i][j][1] - cur_dist, nxt);
			if (cars[i][j][0] + 1 <= right) ints.push_back({cars[i][j][0] + 1, right, cars[i][j][1]});
		}
		for (auto [l, r, dest] : ints) go[i].push_back({l, r, dest, i+1});
		if (i == M-2) {
			for (auto [l, r, dest] : ints) cur.push_back({l, r, dest, i+1});
		}
		else {
			assert(is_sorted(all(cur)));
			int on = 0;
			vector<ar<ll, 4>> here;
			for (auto [l, r, dest] : ints) {
				while (on < sz(cur) && cur[on][1] < dest) on++;
				if (on < sz(cur) && cur[on][0] <= dest) {
					here.push_back({l, r, cur[on][2], cur[on][3]});
				}
				else {
					here.push_back({l, r, dest, i+1});
				}
			}
			swap(cur, here);
		}
		go[i] = cur;
		/*
		cout << "Ints\n";
		for (auto [l, r, dest, to] : cur) cout << l << " " << r << " " << dest << " " << to << '\n';
		cout.flush();
		*/
	}
	tot = cur;
}

long long arrival_time(long long Y)
{
	int on = 0;
	for (int i = 0; i < M; i++) {
		ll mv = (ll)X * (S[i] - S[on]);
		if (on <= i) {
			for (auto [l, r, dest, idx] : go[i]) {
				if (l <= Y + mv && Y + mv <= r) {
					on = idx; Y = dest;
					i = on - 1;
					break;
				}
			}
		}
	}
	return Y + (ll)(S[M-1] - S[on]) * X;
	/*
	auto it = upper_bound(all(tot), ar<ll, 4>{Y, -1, -1, -1});
	bool cov = it != tot.begin() && (*prev(it))[1] >= Y;
	return cov ? (*prev(it))[2] + (ll)(S[M-1] - S[(*prev(it))[3]]) * X : Y + (ll)(S[M-1]-S[0]) * X;
	*/
}

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