oj.uz

Submission #420704

# Submission time Handle Problem Language Result Execution time Memory
420704 2021-06-08T13:25:31 Z Drew_ Autobahn (COI21_autobahn) C++17
100 / 100
 186 ms 10864 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define ll long long
#define pb push_back
#define ii pair<int, int>
#define f1 first
#define s2 second

const int MAX = 3e5 + 69;

int n, k, x;
int people[MAX] = {};
ll fee[MAX] = {};
ll pfx[MAX] = {};
vector<int> comp;

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k >> x;

	vector<ii> v1, v2;
	for (int i = 0; i < n; ++i)
	{
		int l, t, r;
		cin >> l >> t >> r;

		v1.pb({l, r+1});
		if (l + t <= r)
			v2.pb({l+t, r+1});
	}

	comp.pb(0);
	for (auto [a, b] : v1)
		comp.pb(a), comp.pb(b);
	for (auto [a, b] : v2)
		comp.pb(a), comp.pb(b);
	sort(comp.begin(), comp.end());
	comp.resize(unique(comp.begin(), comp.end()) - comp.begin());

	for (auto &[a, b] : v1)
	{
		a = (int)(lower_bound(comp.begin(), comp.end(), a) - comp.begin());
		b = (int)(lower_bound(comp.begin(), comp.end(), b) - comp.begin());
	}
	for (auto &[a, b] : v2)
	{
		a = (int)(lower_bound(comp.begin(), comp.end(), a) - comp.begin());
		b = (int)(lower_bound(comp.begin(), comp.end(), b) - comp.begin());
	}
	int sz = (int)comp.size();

	// for (auto [a, b] : v1)
	// 	cerr << a << " " << b << " ==> " << comp[a] << " " << comp[b]<< '\n';
	// for (auto [a, b] : v2)
	// 	cerr << "> " << a << " " << b << " ==> " << comp[a] << " " << comp[b] << '\n';

	//add range
	for (auto [l, r] : v1)
		people[l]++, people[r]--;
	for (auto [l, r] : v2)
		fee[l]++, fee[r]--;
	
	//get fee and number of people at time i
	for (int i = 1; i < sz; ++i)
		fee[i] += fee[i-1], people[i] += people[i-1];

	//removing free hours
	for (int i = 1; i < sz; ++i)
		if (people[i] < k)
			fee[i] = 0;

	//  cerr << "people: ";
	// for (int i = 1; i < sz; ++i)
	// 	cerr << people[i] << ", ";
	// cerr << '\n';

	// cerr << "fee: ";
	// for (int i = 1; i < sz; ++i)
	// 	cerr << fee[i] << ", ";
	// cerr << '\n';


	//generate prefix

	pfx[0] = fee[0];
	for (int i = 1; i < sz; ++i)
	{
		ll val = 0;
		if (i+1 < sz)
			val = fee[i] * (comp[i+1] - comp[i]);

		pfx[i] = val + pfx[i-1];
	}


	const auto getL = [&](int L, int idL) -> ll //returns sum of value of [L, L+x)
	{
		int R = L + x - 1;
		int idR = (int)(upper_bound(comp.begin(), comp.end(), R) - comp.begin()) - 1;

		ll res = 0;
		if (idL < idR)
			res += (pfx[idR - 1] - pfx[idL - 1]);
		res += fee[idR] * (R - comp[idR] + 1);
		return res;
	};

	const auto getR = [&](int R, int idR) -> ll //returns sum of value [R-x, R)
	{
		int L = R-x;
		if (L < 0)
			return 0;
		int idL = (int)(upper_bound(comp.begin(), comp.end(), L) - comp.begin()) - 1;
		
		ll res = pfx[idR - 1] - pfx[idL];
		res += fee[idL] * (comp[idL + 1] - L);
		return res;
	};

	ll res = 0;
	for (int i = 0; i < sz; ++i)
	{
		// cerr << comp[i] << ", " << i << " =" << getL(comp[i], i) << '\n';
		res = max(res, getL(comp[i], i));
		res = max(res, getR(comp[i], i));
	}
	cout << res << '\n';


	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 320 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 178 ms 10700 KB Output is correct
22 Correct 186 ms 10864 KB Output is correct
23 Correct 183 ms 10848 KB Output is correct
24 Correct 163 ms 10848 KB Output is correct
25 Correct 173 ms 10848 KB Output is correct
26 Correct 164 ms 10852 KB Output is correct
27 Correct 175 ms 10844 KB Output is correct
28 Correct 156 ms 10848 KB Output is correct
29 Correct 156 ms 10852 KB Output is correct