萌新20分WA求助,求路过大佬帮个忙

回复帖子

@Spartan117  2020-07-06 21:20 回复
#include<bits/stdc++.h>
#define ll long long
#define lz(x) tr[x].lz
#define mx(x) tr[x].MAX
#define l(x) tr[x].l
#define r(x) tr[x].r
using namespace std;
const ll N=1e4+5,INF=1e18;
struct nd{
    ll l,r;
    ll MAX;
    ll lz; 
}tr[N*32];
inline void spread(ll x){
    if(lz(x)){
        mx(x*2)+=lz(x);
        mx(x*2+1)+=lz(x);
        lz(x*2)+=lz(x);
        lz(x*2)+=lz(x);
        lz(x)=0;
    }
}
inline void pushup(ll x){
    mx(x)=max(mx(x*2),mx(x*2+1));
}
void build(ll rt,ll l,ll r){
    tr[rt].l=l;tr[rt].r=r;
    tr[rt].MAX=0;tr[rt].lz=0;
    if(l==r) return; 
    ll mid=l+r>>1;
    build(rt*2,l,mid);build(rt*2+1,mid+1,r);
}
void upd(ll rt,ll L,ll R,ll add){
    //cout<<L<<' '<<R<<endl;
    if(L<=l(rt)&&R>=r(rt)){
        mx(rt)+=add;
        lz(rt)+=add;
        return;
    }
    spread(rt);
    ll mid=(l(rt)+r(rt))>>1;
    if(L<=mid) upd(rt*2,L,R,add);
    if(R>mid) upd(rt*2+1,L,R,add);
    pushup(rt);
}
ll ask(ll rt,ll L,ll R){
    if(L<=l(rt)&&R>=r(rt)) return mx(rt);
    spread(rt);
    ll mid=l(rt)+r(rt)>>1;
    ll ret=0;
    if(L<=mid) ret=max(ret,ask(rt*2,L,R));
    if(R>mid) ret=max(ret,ask(rt*2+1,L,R));
    return ret;
}

ll T;
ll n;
ll W,H;
ll ans=0;
struct star{
    ll x,yl,yr,l;
}a[N*2];
bool cmp(const star &a,const star &b){
    return a.x<b.x||a.x==b.x&&a.l<b.l;
}
ll lsh[N*2];
int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        scanf("%lld%lld",&W,&H);
        for(ll i=1,x,y,l;i<=n;i++){
            scanf("%lld%lld%lld",&x,&y,&l);
            a[i].x=x;a[i].yl=y;a[i].yr=y+H-1;a[i].l=l;
            lsh[i]=y;lsh[i+n]=y+H-1;
        }
        sort(lsh+1,lsh+n*2+1);ll nl=unique(lsh+1,lsh+n*2+1)-lsh-1;
        for(ll i=1;i<=n;i++){
            a[i].yl=lower_bound(lsh+1,lsh+nl+1,a[i].yl)-lsh;//离散化 
            a[i].yr=lower_bound(lsh+1,lsh+nl+1,a[i].yr)-lsh;
            a[i+n]=(star){a[i].x+W,a[i].yl,a[i].yr,-a[i].l};
        }
        sort(a+1,a+n*2+1,cmp);
        build(1,1,nl);
        //cout<<"nl: "<<<<endl;
        for(ll i=1;i<=n*2;i++){
            star c=a[i];
            upd(1,c.yl,c.yr,c.l);//更新 
            /*cout<<"sg: "<<' ';
            for(ll j=1;j<=7;j++) 
                cout<<ask(1,j,j)<<' ';
            cout<<endl;*/
            ans=max(ans,mx(1));
        }
        printf("%lld\n",ans);
        ans=0;
    }
    return 0;
}

rt

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



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