Submission #1140029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140029		MuhammadSaram	Fire (BOI24_fire)	C++17	100 / 100	807 ms	199364 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int M = 8e5 + 1, lg = 20;

int maxx[M][lg],ind[M][lg],nxt[M][lg];

int get(int l,int r)
{
	int b=31-__builtin_clz(r-l);
	int mx=max(maxx[l][b],maxx[r-(1<<b)][b]);
	if (mx==maxx[l][b])
		return ind[l][b];
	return ind[r-(1<<b)][b];
}

int main()
{
	int n,m;
	cin>>n>>m;
	set<pair<int,int>> se,se1;
	vector<pair<int,int>> v;
	set<int> vl;
	for (int i=0;i<2*n;i++)
		for (int p=0;p<lg;p++)
			ind[i][p]=-1;
	int s[n],e[n];
	for (int i=0;i<n;i++)
	{
		cin>>s[i]>>e[i];
		vl.insert(s[i]),vl.insert(e[i]);
	}
	map<int,int> id;
	for (int i:vl)
		id[i]=id.size();
	int k=id.size();
	for (int i=0;i<n;i++)
	{
		s[i]=id[s[i]],e[i]=id[e[i]];
		if (s[i]<e[i])
			v.push_back({s[i],e[i]}),v.push_back({s[i]+k,e[i]+k});
		else
			v.push_back({s[i],e[i]+k});
	}
	sort(v.begin(),v.end());
	for (int i=0;i<n;i++)
	{
		if (s[i]<e[i])
		{
			maxx[s[i]][0]=max(maxx[s[i]][0],e[i]);
			maxx[s[i]+k][0]=max(maxx[s[i]+k][0],e[i]+k);
		}
		else
			maxx[s[i]][0]=max(maxx[s[i]][0],e[i]+k);
	}
	for (int i=0;i<2*k;i++)
	{
		ind[i][0]=-1;
		if (maxx[i][0])
			ind[i][0]=lower_bound(v.begin(),v.end(),make_pair(i,maxx[i][0]))-begin(v);
	}
	for (int p=1;p<lg;p++)
		for (int i=0;i+(1<<p)<=4*n;i++)
		{
			maxx[i][p]=max(maxx[i][p-1],maxx[i+(1<<p-1)][p-1]),ind[i][p]=ind[i][p-1];
			if (maxx[i][p]!=maxx[i][p-1])
				ind[i][p]=ind[i+(1<<p-1)][p-1];
		}
	for (int i=0;i<v.size();i++)
	{
		nxt[i][0]=get(v[i].first,v[i].second+1);
		if (nxt[i][0]==i)
			nxt[i][0]=-1;
	}
	for (int p=1;p<lg;p++)
		for (int i=0;i<v.size();i++)
		{
			if (nxt[i][p-1]==-1)
				nxt[i][p]=-1;
			else
				nxt[i][p]=nxt[nxt[i][p-1]][p-1];
		}
	int ans=n+1;
	for (int i=0;i<v.size();i++)
	{
		if (v[i].first>=k) continue;
		int val=1,x=i;
		for (int p=lg-1;p>=0;p--)
			if (nxt[x][p]!=-1 && v[nxt[x][p]].second<v[i].first+k)
				val+=(1<<p),x=nxt[x][p];
		if (nxt[x][0]!=-1 && v[nxt[x][0]].second>=v[i].first+k)
			ans=min(ans,val+1);
	}
	if (ans==n+1)
		ans=-1;
	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