Submission #1051492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051492		MuhammadSaram	Fire (BOI24_fire)	C++17	100 / 100	385 ms	45264 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n,m;
	cin>>n>>m;
	vector<pair<int,int>> op;
	set<int> se={0,m};
	int s[n],e[n];
	for (int i=0;i<n;i++)
	{
		cin>>s[i]>>e[i];
		se.insert(s[i]);
		se.insert(e[i]);
	}
	map<int,int> cmp;
	for (int i:se)
		cmp[i]=cmp.size();
	m=cmp.size();
	int mx[m+1]={};
	for (int i=0;i<n;i++)
	{
		s[i]=cmp[s[i]],e[i]=cmp[e[i]];
		if (s[i]>e[i])
			mx[s[i]]=m,op.push_back({s[i],e[i]});
		mx[s[i]]=max(mx[s[i]],e[i]);
	}
	if (op.empty())
	{
		cout<<-1<<endl;
		return 0;
	}
	for (int i=1;i<=m;i++)
		mx[i]=max(mx[i],mx[i-1]);
	int ans=-1;
	for (auto i:op)
	{
		int cnt=1,prt=i.second;
		while (prt<i.first)
		{
			if (mx[prt]<=prt)
				break;
			prt=mx[prt],cnt++;
		}
		if (prt>=i.first)
		{
			if (ans==-1)
				ans=cnt;
			ans=min(ans,cnt);
		}
	}
	cout<<ans<<endl;
	
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 21 / 21
• Subtask 6: 26 / 26