求助时间复杂度
查看原帖
求助时间复杂度
431265
Fresca楼主2021/10/30 08:11

rt,为什么所有测试点都是300ms左右

记录

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int N=100100;
const int t=100000010;
int MAXnum[2][N],endp[t],MINt,MAXt,ans=0;
typedef pair<int,int> P;
priority_queue<P,vector<P>,greater<P> > pq;
priority_queue<int,vector<int>,greater<int> > nxt;
int n,m[2];
int main()
{
	#ifdef NAME
		freopen("airport.in","r",stdin);
		freopen("airport.out","w",stdout);
	#endif
	n=read(),m[0]=read(),m[1]=read();
	for(int i=1;i<=N;++i)
		nxt.push(i);
	for(int j=0;j<2;++j)
	{
		memset(endp,0,sizeof(endp));
		MINt=2000000000,MINt=0;
		for(int i=1;i<=m[j];++i)
		{
			int a=read(),b=read();
			endp[a]=b;
			MINt=min(MINt,a);
			MAXt=max(MAXt,b);
		}
		for(int i=MINt;i<=MAXt;++i)
		{
			if(!pq.empty())
				if(pq.top().first<=i)
				{
					int temp=pq.top().second;
					pq.pop();
					nxt.push(temp);
				}
			if(endp[i])
			{
				pq.push(P(endp[i],nxt.top()));
				++MAXnum[j][nxt.top()];
				nxt.pop();
			}
		}
		for(int i=2;i<=n;++i)
			MAXnum[j][i]=MAXnum[j][i]+MAXnum[j][i-1];
	}
	for(int i=0;i<=n;++i)
		ans=max(ans,MAXnum[0][i]+MAXnum[1][n-i]);
	printf("%d",ans);
	return 0;
}
2021/10/30 08:11
加载中...