90 pts 求调 pleaseeee
查看原帖
90 pts 求调 pleaseeee
1125054
__XU__楼主2024/8/3 11:29
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll=long long;
const int N=2e6+5;
struct l{
	int x_1,x_2,y,mark;
	friend bool operator<(l a,l b){
		if(a.y!=b.y){
			return a.y<b.y;
		}
		else{
			return a.mark>b.mark;
		}
	}
}line[N];
struct node{
	ll max;
	int l,r,lazy; 
}tnode[N];
int X[N];
int n;
void push_up(int num){
	tnode[num].max=max(tnode[num*2].max,tnode[num*2+1].max);
	
}
void push_down(int num){
	tnode[num*2].lazy+=tnode[num].lazy; 
	tnode[num*2+1].lazy+=tnode[num].lazy;
	tnode[num*2].max+=tnode[num].lazy;
	tnode[num*2+1].max+=tnode[num].lazy;
	tnode[num].lazy=0;
}
void modify(int num,int L,int R,int v){
	if(X[tnode[num].l]>=R||X[tnode[num].r+1]<=L){
		return;
	}
	if(X[tnode[num].l]>=L&&X[tnode[num].r+1]<=R){
		tnode[num].max+=v;
		tnode[num].lazy+=v;
		return;
	}
	push_down(num);
	modify(num*2,L,R,v);
	modify(num*2+1,L,R,v);
	push_up(num);
}
void build(int num,int l,int r){
	tnode[num].l=l,tnode[num].r=r;
	tnode[num].lazy=tnode[num].max=0;
	if(l==r){
		return;
	}
	int mid=(l+r)/2;
	build(num*2,l,mid);
	build(num*2+1,mid+1,r);
}
int t;
signed main(){
	cin>>t;
	while(t--){
		memset(line,0,sizeof(line));
		memset(X,0,sizeof X);
		int n,w,h;
		cin>>n>>w>>h;
		for(int i=1;i<=n;i++){
			int x,y,l;
			cin>>x>>y>>l;
			X[i*2-1]=y,X[i*2]=y+h-1;
			line[i*2-1].x_1=y;
			line[i*2-1].x_2=y+h-1;
			line[i*2-1].y=x;
			line[i*2-1].mark=l;
			line[i*2].x_1=y;
			line[i*2].x_2=y+h-1;
			line[i*2].y=x+w-1;
			line[i*2].mark=-l;
			
		}
		n<<=1ll;
		sort(line+1,line+1+n);
		sort(X+1,X+1+n);
		int k=unique(X+1,X+1+n)-X-1;
		build(1,1,k-1);
		ll ans=0;
		for(int i=1;i<n;i++){
			modify(1,line[i].x_1,line[i].x_2,line[i].mark);
			ans=max(ans,tnode[1].max);
		}
		cout<<ans<<'\n';
	}
	return 0;
}

不知道哪错了

2024/8/3 11:29
加载中...