Submission #1112620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112620		gelastropod	Fire (BOI24_fire)	C++14	100 / 100	347 ms	79152 KiB

Main

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <climits>
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())
	{
		cpq.push(*vals.begin());
		vals.erase(vals.begin());
	}
	int crntmax = -1;
	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: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 21 / 21
• Subtask 6: 26 / 26