萌新求助

回复帖子

@abcde777 2021-04-08 13:48 回复

第9个点WA了,萌新百思不得其解 QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define I inline
#define nnq nanachi
#define int long long
#define lson k<<1
#define rson k<<1|1
#define mid (l+r>>1)
using namespace std ;

const int N = 20010;
struct L {
    int type,xpos,val,st,ed;
}line[N<<1];
struct node {
    int tag,maxx;
}tr[N<<2];
int n,w,h,x1,y1,l1,tot,ans;
int Y[N<<1];

I bool cmp(L a1,L a2) {
    if(a1.xpos^a2.xpos) return a1.xpos<a2.xpos;
    return a1.type>a2.type;
}
I void update(int k) {
    tr[k].maxx=max(tr[lson].maxx,tr[rson].maxx);
}
I void pushdown(int k) {
    if(tr[k].tag) {
        tr[lson].tag+=tr[k].tag;
        tr[lson].maxx+=tr[k].tag;
        tr[rson].tag+=tr[k].tag;
        tr[rson].maxx+=tr[k].tag;
        tr[k].tag=0;
    }
}
void change(int l,int r,int nl,int nr,int k,int val) {
    if(Y[r+1]<=nl||Y[l]>=nr) return ;
    if(Y[r+1]<=nr&&Y[l]>=nl) {
        tr[k].tag+=val;
        tr[k].maxx+=val;
        return ;
    }
    pushdown(k);
    change(l,mid,nl,nr,lson,val);
    change(mid+1,r,nl,nr,rson,val);
    update(k);
}
I void clear() {
    tot=ans=0;
    memset(Y,0,sizeof(Y));
    memset(tr,0,sizeof(tr));
    memset(line,0,sizeof(line));
}
I int read() {
    int ret=0,w=1; char ch;
    while((ch=getchar())>'9'||ch<'0'&&ch!='-'); if(ch=='-') w=-1; else ret=ch-'0';
    while((ch=getchar())>='0'&&ch<='9') ret=ret*10+ch-'0';
    return ret*w;
}
#define mk1 (i<<1)
#define mk2 (i<<1)-1
signed main()
{
    int T; T=read();
    for(int nnq=1;nnq<=T;++nnq) {
        clear();
        n=read(); w=read()-1; h=read()-1;
        for(int i=1;i<=n;++i) {
            x1=read()+1000002; y1=read()+1000002; l1=read();
            Y[mk1]=y1; Y[mk2]=y1+h;
            line[mk1].type=1; line[mk1].st=y1; line[mk1].ed=y1+h; line[mk1].xpos=x1-w;
            line[mk2].type=-1; line[mk2].st=y1; line[mk2].ed=y1+h; line[mk2].xpos=x1;
            line[mk1].val=line[mk2].val=l1;
        }
        sort(line+1,line+1+(n<<1),cmp);
        sort(Y+1,Y+1+(n<<1));
        tot=unique(Y+1,Y+1+(n<<1))-Y-1;
        for(int i=1;i<=(n<<1);++i) {
            change(1,tot-1,line[i].st,line[i].ed,1,line[i].type*line[i].val);
            ans=max(ans,tr[1].maxx);
        }
        cout<<ans<<endl;
    }
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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