WA,只过了一个点

回复帖子

@Scultura_Zhao 2020-08-23 12:40 回复

救救我吧~

测评记录

#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;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。