求助1502为啥10分

回复帖子

@狂丿Kurumi  2019-10-30 11:35 回复
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3fffff
#define MAXINT 2147482647LL
#define M 1000050
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}
    return x*f;
}
int t,n,w,h,ans;
struct Tree
{
    int lson,rson;
    int lz,x;
}tr[M<<3];

void pushdown(int rx,int l,int r)
{
    if(tr[rx].lz==0)return ;
    tr[tr[rx].lson].x+=tr[rx].lz;
    tr[tr[rx].rson].x+=tr[rx].lz;
    tr[tr[rx].lson].lz+=tr[rx].lz;
    tr[tr[rx].rson].lz+=tr[rx].lz;
    tr[rx].lz=0;
}
void change(int rx,int l,int r,int L,int R,int k)
{
    //cout<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
    if(l>=L&&r<=R)
    {
        tr[rx].x+=k;
        tr[rx].lz+=k;
        return ;
    }
    //cout<<"!"<<endl;
    if(tr[rx].lson==0)
    {
        tr[rx].lson=++t;
        tr[rx].rson=++t;
    }
    pushdown(rx,l,r);
    int mid=(l+r)>>1;
    if(L<=mid) change(tr[rx].lson,l,mid,L,R,k);
    if(R>mid) change(tr[rx].rson,mid+1,r,L,R,k);
    tr[rx].x=max(tr[tr[rx].lson].x,tr[tr[rx].rson].x);
}
struct point 
{
    int x,y,l;
}a[M<<1];
bool cmp(point a,point b)
{
    return a.x<b.x;
}

int main()
{
    int T=read();
    while(T--)
    {
        n=read(),w=read(),h=read();
        ans=0;t=0;
        for(int i=1;i<=n;i++)
        {
            int x=read(),y=read(),l=read();
            a[i*2-1].x=x,a[i*2-1].y=y,a[i*2-1].l=l;
            a[i*2].x=min((ll)x+w,MAXINT),
            a[i*2].y=y,
            a[i*2].l=-l;
        }
        sort(a+1,a+2*n+1,cmp);
        for(int i=1;i<=n*2;i++)
        {

            change(0,1,MAXINT,a[i].y,min((ll)a[i].y+h-1,MAXINT),a[i].l);
            if(a[i+1].x!=a[i].x)ans=max(ans,tr[0].x);
        }
        printf("%d\n",ans);
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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