RE 10pts求调
查看原帖
RE 10pts求调
369428
xCLplr楼主2025/7/3 09:57
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define int long long
int t,n,w,h,cnt,height[401000],tot,heng[401000];
int tr[4001000],ans,lazy[4001000];
struct edge{
    int x,y1,y2,val;
}e[401000];
void add_edge(int x,int y1,int y2,int val) {
    cnt++;
    e[cnt].x=x;
    e[cnt].y1=y1;
    e[cnt].y2=y2;
    e[cnt].val=val;
}
bool cmp(edge a,edge b) {
    if(a.x!=b.x) return a.x<b.x;
    return a.val>b.val;
}
int lnode(int x) {
    return x*2;
}
int rnode(int x) {
    return x*2+1;
}
void pushdown(int x) {
    lazy[lnode(x)]+=lazy[x];
    lazy[rnode(x)]+=lazy[x];
    tr[lnode(x)]+=lazy[x];
    tr[rnode(x)]+=lazy[x];
    lazy[x]=0;
}
void pushup(int x) {
    tr[x]=max(tr[lnode(x)],tr[rnode(x)]);
}
void modify(int now,int nowl,int nowr,int targetl,int targetr,int val) {
    cout<<"in"<<endl;
    if(nowl>=targetl&&nowr<=targetr) {
        tr[now]+=val;
        lazy[now]+=val;
        return;
    }
    int mid=(nowl+nowr)/2;
    pushdown(now);
    if(targetl<=mid) modify(lnode(now),nowl,mid,targetl,targetr,val);
    if(targetr>mid) modify(rnode(now),mid+1,nowr,targetl,targetr,val);
    pushup(now);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--) {
        tot=0;
        cnt=0;
        memset(lazy,0,sizeof(lazy));
        memset(tr,0,sizeof(tr));
        memset(height,0,sizeof(height));
        memset(heng,0,sizeof(heng));
        memset(e,0,sizeof(e));
        ans=INT_MIN;
        cin>>n>>w>>h;
        for(int i=1,x,y,l;i<=n;i++ ){
            cin>>x>>y>>l;
            height[++tot]=y;
            heng[tot]=x;
            height[++tot]=y+h-1;
            add_edge(x,y,y+h-1,l);
            add_edge(x+w-1,y,y+h-1,-1*l);
        }
        sort(height+1,height+tot+1);
        int t=unique(height+1,height+tot+1)-height;
        sort(e+1,e+cnt+1,cmp);
        for(int i=1;i<=cnt;i++) {
            int pl1=lower_bound(height+1,height+t+1,e[i].y1)-height;
            int pl2=lower_bound(height+1,height+t+1,e[i].y2)-height;
            e[i].y1=pl1;
            e[i].y2=pl2;
        }
        for(int i=1;i<=cnt;i++) {
            cout<<"e["<<i<<"].y1="<<e[i].y1<<" e["<<i<<"].y2="<<e[i].y2<<endl;
        }
        for(int i=1;i<=cnt;i++) {
            modify(1,1,n,e[i].y1,e[i].y2,e[i].val);
            ans=max(ans,tr[1]);
        }
        cout<<ans<<'\n';
    }
    return 0;
}
2025/7/3 09:57
加载中...