oj.uz

Submission #1002691

# Submission time Handle Problem Language Result Execution time Memory
1002691 2024-06-19T18:13:45 Z luanaamorim Autobahn (COI21_autobahn) C++17
50 / 100
 691 ms 524288 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <vector> 
#include <queue>
#define all(x) x.begin(), x.end()
#define MAXN (int) (2e5 + 10)
#define INF (int) (1e9 + 100)
#define int long long
#define ii pair<int, int> 

using namespace std;

struct tree
{
	int esq, dir, val;
};

int n, k, x;
vector<ii> paga, tot, lazy, inter;
vector<tree> st;
priority_queue<int, vector<int>, greater<int> > pq;

int novo()
{
	st.push_back({-1, -1, 0});
	lazy.push_back({1, 0});
	return st.size() - 1;
}

void push(int idx, int i, int j)
{
	if (lazy[idx].first == 1 && lazy[idx].second == 0) return;
	auto[a, b] = lazy[idx];
	st[idx].val = a*st[idx].val + b*(j-i+1);
	if (i != j)
	{
		if (st[idx].esq == -1) st[idx].esq = novo();
		if (st[idx].dir == -1) st[idx].dir = novo();

		lazy[st[idx].esq] = {a*lazy[st[idx].esq].first, a*lazy[st[idx].esq].second + b};
		lazy[st[idx].dir] = {a*lazy[st[idx].dir].first, a*lazy[st[idx].dir].second + b};
	}

	lazy[idx] = {1, 0};
}

int query(int idx, int i, int j, int l, int r)
{
	push(idx, i, j);
	if (j < l || i > r) return 0;
	if (j <= r && i >= l) 
	{
		return st[idx].val;
	}
	if (st[idx].esq == -1) st[idx].esq = novo();
	if (st[idx].dir == -1) st[idx].dir = novo();

	int mid = (i+j)>>1;
	int x = query(st[idx].esq, i, mid, l, r);
	int y = query(st[idx].dir, mid+1, j, l, r);
	return x+y;
}

void update(int idx, int i, int j, int l, int r, int op)
{
	push(idx, i, j);
	if (j < l || i > r) return;
	if (j <= r && i >= l)
	{
		if (op) lazy[idx] = {1, 1};
		else lazy[idx] = {0, 0};
		push(idx, i, j);
		return;
	}
	if (st[idx].esq == -1) st[idx].esq = novo();
	if (st[idx].dir == -1) st[idx].dir = novo();

	int mid = (i+j)>>1;
	update(st[idx].esq, i, mid, l, r, op);
	update(st[idx].dir, mid+1, j, l, r, op);
	st[idx].val = st[st[idx].esq].val + st[st[idx].dir].val;
}

int32_t main()
{
	cin >> n >> k >> x;
	novo();
	for (int i = 0; i < n; i++)
	{
		int x, y, z;
		cin >> x >> z >> y;
		tot.push_back({x, y});
		int l = (x + z);
		int r = y;

		if (l > r) continue;
		paga.push_back({l, r});
		update(0, 0, INF, l, r, 1);
	}

	sort(all(tot));
	int pessoas = 0, last = 0;
	for (auto[ini, fim] : tot)
	{
		++pessoas;
		pq.push(fim);
		while (!pq.empty() && pq.top() < ini) 
		{
			int curr = pq.top(); pq.pop();
		    --pessoas;
			if (pessoas == k) 
			{

				inter.push_back({last, curr});
			}
		}

		if (pessoas == k) last = ini;
	}

	while (!pq.empty())
	{
		int curr = pq.top(); pq.pop();
		--pessoas;
		if (pessoas == k-1) 
		{
			inter.push_back({last, curr});
		}
	}

	sort(all(inter));
	int idx = 0;
	for (auto[l, r] : inter)
	{
		update(0, 0, INF, idx, l-1, 0);
		idx = r+1;
	}
	update(0, 0, INF, idx, INF, 0);

	int resp = 0;
//	for (auto[ini, fim] : tot)
//	{
//		ini = max(ini, x);
//		resp = max({resp, query(0, 0, INF, ini-x, ini-1), query(0, 0, INF, fim+1, fim+x)});
//	}

	for (auto[ini, fim] : paga)
	{
		resp = max({resp, query(0, 0, INF, ini, ini+x-1), query(0, 0, INF, fim-x+1, fim)});
	}

	cout << resp << endl;
}

Subtask #1
20.0 / 20.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 348 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 0 ms 432 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 448 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Runtime error 691 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -