各位大佬分析一下时间复杂度,应该是nlogm吧?
查看原帖
各位大佬分析一下时间复杂度,应该是nlogm吧?
207671
王烨楼主2021/10/24 22:11
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=100010;
int n,m1,m2;
int ans=0;
struct Node{
	int s,e;
}a[N],b[N];
int st1[N],ov1[N],st2[N],ov2[N];
priority_queue <PII,vector<PII>,greater<PII> > q;
priority_queue <int,vector<int>,greater<int> > fore;
bool cmp(Node x,Node y){
	return x.s<y.s;
}
void work(int m,Node p[],int st[],int ov[]){
	while(q.size()) q.pop();
	while(fore.size()) fore.pop();
	int t=1;
	for(int i=1;i<=m;i++){
		if(i!=1){
			auto k=q.top();
			while(p[i].s>k.first){
				fore.push(k.second);
				ov[k.second]=0;
				q.pop();
				if(q.size()) k=q.top();
				else break;
			}
			if(fore.size()){
				t=fore.top();
				fore.pop();
			}
		}
		while(ov[t]) t++;
		st[t]++,ov[t++]=p[i].e;
		q.push({p[i].e,t-1});
	}
}
int main(){
	scanf("%d%d%d",&n,&m1,&m2);
	for(int i=1;i<=m1;i++) scanf("%d%d",&a[i].s,&a[i].e);
	for(int i=1;i<=m2;i++) scanf("%d%d",&b[i].s,&b[i].e);
	sort(a+1,a+m1+1,cmp);
	sort(b+1,b+m2+1,cmp);
	work(m1,a,st1,ov1);
	work(m2,b,st2,ov2);
	for(int i=1;i<=n;i++) st1[i]+=st1[i-1];
	for(int i=1;i<=n;i++) st2[i]+=st2[i-1];
	for(int i=0;i<=n;i++){
		int j=n-i;
		if(ans<st1[i]+st2[j]) ans=st1[i]+st2[j];
	}
	printf("%d\n",ans);
	return 0;
}
2021/10/24 22:11
加载中...