救救我吧~

测评记录

#include "bits/stdc++.h"
using namespace std;
#define Long long long int
#define MAXN 101000

Long A[MAXN];
struct NPC{
	struct SegmentTree{
		int Left,Right;
		Long Lazy,Max;
	}Tree[MAXN<<2];
	inline int LeftSon(int i){return i<<1;}
	inline int RightSon(int i){return i<<1|1;}
	inline void Build(int i,int Left,int Right){
		Tree[i].Left=Left;
		Tree[i].Right=Right;
		Tree[i].Max=Tree[i].Lazy=0;
		if(Left==Right)
			return;
		int Mid=(Left+Right)>>1;
		int L=LeftSon(i),R=RightSon(i);
		Build(L,Left,Mid);
		Build(R,Mid+1,Right);
		return;
	}
	inline void PushDown(int i){
		if(Tree[i].Lazy==0)
			return;
		int L=LeftSon(i),R=RightSon(i);
		Tree[L].Lazy=Tree[L].Lazy+Tree[i].Lazy;
		Tree[R].Lazy=Tree[R].Lazy+Tree[i].Lazy;
		Tree[L].Max=Tree[L].Max+Tree[i].Lazy;
		Tree[R].Max=Tree[R].Max+Tree[i].Lazy;
		Tree[i].Lazy=0;
		return;
	}
	inline void AddSeg(int i,Long Left,Long Right,Long Add){
		if(A[Tree[i].Right]<Left||Right<A[Tree[i].Left])
			return;
		if(Left<=A[Tree[i].Left]&&A[Tree[i].Right]<=Right){
			Tree[i].Lazy=Tree[i].Lazy+Add;
			Tree[i].Max=Tree[i].Max+Add;
			PushDown(i); 
			return;
		}
		PushDown(i);
		int L=LeftSon(i),R=RightSon(i);
		if(A[Tree[L].Right]>=Left)AddSeg(L,Left,Right,Add);
		if(A[Tree[R].Left]<=Right)AddSeg(R,Left,Right,Add);
		Tree[i].Max=max(Tree[L].Max,Tree[R].Max);
		return;
	}
	inline Long Query(int i,Long Left,Long Right){
		if(A[Tree[i].Right]<Left||Right<A[Tree[i].Left])
			return 0;
		if(Left<=A[Tree[i].Left]&&A[Tree[i].Right]<=Right)
			return Tree[i].Max;
		PushDown(i);
		Long Max=0,L=LeftSon(i),R=RightSon(i);
		if(A[Tree[L].Right]>=Left)Max=max(Max,Query(L,Left,Right));
		if(A[Tree[R].Left]<=Right)Max=max(Max,Query(R,Left,Right));
		return Max;
	}
}Do;

struct Unsigned{
	Long Left,Right,H,Mark;
	inline void Clear(void){
		Left=Right=H=Mark=0;
		return;
	}
	friend bool operator <(Unsigned A,Unsigned B){
		if(A.H==B.H)
			return A.Mark>B.Mark;
		return A.H<B.H;
	}
}Line[MAXN];

Long T,N,M,AddX,AddY,X,Y,Z;
int main(void){
	scanf("%lld",&T);
	for(register int Txt=1;Txt<=T;Txt++){
		scanf("%lld%lld%lld",&N,&AddX,&AddY);
		for(register int i=1;i<=N*2;i++)
			Line[i].Clear(),A[i]=0;
		for(register int i=1;i<=N;i++){
			scanf("%lld%lld%lld",&X,&Y,&Z);
			#define j (i<<1)-1
			#define k i<<1
			Line[j]=(Unsigned){X,X+AddX-1,Y,Z};
			Line[k]=(Unsigned){X,X+AddX-1,Y+AddY-1,-Z};
			A[j]=X,A[k]=X+AddX-1;
		}
		N<<=1;
		sort(A+1,A+N+1);
		sort(Line+1,Line+1+N);
		Long Top=unique(A+1,A+1+N)-A-1;
		Do.Build(1,1,Top);
		
		Long Max=0;
		for(register int i=1;i<=N;i++){
			Do.AddSeg(1,Line[i].Left,Line[i].Right,Line[i].Mark);
			Max=max(Max,Do.Query(1,1,Top));
		}
		printf("%lld\n",Max);
	}
	return 0;
}