萌新请求帮助qwq

回复帖子

@Reywmp  2020-10-29 20:32 回复
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define N 10005
#define ll long long
using namespace std;

ll mx(ll a,ll b){return a>b?a:b;}

ll t;
ll n,w,h;
ll LS(ll p){return p<<1;}
ll RS(ll p){return p<<1|1;}

ll p[N<<1];
struct info
{
    ll x,y,w;
}a[N];

struct Rey
{
    ll l,r;
    ll mxn,lazadd;
}T[N<<2];

struct SP
{
    ll l,r,len,val;
    ll st,ed;
    bool operator <(const SP &now) const
    {
        return len==now.len?val>now.val:len<now.len;
    }
}star[N<<2];

/*bool cmp1(SP P,SP Q)
{
    if(P.len==Q.len)return P.val>Q.val;
    else return P.len<Q.len;
}*/

void UPDATE_max(ll p)
{
    T[p].mxn=mx(T[LS(p)].mxn,T[RS(p)].mxn);
}

void build(ll p,ll l,ll r)
{
    T[p].l=l;T[p].r=r;
    T[p].mxn=T[p].lazadd=0;
    if(l==r)return;
    ll mid=(l+r)>>1;
    build(LS(p),l,mid);
    build(RS(p),mid+1,r);
}

void pushdown(ll p)
{
    T[LS(p)].mxn+=T[p].lazadd;
    T[RS(p)].mxn+=T[p].lazadd;
    T[LS(p)].lazadd+=T[p].lazadd;
    T[RS(p)].lazadd+=T[p].lazadd;
    T[p].lazadd=0;
}

void FIX(ll p,ll l,ll r,ll x)
{
    if(r<T[p].l||T[p].r<l)return ;
    if(r>=T[p].r&&T[p].l>=l)
    {
        T[p].mxn+=x;
        T[p].lazadd+=x;
        return ;
    }
    pushdown(p);
    FIX(LS(p),l,r,x);
    FIX(RS(p),l,r,x);
    UPDATE_max(p); 
}

int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        memset(a,0,sizeof(a));
        memset(T,0,sizeof(T));
        memset(star,0,sizeof(star));
        memset(p,0,sizeof(p));
        scanf("%lld %lld %lld",&n,&w,&h);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].w);
        }
        for(int i=1;i<=n;i++)
        {
            p[i<<1]=a[i].y+h-1;
            p[(i<<1)-1]=a[i].y;
            star[(i<<1)-1].l=star[(i<<1)].l=a[i].y;
            star[(i<<1)-1].r=star[(i<<1)].r=a[i].y+h-1;
            star[(i<<1)-1].len=a[i].x;star[(i<<1)-1].val=a[i].w; 
            star[i<<1].len=a[i].x+w-1;star[i<<1].val=-a[i].w;
        }
        n=n<<1; 
        sort(p+1,p+1+n);
        sort(star+1,star+1+n);
        /*for(int i=1;i<=n;i++)
        {
            printf("%lld %lld\n",star[i].l,star[i].r);
        }
        for(int i=1;i<=n;i++)
        {
            printf("%lld ",p[i]); 
        }*/
        ll num=unique(p+1,p+1+n)-p-1;
        //printf("%lld\n",num);
        for(int i=1;i<=n;i++)
        { 
            star[i].st=lower_bound(p+1,p+1+num,star[i].l)-p-1;
            star[i].ed=lower_bound(p+1,p+1+num,star[i].r)-p-1;
        }
        build(1,1,num-1);
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            //printf("%lld %lld\n",star[i].st,star[i].ed);
            FIX(1,star[i].st,star[i].ed,star[i].val);
            ans=mx(ans,T[1].mxn);
        }
        printf("%lld\n",ans);
    }
    return 0;
} 

80分 请求帮助qwq,调了一个下午了

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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