WA#9 求助大佬
查看原帖
WA#9 求助大佬
326663
included楼主2023/3/29 15:41

求助各位dalao帮忙看下,本人的代码在第9个点WA

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=10005;
int n,W,H,nx;
ll x[maxn],y[maxn],l[maxn],lsx[maxn*2];
ll val[maxn*8],addv[maxn*8];
struct Event{
    ll y,xl,xr,v;
    Event(ll y=0,ll l=0,ll r=0,ll v=0):y(y),xl(l),xr(r),v(v){}
    bool operator<(const Event&r)const
        {return y<r.y;}
};vector<Event>e;

void maintain(int o,int L,int R){
    if(L==R)val[o]=0;
    else val[o]=max(val[o<<1],val[o<<1|1]);
    val[o]+=addv[o];
}
void update(int o,int L,int R,int ql,int qr,ll v){
    if(ql<=L&&R<=qr)addv[o]+=v;
    else{
        int M=(L+R)>>1;
        if(ql<=M)update(o<<1,L,M,ql,qr,v);
        if(M<qr)update(o<<1|1,M+1,R,ql,qr,v);
    }maintain(o,L,R);
}

int main(){int _o;
    for(cin>>_o;_o--;){

    cin>>n>>W>>H;
    nx=0;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i]>>l[i];
        lsx[++nx]=x[i];
        lsx[++nx]=x[i]+W-1;
    }
    sort(lsx+1,lsx+nx+1);
    nx=unique(lsx+1,lsx+nx+1)-lsx-1;
    e.clear();
    for(int i=1;i<=n;i++){
        int xl=lower_bound(lsx+1,lsx+nx+1,x[i])-lsx;
        int xr=lower_bound(lsx+1,lsx+nx+1,x[i]+W-1)-lsx;
        e.push_back(Event(y[i],xl,xr,l[i]));
        e.push_back(Event(y[i]+H-1,xl,xr,-l[i]));
    }
    sort(e.begin(),e.end());
    memset(val,0,sizeof(val));
    memset(addv,0,sizeof(addv));
    ll ans=0;
    for(int i=0;i<e.size();i++){
        ans=max(ans,val[1]);
        update(1,1,nx,e[i].xl,e[i].xr,e[i].v);
    }
    cout<<ans<<endl;

    }return 0;
}
···
2023/3/29 15:41
加载中...