萌新请求帮助qwq
查看原帖
萌新请求帮助qwq
57273
Reywmp楼主2020/10/29 20:32
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define N 10005
#define ll long long
using namespace std;

ll mx(ll a,ll b){return a>b?a:b;}

ll t;
ll n,w,h;
ll LS(ll p){return p<<1;}
ll RS(ll p){return p<<1|1;}

ll p[N<<1];
struct info
{
	ll x,y,w;
}a[N];

struct Rey
{
	ll l,r;
	ll mxn,lazadd;
}T[N<<2];

struct SP
{
	ll l,r,len,val;
	ll st,ed;
	bool operator <(const SP &now) const
	{
		return len==now.len?val>now.val:len<now.len;
	}
}star[N<<2];

/*bool cmp1(SP P,SP Q)
{
	if(P.len==Q.len)return P.val>Q.val;
	else return P.len<Q.len;
}*/

void UPDATE_max(ll p)
{
	T[p].mxn=mx(T[LS(p)].mxn,T[RS(p)].mxn);
}

void build(ll p,ll l,ll r)
{
	T[p].l=l;T[p].r=r;
	T[p].mxn=T[p].lazadd=0;
	if(l==r)return;
	ll mid=(l+r)>>1;
	build(LS(p),l,mid);
	build(RS(p),mid+1,r);
}

void pushdown(ll p)
{
	T[LS(p)].mxn+=T[p].lazadd;
	T[RS(p)].mxn+=T[p].lazadd;
	T[LS(p)].lazadd+=T[p].lazadd;
	T[RS(p)].lazadd+=T[p].lazadd;
	T[p].lazadd=0;
}

void FIX(ll p,ll l,ll r,ll x)
{
	if(r<T[p].l||T[p].r<l)return ;
	if(r>=T[p].r&&T[p].l>=l)
	{
		T[p].mxn+=x;
		T[p].lazadd+=x;
		return ;
	}
	pushdown(p);
	FIX(LS(p),l,r,x);
	FIX(RS(p),l,r,x);
	UPDATE_max(p); 
}

int main()
{
	scanf("%lld",&t);
	while(t--)
	{
		memset(a,0,sizeof(a));
		memset(T,0,sizeof(T));
		memset(star,0,sizeof(star));
		memset(p,0,sizeof(p));
		scanf("%lld %lld %lld",&n,&w,&h);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].w);
		}
		for(int i=1;i<=n;i++)
		{
			p[i<<1]=a[i].y+h-1;
			p[(i<<1)-1]=a[i].y;
			star[(i<<1)-1].l=star[(i<<1)].l=a[i].y;
			star[(i<<1)-1].r=star[(i<<1)].r=a[i].y+h-1;
			star[(i<<1)-1].len=a[i].x;star[(i<<1)-1].val=a[i].w; 
			star[i<<1].len=a[i].x+w-1;star[i<<1].val=-a[i].w;
		}
		n=n<<1; 
		sort(p+1,p+1+n);
		sort(star+1,star+1+n);
		/*for(int i=1;i<=n;i++)
		{
			printf("%lld %lld\n",star[i].l,star[i].r);
		}
		for(int i=1;i<=n;i++)
		{
			printf("%lld ",p[i]); 
		}*/
		ll num=unique(p+1,p+1+n)-p-1;
		//printf("%lld\n",num);
		for(int i=1;i<=n;i++)
		{ 
			star[i].st=lower_bound(p+1,p+1+num,star[i].l)-p-1;
			star[i].ed=lower_bound(p+1,p+1+num,star[i].r)-p-1;
		}
		build(1,1,num-1);
		ll ans=0;
		for(int i=1;i<=n;i++)
		{
			//printf("%lld %lld\n",star[i].st,star[i].ed);
			FIX(1,star[i].st,star[i].ed,star[i].val);
			ans=mx(ans,T[1].mxn);
		}
		printf("%lld\n",ans);
	}
	return 0;
} 

80分 请求帮助qwq,调了一个下午了

2020/10/29 20:32
加载中...