实践证明用了pbds复杂度甚至高于不用(
查看原帖
实践证明用了pbds复杂度甚至高于不用(
426545
light_ght楼主2021/10/23 23:41

rt。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
#define ll long long
#define N 100001
//#define int long long

template<typename T>inline void read(T &ret){
	ret=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	ret*=f;
}
template<typename T,typename... Args>inline void read(T &ret,Args&... args){read(ret);read(args...);}
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)

int n,m1,m2;
struct nd{
	int a,b;
}x[N],y[N];
int ans;

void f(int c,int f){
	__gnu_pbds::priority_queue<int,greater<int>>q,p;
	int u=c,v=f,cnt=0;
	for(int i=1;i<=m1;i++){
		if(q.size())
			while(x[i].a>=q.top()){	
				u++;q.pop();
				if(!q.size())break;
			}
		if(u){
			u--;cnt++;q.push(x[i].b);
			//cerr<<u<<' '<<x[i].b<<'\n';
		}
	}
	for(int i=1;i<=m2;i++){
		if(p.size())
			while(y[i].a>=p.top()){
				v++;p.pop();
				if(!p.size())break;
			}
		if(v){
			v--;cnt++;p.push(y[i].b);
		}	
	}
	ans=max(ans,cnt);
}

signed main(){
	ios::sync_with_stdio(0);
	read(n,m1,m2);
	for(int i=1;i<=m1;i++){
		read(x[i].a,x[i].b);//tmx=max(tmx,x[i].b);
	}
	for(int i=1;i<=m2;i++){
		read(y[i].a,y[i].b);//tmy=max(tmy,y[i].b);
	}
	sort(x+1,x+1+m1,[](nd g,nd h){return g.a<h.a;});
	sort(y+1,y+1+m2,[](nd g,nd h){return g.a<h.a;});

	//int ed1=min(n,m1),ed2=min(n,m2);
	for(int i=0;i<=n;i++)f(i,n-i);
	
	cout<<ans<<endl;

 return 0;
 }
/*
2 4 6
20 30
40 50
21 22
41 42
1 19
2 18
3 4
5 6
7 8
9 10
*/

这个是25pts。 删掉奇怪的东西之后是40pts。

iee

2021/10/23 23:41
加载中...