oj.uz

Submission #1002976

# Submission time Handle Problem Language Result Execution time Memory
1002976 2024-06-19T21:45:42 Z ThegeekKnight16 Autobahn (COI21_autobahn) C++17
50 / 100
 1000 ms 524288 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 4 ms 604 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 4 ms 604 KB Output is correct
17 Correct 4 ms 604 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 4 ms 604 KB Output is correct
20 Correct 3 ms 796 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 4 ms 604 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 4 ms 604 KB Output is correct
17 Correct 4 ms 604 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 4 ms 604 KB Output is correct
20 Correct 3 ms 796 KB Output is correct
21 Execution timed out 1033 ms 524288 KB Time limit exceeded
22 Halted 0 ms 0 KB -