刚学扫描线90分求助

回复帖子

@exzang 2020-03-18 22:28 回复

如题

代码是抄袭神蛙的

#include<bits/stdc++.h>
using namespace std;
#define ls p<<1
#define rs p<<1|1
typedef long long ll;

const int N=2e5+5;
int L[N<<3],R[N<<3],f[N<<3],cnt,tot;
ll v[N<<3],Y[N<<1],cov[N<<3];
void build(int p,int l,int r){
    L[p]=l; R[p]=r; v[p]=0; cov[p]=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(ls,l,mid);

    build(rs,mid+1,r);

}
void pushup(int p){v[p]=max(v[ls],v[rs]);}
void pushdown(int p){
    if(cov[p]){
        cov[ls]+=cov[p]; cov[rs]+=cov[p];
        v[ls]+=cov[p]; v[rs]+=cov[p];
        cov[p]=0;
    }
}
void upt(int p,int l,int r,ll c){
    if(l<=L[p] && R[p]<=r){
        cov[p]+=c; v[p]+=c; return;
    }
    pushdown(p);
    int mid=(L[p]+R[p])>>1;
    if(l<=mid) upt(ls,l,r,c);
    if(mid+1<=r) upt(rs,l,r,c);
    pushup(p);
}
struct Border{

    ll x,y1,y2,f;
}a[N<<1];
bool cmp(Border i,Border j){

    return (i.x==j.x)?i.f>j.f:i.x<j.x;

}
int main(){
    ll x1,y1,x2,y2,W,H,l;
    int n,T;
    scanf("%d",&T);

    while(T--){
        scanf("%d%lld%lld",&n,&W,&H); cnt=0;
        for(int i=1;i<=n;++i){
            scanf("%lld%lld%lld",&x1,&y1,&l); x2=x1+W-1; y2=y1+H-1;
            a[++cnt].x=x1; a[cnt].y1=y1; a[cnt].y2=y2; a[cnt].f=l;
            Y[cnt]=y1;
            a[++cnt].x=x2; a[cnt].y1=y1; a[cnt].y2=y2; a[cnt].f=-l;
            Y[cnt]=y2;
        }
        sort(a+1,a+cnt+1,cmp);
        sort(Y+1,Y+cnt+1);
        tot=unique(Y+1,Y+cnt+1)-Y-1;
        build(1,1,tot);

        ll ans=0,l,r,last=0;
        for(int i=1;i<=cnt;++i){
            l=lower_bound(Y+1,Y+tot+1,a[i].y1)-Y;
            r=lower_bound(Y+1,Y+tot+1,a[i].y2)-Y-1;
            upt(1,l,r,a[i].f);
            ans=max(ans,v[1]);
        }
        printf("%lld\n",ans);       
    }

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



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