Submission #1002976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002976		ThegeekKnight16	Autobahn (COI21_autobahn)	C++17	50 / 100	1033 ms	524288 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-1, r); sweep.emplace_back(l, 1); sweep.emplace_back(r+1, 0);}
	sort(sweep.begin(), sweep.end());
	int lastPlace = 0, cntPeople = 0;
	for (auto [x, type] : sweep)
	{
		if (type == 1) cntPeople++;
		else cntPeople--;
		if (cntPeople >= K) 
		{
			line.updateM(1, 0, border, x, border, 1); 
			// cerr << "||" << x << " pay " << '\n';
		}
		else 
		{
			line.updateM(1, 0, border, x, border, 0);
			// cerr << "||" << x << " no pay" << '\n';
		}
	}

	for (auto [l, t, r] : person) line.update(1, 0, border, t+1, r, +1);

	int resp = 0;
	for (auto [l, t, r] : person)
	{
		int ans = max(line.query(1, 0, border, l, l+X-1), line.query(1, 0, border, l-X+1, l));
		ans = max({ans, line.query(1, 0, border, r, r+X-1), line.query(1, 0, border, r-X+1, r)});
		ans = max({ans, line.query(1, 0, border, t, t+X-1), line.query(1, 0, border, t-X+1, t)});
		resp = max(resp, ans);
	}

	cout << resp << '\n';
}

Compilation message (stderr)

autobahn.cpp: In function 'int32_t main()':
autobahn.cpp:120:6: warning: unused variable 'lastPlace' [-Wunused-variable]
  120 |  int lastPlace = 0, cntPeople = 0;
      |      ^~~~~~~~~

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