Submission #1002868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002868		ThegeekKnight16	Autobahn (COI21_autobahn)	C++17	0 / 100	0 ms	348 KiB

autobahn

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int border = 2e9 + 10;
class SparseSeg
{
protected:
	vector<int> seg, mSum, lz, lzM, e, d; 

public:
	int create()
	{
		seg.push_back(0);
		mSum.push_back(0);
		lz.push_back(0);
		lzM.push_back(-1);
		e.push_back(0);
		d.push_back(0);
		return seg.size()-1;
	}

	int getLeft(int pos)
	{
		if (e[pos] == 0) {int aux = create(); e[pos] = aux;}
		return e[pos];
	}

	int getRight(int pos)
	{
		if (d[pos] == 0) {int aux = create(); d[pos] = aux;}
		return d[pos];
	}

	void refreshM(int pos, int ini, int fim)
	{
		if (lzM[pos] == -1) return;
		int x = lzM[pos]; lzM[pos] = -1;
		mSum[pos] = x * (fim - ini + 1);

		if (ini == fim) return;
		lzM[getLeft(pos)] = x;
		lzM[getRight(pos)] = x; 
	}

	void init()
	{
		create(); create();
	}

	void refresh(int pos, int ini, int fim)
	{
		if (lz[pos] == 0) return;
		int x = lz[pos]; lz[pos] = 0;
		seg[pos] += x * mSum[pos];

		if (ini == fim) return;
		lz[getLeft(pos)] += x;
		lz[getRight(pos)] += x;
	}

	void updateM(int pos, int ini, int fim, int p, int q, int val)
	{
		refreshM(pos, ini, fim);
		if (q < ini || p > fim || q < p) return;
		if (p <= ini && fim <= q)
		{
			lzM[pos] = val;
			refreshM(pos, ini, fim);
			return;
		}
		int m = (ini + fim) >> 1;
		updateM(getLeft(pos), ini, m, p, q, val);
		updateM(getRight(pos), m+1, fim, p, q, val);
		mSum[pos] = mSum[e[pos]] + mSum[d[pos]];
	}

	void update(int pos, int ini, int fim, int p, int q, int val)
	{
		refreshM(pos, ini, fim);
		refresh(pos, ini, fim); 
		if (q < ini || p > fim || q < p) return;
		if (p <= ini && fim <= q)
		{
			lz[pos] += val;
			refreshM(pos, ini, fim);
			refresh(pos, ini, fim);
			return;
		}
		int m = (ini + fim) >> 1;
		update(getLeft(pos), ini, m, p, q, val);
		update(getRight(pos), m+1, fim, p, q, val);
		seg[pos] = seg[e[pos]] + seg[d[pos]];
	}

	int query(int pos, int ini, int fim, int p, int q)
	{
		refreshM(pos, ini, fim);
		refresh(pos, ini, fim);
		if (q < ini || p > fim || q < p || pos == 0) return 0;
		if (p <= ini && fim <= q) return seg[pos];
		int m = (ini + fim) >> 1;
		return (query(e[pos], ini, m, p, q) + query(d[pos], m+1, fim, p, q));
	}	
} line;



int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	line.init();
	line.updateM(1, 0, border, 0, border, 0);
	int N, K, X;
	cin >> N >> K >> X;
	vector<tuple<int, int, int>> person(N);
	vector<pair<int, int>> sweep;
	for (auto &[l, t, r] : person) {cin >> l >> t >> r; t = min(l+t, r); sweep.emplace_back(l, 1); sweep.emplace_back(r+1, 0);}
	
	vector<int> cntPeople(1001);
	for (auto [l, t, r] : person) 
		for (int i = l; i <= r; i++) cntPeople[i]++;

	vector<int> mult(1001, 0);
	for (int i = 1; i <= 1000; i++) 
	{
		mult[i] = (cntPeople[i] >= K);
		// cerr << "i: " << i << ", cnt: " << cntPeople[i] << '\n';
	}

	vector<int> pay(1001);
	for (auto [l, t, r] : person) for (int i = t; i <= r; i++) pay[i] += mult[i];
	for (int i = 1; i <= 1000; i++)
	{
		// cerr << "i: " << i << ", pay: " << pay[i] << '\n';
	 	pay[i] += pay[i-1];
	}
	int resp = 0;
	for (int i = 1; i <= 1000-X+1; i++) resp = max(resp, pay[i+X-1] - pay[i-1]);
	cout << resp << '\n';
}

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