Submission #1140026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140026		Faisal_Saqib	Fire (BOI24_fire)	C++20	31 / 100	324 ms	427444 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N=602,M=4e5+100;

int dp[N][N][N];
int s[M],e[M],mpe[M],mps[M],ord[M];
vector<int> s_p;
bool funot(int a,int b)
{
	return (s[a]<s[b] or (s[a]==s[b] and e[a]<e[b]));
}

const int SZ=633;
int lazy[SZ],mi[SZ];
int val[M];

void init(int sp)
{
	for(int i=0;i<=sp;i++)
	{
		val[i]=M;
	}
	for(int i=0;i<SZ;i++)
	{
		mi[i]=lazy[i]=M;
	}
}
int get(int l,int r)
{
	int ans=M;
	while(l<=r)
	{
		ans=min(ans,lazy[l/SZ]);
		if(l%SZ==0 and (l+SZ-1)<=r)
		{
			ans=min(ans,mi[l/SZ]);
			l+=SZ;
		}
		else
		{
			ans=min(ans,val[l]);
			l++;
		}
	}
	return ans;
}
void remake(int block)
{
	mi[block]=lazy[block];
	for(int p=block*SZ;p<(block+1)*SZ;p++)
	{
		mi[block]=min(mi[block],val[p]);
	}
}
void update(int l,int r,int valp)
{
	int bl1=l/SZ,bl2=r/SZ;
	while(l<=r)
	{
		if(l%SZ==0 and (l+SZ-1)<=r)
		{
			lazy[l/SZ]=min(lazy[l/SZ],valp);
			l+=SZ;
		}
		else
		{
			val[l]=min(val[l],valp);
			l++;
		}
	}
	remake(bl1);
	remake(bl2);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		ord[i]=i;
		cin>>s[i]>>e[i];
		s_p.push_back(s[i]);
		s_p.push_back(e[i]);
		// if(s[i]>0)
		// 	s_p.push_back(s[i]-1);
		// if((s[i]+1)<m)
		// 	s_p.push_back(s[i]+1);
		// if((e[i]+1)<m)
		// 	s_p.push_back(e[i]+1);
		// if(e[i]>0)
		// 	s_p.push_back(e[i]-1);
	}
	sort(ord,ord+n,funot);
	s_p.push_back(0);
	s_p.push_back(m-1);
	sort(begin(s_p),end(s_p));
	s_p.resize(unique(begin(s_p),end(s_p))-begin(s_p));
	int sz=s_p.size();
	if(n<=300)
	{
		for(int i=0;i<=n;i++)
		{
			if(i<n)
			{
				mps[i]=lower_bound(begin(s_p),end(s_p),s[i])-begin(s_p);
				mpe[i]=lower_bound(begin(s_p),end(s_p),e[i])-begin(s_p);
			}
			for(int j=0;j<sz;j++)
			{
				for(int k=0;k<sz;k++)
				{
					dp[i][j][k]=n+1e5;
				}
			}
		}
		int ans=n+1e5;
		for(int iads=0;iads<n;iads++)
		{
			int i=ord[iads];
			for(int j=0;j<sz;j++)
				for(int k=j;k<sz;k++)
					dp[iads+1][j][k]=min(dp[iads+1][j][k],dp[iads][j][k]);
			if(s[i]<=e[i])
			{
				for(int j=0;j<sz;j++)
				{
					for(int k=j;k<sz;k++)
					{
						int l=s_p[j],r=s_p[k];
						if(s[i]<=l and r<=e[i])
						{
							// can be covered using only current meaning i
							dp[iads+1][j][k]=min(dp[iads+1][j][k],1);
						}
						if(s[i]<=r)
							dp[iads+1][j][max(k,mpe[i])]=min(dp[iads+1][j][max(k,mpe[i])],dp[iads][j][k]+1);
					}
				}
			}
			else
			{
				for(int j=0;j<sz;j++)
				{
					for(int k=j;k<sz;k++)
					{
						int l=s_p[j],r=s_p[k];
						if(s[i]<=l)
						{
							// simply it is two segments [0,e[i]] and [s[i],m]
							ans=min(ans,dp[iads][mpe[i]][mps[i]]+1);
							// 
							// can be covered using only current meaning i
							dp[iads+1][j][k]=min(dp[iads+1][j][k],1);
						}
						if(r<=e[i])
							dp[iads+1][j][k]=min(dp[iads+1][j][k],1);							
						if(s[i]<=r)
						{
							// cover [l,r]
							// we can do [r,m]
							// [l,m]
							// s[i] to m
							dp[iads+1][j][sz-1]=min(dp[iads+1][j][sz-1],dp[iads][j][k]+1);
						}
						if(l<=e[i])
						{
							// cover [l,r]
							// we can do [0,l]
							// [0,r]
							dp[iads+1][0][k]=min(dp[iads+1][0][k],dp[iads][j][k]+1);
						}
						if(l<=e[i] and s[i]<=r)
						{
							dp[iads+1][0][sz-1]=min(dp[iads+1][0][sz-1],dp[iads][j][k]+1);
							ans=min(ans,dp[iads][j][k]+1);
						}
					}
				}
			}
		}
		ans=min(ans,dp[n][0][sz-1]);
		if(ans>n)
			ans=-1;
		cout<<ans<<endl;
	}
	else
	{
		// solve subtask s<e

		// solve dp[n][0][end_position]
		// dp[i] = min answer to cover [0,i] 
		
		// if currently we have [l,r]
		// then we update the dp as follow:

		// i in [0,l-1]
			// no update

		// i in [l,r]
			// l<=x<=r
			//dp[x] = min (dp[i]+1)
			//dp[i] = suf_min(i)
			//dp[r]=range_min(l,r)+1
		for(int i=0;i<n;i++)
		{
			ord[i]=i;
			if(e[i]==0)e[i]=m-1;
			mps[i]=lower_bound(begin(s_p),end(s_p),s[i])-begin(s_p);
			mpe[i]=lower_bound(begin(s_p),end(s_p),e[i])-begin(s_p);
		}
		sort(ord,ord+n,funot);
		init(sz);
		update(0,0,0);
		for(int kp=0;kp<n;kp++)
		{
			int i=ord[kp];

			int cur=get(mps[i],mpe[i]);
			update(mps[i],mpe[i],cur+1);
		}
		int cur=get(sz-1,sz-1);
		if(cur>n)
			cur=-1;
		cout<<cur<<endl;
	}
}

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