oj.uz

Submission #1112617

# Submission time Handle Problem Language Result Execution time Memory
1112617 2024-11-14T12:27:38 Z gelastropod Fire (BOI24_fire) C++14
0 / 100
 1 ms 512 KB 
#include <climits>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
#define int long long

signed main(signed argc, char *argv[])
{
	int N, M, s, e;
	cin >> N >> M;
	vector<pair<int, int>> sorted;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq, cpq;
	map<int, int> vals;
	for (int i = 0; i < N; i++)
	{
		cin >> s >> e;
		if (s > e)
			e += M;
		vals[s] = max(vals[s], e);
	}
	map<int, int> endvals;
	while (!vals.empty())
	{
		sorted.push_back(*vals.begin());
		cpq.push(*vals.begin());
		endvals[vals.begin()->second] = sorted.size() - 1;
		vals.erase(vals.begin());
	}
	int crntmax = cpq.top().second;
	while (!cpq.empty())
	{
		if (cpq.top().second > crntmax)
		{
			crntmax = cpq.top().second;
			pq.push(cpq.top());
			sorted.push_back(cpq.top());
			endvals[cpq.top().second] = sorted.size() - 1;
		}
		cpq.pop();
	}
	N = sorted.size();
	vector<vector<int>> parent(31, vector<int>(N, -1));
	auto currvals = pq.top();
	int currmax = pq.top().second;
	int currind = 0;
	pq.pop();
	for (auto i : endvals)
	{
			while (currvals.first <= i.first)
			{
				if (currmax < currvals.second)
				{
					currmax = currvals.second;
					currind = N - pq.size() - 1;
				}
				if (pq.empty())
					currvals.first = LLONG_MAX;
				else
				{
					currvals = pq.top();
					pq.pop();
				}
			}
		if (currind == i.second)
			parent[0][i.second] = -1;
		else
			parent[0][i.second] = currind;
	}
	for (int i = 1; i < 31; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (parent[i - 1][j] == -1)
				parent[i][j] = -1;
			else
				parent[i][j] = parent[i - 1][parent[i - 1][j]];
		}
	}
	int ans = LLONG_MAX;
	for (int i = 0; i < N; i++)
	{
		int qq = i;
		int b = 0;
		int currans = 0;
		int a = sorted[i].first + M;
		for (int j = 30; j >= 0; j--)
		{
			int abc = parent[j][qq];
			if (abc != -1)
			{
				if (sorted[abc].second >= a)
					currans = b + (1 << j);
				else
					b += 1 << j, qq = abc;
			}
		}
		if (currans != 0)
			ans = min(ans, currans + 1);
	}
	if (ans == LLONG_MAX)
		cout << "-1\n";
	else
		cout << ans << '\n';
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Runtime error 1 ms 336 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Runtime error 1 ms 336 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Runtime error 1 ms 336 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 336 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Runtime error 1 ms 336 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -