help!!!wa on 9
查看原帖
help!!!wa on 9
1112113
q9025715056楼主2025/1/20 15:10
#include<stdio.h>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=1e6+7;
struct Tree
{
	int l,r,w,lab;
}t[maxn<<2];
struct point
{
	int x,y1,y2,k;
	bool operator <(const point &a)const
	{
		if(x!=a.x)return x<a.x;
		return k>a.k;
	}
}p[maxn<<1];
int cnt;
int Y[maxn<<1],tail;
void build(int i,int l,int r)
{
	t[i].l=l,t[i].r=r;
	t[i].w=t[i].lab=0;
	if(l==r) return;
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
}
void push(int i)
{
	if(t[i].lab==0) return;
	t[i<<1].w+=t[i].lab,t[(i<<1)+1].w+=t[i].lab;
	t[i<<1].lab+=t[i].lab,t[(i<<1)+1].lab+=t[i].lab;
	t[i].lab=0;
}
void add(int i,int l,int r,int k)
{
	if(Y[t[i].l]>=r||Y[t[i].r+1]<=l) return;
	if(Y[t[i].r+1]<=r&&Y[t[i].l]>=l)
	{
		t[i].w+=k;
		t[i].lab+=k;
		return;
	}
	push(i);
	add(i*2,l,r,k);
	add(i*2+1,l,r,k);
	t[i].w=max(t[i<<1].w,t[(i<<1)+1].w);
}
void solve()
{
	int n,W,H;scanf("%lld%lld%lld",&n,&W,&H);
	cnt=tail=0;
	for(int i=1;i<=n;i++)
	{
		int x,y,w;
		scanf("%lld%lld%lld",&x,&y,&w);
		p[++cnt]={x,y,y+H-1,w};
		p[++cnt]={x+W-1,y,y+H-1,-w};
		Y[++tail]=y+H-1,Y[++tail]=y;
	}
	sort(p+1,p+1+cnt);
	sort(Y+1,Y+1+tail);
	tail=unique(Y+1,Y+1+tail)-Y-1;
	build(1,1,tail-1);
	int ans=0;
	for(int i=1;i<cnt;i++)
	{
		ans=max(t[1].w,ans);
		add(1,p[i].y1,p[i].y2,p[i].k);
	}
	printf("%lld\n",ans);
}
signed main()
{
	int t;scanf("%lld",&t);
	while(t--) solve();
}
2025/1/20 15:10
加载中...