wa了#9,跪求大佬帮忙看看
查看原帖
wa了#9,跪求大佬帮忙看看
362627
frank15楼主2021/2/1 10:40
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int maxn=2e6+5;
int t,n,w,h,xa,ya,xb,yb,L,pos1,pos2,tot,ans;
struct line_y{
	int x,l,r,flag;
}y[maxn];
int discre[maxn],val[maxn];
bool cmp(line_y X,line_y Y){
	return X.x<Y.x||(X.x==Y.x&&X.flag>Y.flag);
}
struct t{
	int MAX,lazy;
}tree[4*maxn];
void change(int node,int k){
	tree[node].lazy+=k;
	tree[node].MAX+=k;
}
void push_down(int node){
	if(tree[node].lazy){
		int left_node=node<<1;
		int right_node=node<<1|1;
		change(left_node,tree[node].lazy);
		change(right_node,tree[node].lazy);
		tree[node].lazy=0;
	}
}
void update(int node,int l,int r,int aim_L,int aim_R,int k){
	if(l>=aim_R||r<=aim_L)
		return ;
//	cout<<l<<' '<<r<<' '=<<aim_L<<' '<<aim_R<<endl;
	if(aim_L<=l&&r<=aim_R){
		tree[node].lazy+=k;
		tree[node].MAX+=k;
		return ;
	}
	push_down(node);
	int mid=(l+r)>>1;
	int left_node=node<<1;
	int right_node=node<<1|1;
	update(left_node,l,mid,aim_L,aim_R,k);
	update(right_node,mid,r,aim_L,aim_R,k);
	tree[node].MAX=max(tree[left_node].MAX,tree[right_node].MAX);
}
signed main(){
	scanf("%lld",&t);
	while(t--){
//		fill(tree+1,tree+maxn+1,0);
		ans=0;
		scanf("%lld%lld%lld",&n,&w,&h);
		memset(tree,sizeof(tree),0);
		for(int i=1;i<=n;i++){
			scanf("%lld%lld%lld",&xa,&ya,&L);
			xb=xa+w-1;
			yb=ya+h-1;
			y[(i<<1)-1].flag=L;
			y[(i<<1)-1].l=yb;
			y[(i<<1)-1].r=ya;
			y[(i<<1)-1].x=xa;
			y[i<<1].flag=-L;
			y[i<<1].l=yb;
			y[i<<1].r=ya;
			y[i<<1].x=xb;
			discre[(i<<1)-1]=ya;
			discre[i<<1]=yb;
		}
		sort(discre+1,discre+(n<<1)+1);
		tot=unique(discre+1,discre+(n<<1)+1)-discre-1;
//		cout<<tot<<endl;
//		for(int i=1;i<=	tot;i++)
//			cout<<discre[i]<<' ';
//		cout<<endl;
		for(int i=1;i<=2*n;i++){
			y[i].l=lower_bound(discre+1,discre+tot+1,y[i].l)-discre;
			y[i].r=lower_bound(discre+1,discre+tot+1,y[i].r)-discre;
		}
		sort(y+1,y+(n<<1)+1,cmp);
		for(int i=1;i<=(n<<1);i++){
//			cout<<y[i].x<<' '<<y[i].flag<<endl;
			update(1,1,tot,y[i].r,y[i].l,y[i].flag);
//			cout<<ans<<endl;
			ans=max(ans,tree[1].MAX);
//			cout<<tre<<endl;
//			for(int i=1;i<=8;i++)
//				cout<<tree[i].MAX<<' '<<tree[i].lazy<<endl;
		}
		printf("%lld\n",ans);
	}
}
2021/2/1 10:40
加载中...