80pts啊啊啊,(悬棺#6#10
查看原帖
80pts啊啊啊,(悬棺#6#10
978200
aqzjklo楼主2025/7/16 16:36

救救我吧,调一下午了

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,w,h,tt,a[40005],tot;
struct stars
{
	int x1,x2,y;
	int w;
} s[40005];
struct tree
{
	int l,r;
	long long b,w;
} t[160005];
bool cmp(stars x, stars y)
{
	return x.y==y.y?x.w>y.w:x.y<y.y;
}
int f(int x)
{
	return lower_bound(a+1,a+tot+1,x)-a;
}
void build(int l,int r,int p)
{
	t[p].w=0;
	t[p].l=l;
	t[p].r=r;
	t[p].b=0;
	if (l==r)
	{
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,p*2);
	build(mid+1,r,p*2+1);
}
void add(int l,int r,int c,int nl,int nr,int p)
{
	if (l<=nl&&r>=nr)
	{
		t[p].w+=c;
		t[p].b+=c;
		return;
	}
	int mid=(nl+nr)/2;
	if (t[p].b)
	{
		t[p*2].w+=t[p].b;
		t[p*2+1].w+=t[p].b;
		t[p*2].b+=t[p].b;
		t[p*2+1].b+=t[p].b;
		t[p].b=0;
	}
	if (l<=mid)
	{
		add(l,r,c,nl,mid,p*2);
	}
	if (r>mid)
	{
		add(l,r,c,mid+1,nr,p*2+1);
	}
	t[p].w=max(t[p*2].w,t[p*2+1].w);
}
long long ans=-1;
signed main()
{
	cin>>tt;
	while (tt--)
	{
		cin>>n>>w>>h;
		for (int i=1;i<=n; i++)
		{
			cin>>s[i].x1>>s[i].y>>s[i].w;
			s[i].x2=s[i].x1+w;
			s[i+n].x1=s[i].x1;
			s[i+n].x2=s[i].x2;
			s[i+n].y=s[i].y+h;
			s[i+n].w=-s[i].w;
			a[i]=s[i].x1;
			a[i+n]=s[i].x2;
		}
		sort(s+1,s+n*2+1,cmp);
		sort(a+1,a+n*2+1);
		tot=unique(a+1,a+2*n+1)-(a+1); 
		build (1,tot-1,1);
		ans=0;
		for (int i=1; i<=2*n; i++)
		{
			add(f(s[i].x1),f(s[i].x2)-1,s[i].w,1,tot-1,1);
			ans=max(ans,t[1].w);
		}
		cout<<ans<<endl;
	}
}
2025/7/16 16:36
加载中...