O(mlogm)算法超时求调(悬关)
查看原帖
O(mlogm)算法超时求调(悬关)
1145602
dongzhenmao楼主2024/8/17 12:32
#include <stdio.h>
#include <ctype.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#define lnt long long
#define inf 0x3f3f3f3f
using namespace std;
int xx;char ff,chh;inline int read(){
    xx=ff=0;while(!isdigit(chh)){if(chh=='-'){ff=1;}chh=getchar();}
    while(isdigit(chh)){xx=(xx<<1)+(xx<<3)+chh-'0';chh=getchar();}return ff? -xx: xx;
}
const int N=2e6;
struct node{
	node *lt,*nx;
	int date,v;
	void del(){lt->nx=nx;nx->lt=lt;}
}*a,*b,*ai,*bi,_new[N];int top=0;
struct tl{
	int b,date,v;
}sr[N];
int n,m1,m2,pa[N],pb[N];
node *ak[N],*bk[N];
int main(){
	ai=a=&_new[top++];bi=b=&_new[top++];
	n=read();m1=read();m2=read();
	a->nx=&_new[top++];a->nx->lt=a;a=a->nx;
	b->nx=&_new[top++];b->nx->lt=b;b=b->nx;
	for(int i=0;i<m1;++i){
		sr[i<<1]={read(),i,1};
		sr[(i<<1)+1]={read(),i,-1};
	}
	sort(sr,sr+m1*2,[](tl x,tl y){return x.b<y.b;});
	for(int i=0;i<m1*2;++i){
		a->nx=&_new[top++];
		a->date=sr[i].date;
		a->v=sr[i].v;
		a->nx->lt=a;
		if(a->v==-1){
			ak[a->date]=a;
		}
		a=a->nx;
	}
	for(int i=0;i<m2;++i){
		sr[i<<1]={read(),i,1};
		sr[(i<<1)+1]={read(),i,-1};
	}
	sort(sr,sr+m2*2,[](tl x,tl y){return x.b<y.b;});
	for(int i=0;i<m2*2;++i){
		b->nx=&_new[top++];
		b->date=sr[i].date;
		b->v=sr[i].v;
		b->nx->lt=b;
		if(b->v==-1){
			bk[b->date]=b;
		}
		b=b->nx;
	}
	a=ai;b=bi;
	for(int i=1;i<=n;++i){
		int cnt=0;
		for(node *e=a->nx;e->nx!=NULL;){
			if(e->v==1){
				node *u=e;
				e=ak[e->date];
				u->del();
				u=e;
				e=e->nx;
				u->del();
				++cnt;
			}else{e=e->nx;}
		}
		pa[i]=pa[i-1]+cnt;
	}
	for(int i=1;i<=n;++i){
		int cnt=0;
		for(node *e=b->nx;e->nx!=NULL;){
			if(e->v==1){
				node *u=e;
				e=bk[e->date];
				u->del();
				u=e;
				e=e->nx;
				u->del();
				++cnt;
			}else{e=e->nx;}
		}
		pb[i]=pb[i-1]+cnt;
	}
	int ans=0;
	for(int i=0;i<=n;++i){
		ans=max(ans,pa[i]+pb[n-i]);
	}	
	printf("%d",ans);
	
	
	
    return 0;
}

删除sort就变成WA

2024/8/17 12:32
加载中...