感觉很对的30pts代码
查看原帖
感觉很对的30pts代码
1379399
reductt楼主2024/7/23 21:18

rt,提交记录,代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=1e4+10,INF=(1ll<<31)-1;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
    while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
namespace Seg{
struct Node{int l,r,maxv,tag;}tr[N<<3];
void pushup(Node &t,Node &t1,Node &t2){
    t.maxv=max(t1.maxv,t2.maxv);
}
void pushdown(Node &t,Node &t1,Node &t2){
    if(!t.tag)return;
    t1.tag+=t.tag,t2.tag+=t.tag;
    t1.maxv+=t.tag,t2.maxv+=t.tag;
    t.tag=0;
}
void build(int p,int l,int r){
    tr[p]={l,r,0,0};
    if(l==r)return;
    int mid=(l+r)>>1;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    pushup(tr[p],tr[2*p],tr[2*p+1]);
}
void add(int p,int l,int r,int k){
    if(l<=tr[p].l&&tr[p].r<=r){
        tr[p].tag+=k,tr[p].maxv+=k;
        return;
    }
    pushdown(tr[p],tr[2*p],tr[2*p+1]);
    int mid=(tr[p].l+tr[p].r)>>1;
    if(l<=mid)add(2*p,l,r,k);
    if(mid<r)add(2*p+1,l,r,k);
    pushup(tr[p],tr[2*p],tr[2*p+1]);
}
void add(int l,int r,int k){add(1,l,r,k);}
int query(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r)return tr[p].maxv;
    pushdown(tr[p],tr[2*p],tr[2*p+1]);
    int mid=(tr[p].l+tr[p].r)>>1,ans=-INF;
    if(l<=mid)ans=max(ans,query(2*p,l,r));
    if(mid<r)ans=max(ans,query(2*p+1,l,r));
    return ans;
}
int query(){return query(1,0,2*(N-1));}
}using namespace Seg;
struct Rect{int x,y,x2,y2,w;}a[N];
struct Ins{int x,y,y2,w;}ins[2*N];
int cmp_Ins(Ins i1,Ins i2){return i1.x<i2.x;}
int n,width,height,ls[2*N];
void solve(){
    memset(tr,0,sizeof(tr));
    memset(a,0,sizeof(a));
    memset(ls,0,sizeof(ls));
    memset(ins,0,sizeof(ins));
    n=read(),width=read(),height=read();
    FOR(i,1,n){
        int x=read(),y=read(),l=read();
        a[i]=(Rect){x,y,x+width-1,y+height-1,l};
        ls[++ls[0]]=y,ls[++ls[0]]=y-height+1;
    }
    sort(ls+1,ls+ls[0]+1);
    unique(ls+1,ls+ls[0]+1);
    FOR(i,1,n){
        a[i].y=lower_bound(ls+1,ls+ls[0]+1,a[i].y)-ls;
        a[i].y2=lower_bound(ls+1,ls+ls[0]+1,a[i].y2)-ls;
    }
    FOR(i,1,n){
        ins[i]=(Ins){a[i].x,a[i].y,a[i].y2,a[i].w};
        ins[i+n]=(Ins){a[i].x2,a[i].y,a[i].y2,-a[i].w};
    }
    sort(ins+1,ins+2*n+1,cmp_Ins);
    int ans=0;
    build(1,0,2*(N-1));
    FOR(i,1,2*n){
        add(1,ins[i].y,ins[i].y2,ins[i].w);
        ans=max(ans,query());
    }
    printf("%lld\n",ans);
}
signed main(){
    int T=read();while(T--)solve();
    return 0;
}

感觉很没问题,然而似了。

2024/7/23 21:18
加载中...