WA 95PTS求助qwq
查看原帖
WA 95PTS求助qwq
591179
huangyuxaing楼主2023/10/19 16:12

交上去一直WA第九个测试点,答案5000,输出2500,码风良好,求大佬帮调

#include<bits/stdc++.h>
using namespace std;
const int M=1e6+7;
int n,m1,m2,cnt[2][M],tot[2][M],pre[2][M],ans;
struct node{
	int l,r,id;
	bool operator<(const node &x)const{return r==x.r?l>x.l:r>x.r;}
}t1[M],t2[M];
priority_queue<int> q;
priority_queue<node> q2;
bool cmp(node x,node y){return x.l==y.l?x.r<y.r:x.l<y.l;}
void solve(node a[],int m,int op){
	while(!q.empty())q.pop();while(!q2.empty())q2.pop(); 
	for(int i=1;i<=m1+m2;i++)q.push(-1*i);
	for(int i=1;i<=m;i++){
		while(!q2.empty()&&q2.top().r<=a[i].l)q.push(-1*cnt[op][q2.top().id]),q2.pop();
		cnt[op][i]=-1*q.top();q.pop();a[i].id=i;
		tot[op][cnt[op][i]]++;q2.push(a[i]);
	}
	for(int i=1;i<=m1+m2;i++)pre[op][i]=pre[op][i-1]+tot[op][i];
}
int main(){
	scanf("%d%d%d",&n,&m1,&m2);
	for(int i=1;i<=m1;i++)scanf("%d%d",&t1[i].l,&t1[i].r);
	for(int i=1;i<=m2;i++)scanf("%d%d",&t2[i].l,&t2[i].r);
	sort(t1+1,t1+m1+1,cmp);sort(t2+1,t2+m2+1,cmp);
	solve(t1,m1,0);solve(t2,m2,1);
	for(int i=0;i<=n;i++)ans=max(ans,pre[0][i]+pre[1][n-i]);
	printf("%d\n",ans);
	return 0;
}
2023/10/19 16:12
加载中...