求助,不知道哪里错了
查看原帖
求助,不知道哪里错了
244362
L2007楼主2021/10/17 20:51

WA了九个点

#include<bits/stdc++.h>
#define int long long
#define N 1000005
using namespace std;
int T,n,W,H,id[N],len,add[N];
struct cxl{int l,r,h,s;}line[N];
struct tree{int l,r,mx;}t[N];
bool cmp(cxl x,cxl y){return x.h<y.h;}
void build(int o,int l,int r){
    t[o]=(tree){l,r,0};
    int mid=(l+r)>>1;
    if(l==r)return;
    build((o<<1),l,mid);
    build((o<<1)+1,mid+1,r);
}
void update(int o,int l,int r,int x){
    int nl=t[o].l,nr=t[o].r;
    if(id[nr]<l||r<id[nl])return;
    if(l<=id[nl]&&id[nr]<=r){
        add[o]+=x;
        t[o].mx+=x;
        return;
    }
    if(add[o]!=0){
    	t[(o<<1)].mx+=add[o];
    	t[(o<<1)+1].mx+=add[o];
        add[(o<<1)]+=add[o];
        add[(o<<1)+1]+=add[o];
        add[o]=0;
    }
    update((o<<1),l,r,x);
    update((o<<1)+1,l,r,x);
    t[o].mx=max(t[(o<<1)].mx,t[(o<<1)+1].mx);
}
signed Main(){
	memset(t,0,sizeof(t));
    scanf("%lld%lld%lld",&n,&W,&H);
    for(int x,y,z,i=1;i<=n;i++){
        scanf("%lld%lld%lld",&x,&y,&z);
        int x1=x,y1=y,x2=x+W-1,y2=y+H-1;
        id[(i<<1)-1]=x1,id[(i<<1)]=x2;
        line[(i<<1)-1]=(cxl){x1,x2,y1,z};
        line[(i<<1)]=(cxl){x1,x2,y2,-z};
    }
    n=n<<1;
    sort(line+1,line+n+1,cmp);
    sort(id,id+n+1);
    len=unique(id,id+n+1)-id-1;
    build(1,1,len);
    int ans=-(int)2147483648;
    for(int i=1;i<n;i++){
        update(1,line[i].l,line[i].r,line[i].s);
        ans=max(ans,t[1].mx);
    }
    printf("%lld\n",ans);
    return 0;
}   
signed main(){
    scanf("%lld",&T);
    while(T--)Main();
    return 0;
}
2021/10/17 20:51
加载中...