oj.uz

Submission #1002850

# Submission time Handle Problem Language Result Execution time Memory
1002850 2024-06-19T20:36:21 Z pedroslrey Autobahn (COI21_autobahn) C++17
100 / 100
 121 ms 25088 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 120 ms 24984 KB Output is correct
22 Correct 117 ms 24984 KB Output is correct
23 Correct 118 ms 24980 KB Output is correct
24 Correct 120 ms 24980 KB Output is correct
25 Correct 116 ms 24960 KB Output is correct
26 Correct 112 ms 24832 KB Output is correct
27 Correct 119 ms 25088 KB Output is correct
28 Correct 117 ms 24976 KB Output is correct
29 Correct 121 ms 25068 KB Output is correct