Submission #1002850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002850		pedroslrey	Autobahn (COI21_autobahn)	C++17	100 / 100	121 ms	25088 KiB

autobahn

#include <bits/stdc++.h>

using namespace std;
using lli = long long;

vector<tuple<int, int, lli>> calc_costs(vector<tuple<int, int, int>> &inters, int k) {
	enum event_type { start, mid, end };
	
	vector<pair<int, event_type>> events;
	for (auto [a, b, c]: inters) {
		++c;
		events.emplace_back(a, start);
		events.emplace_back(min(a + b, c), mid);
		events.emplace_back(c, end);
	}

	sort(events.begin(), events.end());

	vector<tuple<int, int, lli>> costs;
	int cars = 0, illegal = 0, lst = 0;
	for (auto [x, t]: events) {
		if (t == start) {
			++cars;
			if (cars == k) lst = x;
		}
		else if (t == end) {
			if (cars >= k) costs.emplace_back(lst, x, 1LL*illegal);
			--cars; --illegal;
			lst = x;
		}
		else {
			if (cars >= k) costs.emplace_back(lst, x, 1LL*illegal);
			++illegal;
			lst = x;
		}
	}

	// cerr << "COSTS:\n";
	// for (auto [l, r, c]: costs)
	// 	cerr << l << " " << r << " " << c << "\n";
	// cerr << "\n";

	return costs;
}

lli calc_val(vector<tuple<int, int, lli>> costs, int x) {
	enum event_type { end_crosse, end_crossb, start_crossb, start_crosse };
	
	vector<tuple<int, lli, event_type>> events;
	for (auto [l, r, c]: costs) {
		events.emplace_back(l - x, c, start_crosse);
		events.emplace_back(r - x, c, end_crosse);
		events.emplace_back(l, c, start_crossb);
		events.emplace_back(r, c, end_crossb);
	}

	sort(events.begin(), events.end());

	lli cost = 0; lli best = 0;
	lli crossb = 0, crosse = 0; int lst = 0;
	for (auto [k, c, t]: events) {
		// cerr << k << " " << cost << "\n";
		cost += crosse*(k - lst) - crossb*(k - lst);

		if (t == start_crosse) crosse += c;
		else if (t == end_crosse) crosse -= c;
		else if (t == start_crossb) crossb += c;
		else crossb -= c;

		best = max(best, cost);
		lst = k;
	}

	return best;
}

int main() {
	int n, k, x;
	cin >> n >> k >> x;

	vector<tuple<int, int, int>> inters(n);
	for (auto &[a, b, c]: inters)
		cin >> a >> b >> c;

	cout << calc_val(calc_costs(inters, k), x) << "\n";
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50