#9wa 有点迷惑,改下上线就a了
查看原帖
#9wa 有点迷惑,改下上线就a了
71150
YL_9楼主2021/5/26 20:35
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e4+9;
int T,n,W,H,len;
int ls[N*2];
LL ans;
struct Star
{
	int x,xx,y,l;
	bool operator < (const Star &x) const
	{
		if(y==x.y) return l<x.l;
		else return y>x.y;
	}
}s[N*2];
struct Segment_Tree
{
	int l,r;
	LL mx,lazy;
}t[N*16];
inline int read()
{
	int tot=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') {tot=tot*10+ch-'0'; ch=getchar();}
	return tot*w;
}
void Build(int x,int l,int r)
{
	t[x]={l,r,0,0};
	if(l==r) return;
	int mid=(l+r)/2;
	Build(x*2,l,mid);
	Build(x*2+1,mid+1,r);
}
void Spread(int x)
{
	t[x*2].mx+=t[x].lazy;
	t[x*2+1].mx+=t[x].lazy;
	t[x*2].lazy+=t[x].lazy;
	t[x*2+1].lazy+=t[x].lazy;
	t[x].lazy=0;
}
void Change(int x,int l,int r,int lt)
{
	if(t[x].l>r||t[x].r<l) return;
	if(l<=t[x].l&&t[x].r<=r)
	{
		t[x].mx+=(LL)lt;
		t[x].lazy+=(LL)lt;
		Spread(x);
		return;
	}
	Change(x*2,l,r,lt);
	Change(x*2+1,l,r,lt);
	Spread(x);
	t[x].mx=max(t[x*2].mx,t[x*2+1].mx);
}
int Get(int x)
{
	return lower_bound(ls+1,ls+1+len,x)-ls;
}
int main()
{
	T=read();
	while(T--)
	{
		n=read(); W=read(); H=read();
		for(int i=1;i<=n;i++)
		{
			int x=read(),y=read(),l=read();
			s[i]={x,x+W-1,y,-l};
			s[i+n]={x,x+W-1,y+H-1,l};//*
			ls[i*2-1]=x;
			ls[i*2]=x+W-1;
		}
		sort(ls+1,ls+1+n*2);
		len=unique(ls+1,ls+1+n*2)-ls-1;
		sort(s+1,s+1+n*2);
		Build(1,1,len);
		ans=0;
		for(int i=1;i<=n*2;i++)
		{
			int x=Get(s[i].x),xx=Get(s[i].xx);
			Change(1,x,xx,s[i].l);
			ans=max(ans,t[1].mx);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

s[i+n]={x,x+W-1,y+H-1,l};//*

改成

s[i+n]={x,x+W-1,y+H,l};

就过了

2021/5/26 20:35
加载中...