90pts WA#9求调
查看原帖
90pts WA#9求调
911834
bangdeng楼主2024/2/25 21:49

rt

#include<bits/stdc++.h>
#define int long long
#define lc (u<<1)
#define rc (u<<1|1)
#define mid ((tr[u].l+tr[u].r)>>1)
using namespace std;
const int N=1e7+1;
int T,n,g,w,x,y,lig,X[N],szx,ans;
struct node{int l,r,h,li;}line[N];
struct tree{int l,r,maxx,add;}tr[N];
bool cmpl(node a,node b){return a.h<b.h;}
bool cmpx(int a,int b){return a<b;}
void pushup(int u){tr[u].maxx=max(tr[lc].maxx,tr[rc].maxx);}
void pushdown(int u)
{
	tr[lc].maxx+=tr[u].add;
	tr[rc].maxx+=tr[u].add;
	tr[lc].add+=tr[u].add;
	tr[rc].add+=tr[u].add;
	tr[u].add=0;
}
void build(int u,int l,int r)
{
	tr[u].l=l,tr[u].r=r;
	tr[u].add=tr[u].maxx=0;
	if(l==r)return;
	build(lc,l,mid);
	build(rc,mid+1,r);
}
void update(int u,int l,int r,int k)
{
	if(l>X[tr[u].r]||r<X[tr[u].l])return;
	if(l<=X[tr[u].l]&&r>=X[tr[u].r])
	{
		tr[u].maxx+=k;
		tr[u].add+=k;
		return;
	}
	pushdown(u);
	update(lc,l,r,k);
	update(rc,l,r,k);
	pushup(u);
}
signed main()
{
	scanf("%lld",&T);
	while(T--)
	{
		ans=0;
		scanf("%lld%lld%lld",&n,&w,&g);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld%lld%lld",&x,&y,&lig);
			line[i]={x,x+w,y,lig};
			line[i+n]={x,x+w,y+g-1,-lig};
			X[i]=x;
			X[i+n]=x+w;
		}
		n<<=1;
		sort(line+1,line+1+n,cmpl);
		sort(X+1,X+n+1,cmpx);
		szx=unique(X+1,X+1+n)-X-1;
		build(1,1,szx);
		for(int i=1;i<=n;i++)
		{
			update(1,line[i].l,line[i].r-1,line[i].li);
			ans=max(ans,tr[1].maxx);
		}
		printf("%lld\n",ans);
	}
}
2024/2/25 21:49
加载中...