不管怎么做都RE九个点,路过dalao帮帮蒟蒻吧qwq
查看原帖
不管怎么做都RE九个点,路过dalao帮帮蒟蒻吧qwq
519384
Link_Cut_Y楼主2021/9/3 19:19

码风略丑,请见谅……

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>

using namespace std;

const int N=1000010;

struct Segment
{
	int l,r;
	int h,val;
	
	bool operator < (const Segment &w)const
	{
		return (h!=w.h)?h<w.h:val>w.val;
	}
}seg[N<<2];

struct Tree
{
	int l,r;
	int maxn,add;
}tr[N<<2];

void pushup(int u)
{
	tr[u].maxn=max(tr[u<<1].maxn,tr[u<<1|1].maxn);
}

void build(int u,int l,int r)
{
	tr[u]={l,r,0,0};
	if(l==r) return;
	
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
}

void pushdown(int u)
{
	tr[u<<1].maxn+=tr[u].add;
	tr[u<<1|1].maxn+=tr[u].add;
	
	tr[u<<1].add+=tr[u].add;
	tr[u<<1|1].add+=tr[u].add;
	
	tr[u].add=0;
}

void modify(int u,int l,int r,int d)
{
	if(tr[u].l>=l && tr[u].r<=r)
	{
		tr[u].maxn+=d;
		tr[u].add+=d;
		return;
	}
	
	pushdown(u);
	int mid=(l+r)>>1;
	
	if(l<=mid) modify(u<<1,l,r,d);
	if(r>mid) modify(u<<1|1,l,r,d);
	
	pushup(u);
}

int cnt;
int c[N<<2];

int find(int x)
{
	return lower_bound(c+1,c+cnt+1,x)-c-1;
}

int T,n,h,w;

int main()
{
	scanf("%d",&T);
	
	while(T--)
	{
		memset(seg,0,sizeof seg);
		memset(tr,0,sizeof tr);
		
		scanf("%d%d%d",&n,&w,&h);
		for(int i=1;i<=n;i++)
		{
			int x,y,l;
			scanf("%d%d%d",&x,&y,&l);
			
			c[(i<<1)-1]=y;
			c[(i<<1)]=y+h-1;
			
			seg[(i<<1)-1]=(Segment){y,y+h-1,x,l};
			seg[(i<<1)]=(Segment){y,y+h-1,x+w-1,-l};
		}
		n<<=1;
	
		sort(c+1,c+n+1);
		sort(seg+1,seg+n+1);
		
		cnt=unique(c+1,c+n+1)-c-1;
		
		for(int i=1;i<=n;i++)
		{
			int pos1=find(seg[i].l);
			int pos2=find(seg[i].r);
			
			seg[i].l=pos1;
			seg[i].r=pos2;
		}
		
		build(1,1,cnt-1);
		
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			modify(1,seg[i].l,seg[i].r,seg[i].val);
			ans=max(ans,tr[1].maxn);
		}
		
		printf("%d\n",ans);
	}
	
	return 0;
}
2021/9/3 19:19
加载中...