wa了#9,跪求大佬帮忙看看

回复帖子

@frank15 2021-02-01 10:40 回复
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int maxn=2e6+5;
int t,n,w,h,xa,ya,xb,yb,L,pos1,pos2,tot,ans;
struct line_y{
    int x,l,r,flag;
}y[maxn];
int discre[maxn],val[maxn];
bool cmp(line_y X,line_y Y){
    return X.x<Y.x||(X.x==Y.x&&X.flag>Y.flag);
}
struct t{
    int MAX,lazy;
}tree[4*maxn];
void change(int node,int k){
    tree[node].lazy+=k;
    tree[node].MAX+=k;
}
void push_down(int node){
    if(tree[node].lazy){
        int left_node=node<<1;
        int right_node=node<<1|1;
        change(left_node,tree[node].lazy);
        change(right_node,tree[node].lazy);
        tree[node].lazy=0;
    }
}
void update(int node,int l,int r,int aim_L,int aim_R,int k){
    if(l>=aim_R||r<=aim_L)
        return ;
//  cout<<l<<' '<<r<<' '=<<aim_L<<' '<<aim_R<<endl;
    if(aim_L<=l&&r<=aim_R){
        tree[node].lazy+=k;
        tree[node].MAX+=k;
        return ;
    }
    push_down(node);
    int mid=(l+r)>>1;
    int left_node=node<<1;
    int right_node=node<<1|1;
    update(left_node,l,mid,aim_L,aim_R,k);
    update(right_node,mid,r,aim_L,aim_R,k);
    tree[node].MAX=max(tree[left_node].MAX,tree[right_node].MAX);
}
signed main(){
    scanf("%lld",&t);
    while(t--){
//      fill(tree+1,tree+maxn+1,0);
        ans=0;
        scanf("%lld%lld%lld",&n,&w,&h);
        memset(tree,sizeof(tree),0);
        for(int i=1;i<=n;i++){
            scanf("%lld%lld%lld",&xa,&ya,&L);
            xb=xa+w-1;
            yb=ya+h-1;
            y[(i<<1)-1].flag=L;
            y[(i<<1)-1].l=yb;
            y[(i<<1)-1].r=ya;
            y[(i<<1)-1].x=xa;
            y[i<<1].flag=-L;
            y[i<<1].l=yb;
            y[i<<1].r=ya;
            y[i<<1].x=xb;
            discre[(i<<1)-1]=ya;
            discre[i<<1]=yb;
        }
        sort(discre+1,discre+(n<<1)+1);
        tot=unique(discre+1,discre+(n<<1)+1)-discre-1;
//      cout<<tot<<endl;
//      for(int i=1;i<= tot;i++)
//          cout<<discre[i]<<' ';
//      cout<<endl;
        for(int i=1;i<=2*n;i++){
            y[i].l=lower_bound(discre+1,discre+tot+1,y[i].l)-discre;
            y[i].r=lower_bound(discre+1,discre+tot+1,y[i].r)-discre;
        }
        sort(y+1,y+(n<<1)+1,cmp);
        for(int i=1;i<=(n<<1);i++){
//          cout<<y[i].x<<' '<<y[i].flag<<endl;
            update(1,1,tot,y[i].r,y[i].l,y[i].flag);
//          cout<<ans<<endl;
            ans=max(ans,tree[1].MAX);
//          cout<<tre<<endl;
//          for(int i=1;i<=8;i++)
//              cout<<tree[i].MAX<<' '<<tree[i].lazy<<endl;
        }
        printf("%lld\n",ans);
    }
}
@sprads 2021-02-02 12:58 回复 举报
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int maxn=2e6+5;
int t,n,w,h,xa,ya,xb,yb,L,pos1,pos2,tot,ans;
struct line_y{
    int x,l,r,flag;
}y[maxn];
int discre[maxn],val[maxn];
bool cmp(line_y X,line_y Y){
    return X.x<Y.x||(X.x==Y.x&&X.flag>Y.flag);
}
struct t{
    int MAX,lazy;
}tree[4*maxn];
void change(int node,int k){
    tree[node].lazy+=k;
    tree[node].MAX+=k;
}
void push_down(int node){
    if(tree[node].lazy){
        int left_node=node<<1;
        int right_node=node<<1|1;
        change(left_node,tree[node].lazy);
        change(right_node,tree[node].lazy);
        tree[node].lazy=0;
    }
}
void update(int node,int l,int r,int aim_L,int aim_R,int k){
    if(l>aim_R||r<aim_L)//here
        return ;
//  cout<<l<<' '<<r<<' '=<<aim_L<<' '<<aim_R<<endl;
    if(aim_L<=l&&r<=aim_R){
        tree[node].lazy+=k;
        tree[node].MAX+=k;
        return ;
    }
    push_down(node);
    int mid=(l+r)>>1;
    int left_node=node<<1;
    int right_node=node<<1|1;
    update(left_node,l,mid,aim_L,aim_R,k);
    update(right_node,mid+1,r,aim_L,aim_R,k);//here
    tree[node].MAX=max(tree[left_node].MAX,tree[right_node].MAX);
}
signed main(){
    scanf("%lld",&t);
    while(t--){
//      fill(tree+1,tree+maxn+1,0);
        ans=0;
        scanf("%lld%lld%lld",&n,&w,&h);
        memset(tree,sizeof(tree),0);
        for(int i=1;i<=n;i++){
            scanf("%lld%lld%lld",&xa,&ya,&L);
            xb=xa+w-1;
            yb=ya+h-1;
            y[(i<<1)-1].flag=L;
            y[(i<<1)-1].l=yb;
            y[(i<<1)-1].r=ya;
            y[(i<<1)-1].x=xa;
            y[i<<1].flag=-L;
            y[i<<1].l=yb;
            y[i<<1].r=ya;
            y[i<<1].x=xb;
            discre[(i<<1)-1]=ya;
            discre[i<<1]=yb;
        }
        sort(discre+1,discre+(n<<1)+1);
        tot=unique(discre+1,discre+(n<<1)+1)-discre-1;
//      cout<<tot<<endl;
//      for(int i=1;i<= tot;i++)
//          cout<<discre[i]<<' ';
//      cout<<endl;
        for(int i=1;i<=2*n;i++){
            y[i].l=lower_bound(discre+1,discre+tot+1,y[i].l)-discre;
            y[i].r=lower_bound(discre+1,discre+tot+1,y[i].r)-discre;
        }
        sort(y+1,y+(n<<1)+1,cmp);
        for(int i=1;i<=(n<<1);i++){
//          cout<<y[i].x<<' '<<y[i].flag<<endl;
            update(1,1,tot,y[i].r,y[i].l,y[i].flag);
//          cout<<ans<<endl;
            ans=max(ans,tree[1].MAX);
//          cout<<tre<<endl;
//          for(int i=1;i<=8;i++)
//              cout<<tree[i].MAX<<' '<<tree[i].lazy<<endl;
        }
        printf("%lld\n",ans);
    }
    return 0; 
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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