Submission #420704

#	Time	Username	Problem	Language	Result	Execution time	Memory
420704		Drew_	Autobahn (COI21_autobahn)	C++17	100 / 100	186 ms	10864 KiB

autobahn

#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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50