95分求助!
查看原帖
95分求助!
334041
沉鸣cmh楼主2021/11/14 20:51

第9个点WA了答案是5000我是2500,怎么回事。。。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,n1,n2,tmp[400005],t,ans,gn[100005],gw[100005];
priority_queue<ll,vector<ll>,greater<ll> >q1;
struct pp{
	ll id,t;
    friend bool operator<(pp x,pp y){
	    return x.t>y.t;
    }
};
priority_queue<pp>q2;
struct p{
	ll s,t;
}a[100005],b[100005];
bool cmp(p x,p y){
	if(x.s!=y.s)return x.s<y.s;return x.t<y.t;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>n1>>n2;
	for(int i=1;i<=n1;i++)cin>>a[i].s>>a[i].t,tmp[++t]=a[i].s,tmp[++t]=a[i].t;
	for(int i=1;i<=n2;i++)cin>>b[i].s>>b[i].t,tmp[++t]=b[i].s,tmp[++t]=b[i].t;
	sort(tmp+1,tmp+t+1);int m=unique(tmp+1,tmp+t+1)-tmp-1;
	for(int i=1;i<=n1;i++)a[i].s=lower_bound(tmp+1,tmp+t+1,a[i].s)-tmp,
	a[i].t=lower_bound(tmp+1,tmp+t+1,a[i].t)-tmp;
	for(int i=1;i<=n2;i++)b[i].s=lower_bound(tmp+1,tmp+t+1,b[i].s)-tmp,
	b[i].t=lower_bound(tmp+1,tmp+t+1,b[i].t)-tmp;
	sort(a+1,a+n1+1,cmp),sort(b+1,b+n2+1,cmp);
	for(int i=1;i<=n;i++)q1.push(i);
	for(int i=1;i<=n1;i++){
		while(!q2.empty())if(q2.top().t<a[i].s)
		q1.push(q2.top().id),q2.pop();else break;
		if(q1.empty())continue;
		pp o;o.id=q1.top(),o.t=a[i].t,q1.pop(),gn[o.id]++,q2.push(o);
	}for(int i=1;i<=n1;i++)gn[i]+=gn[i-1];
	while(!q1.empty())q1.pop();while(!q2.empty())q2.pop();
	for(int i=1;i<=n;i++)q1.push(i); 
	for(int i=1;i<=n2;i++){
		while(!q2.empty())if(q2.top().t<b[i].s)
		q1.push(q2.top().id),q2.pop();else break;
		if(q1.empty())continue;
		pp o;o.id=q1.top(),o.t=b[i].t,q1.pop(),gw[o.id]++,q2.push(o);
	}for(int i=1;i<=n2;i++)gw[i]+=gw[i-1];
	for(int i=0;i<=n;i++)ans=max(ans,gn[i]+gw[n-i]);
	cout<<ans;
	return 0;
}
2021/11/14 20:51
加载中...