本人OI萌新,开了2倍边,8倍树,还是RE,烦请诸位大佬帮看看

回复帖子

@我爱杨帆 2020-10-23 17:35 回复
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define l(p) tree[p].l
#define r(p) tree[p].r
#define add(p) tree[p].add
#define dat(p) tree[p].dat
#define k(p)  tree[p].k
#define re register
inline int read()
{
    char c;
    int f=1,r=0;
    c=getchar();
    while(c!='-'&&(c<'0'||c>'9'))
    c=getchar();
    if(c=='-')
    {
    f=-1;
    c=getchar();
    }
    while(c>='0'&&c<='9')
    {
    r=r*10+c-'0';
    c=getchar();
    }
    return r*f;
}
const int sz=200005;
int a[sz],sum,c[sz],cnt;
struct node
{
    int l,r,dat,add;
}tree[sz*8];
struct node1
{
    int x,y1,y2,k;

}t[2*sz];
bool cmp1(node1 X,node1 Y)
{
    if(X.x!=Y.x)
    return X.x<Y.x;
    else 
    return X.k>Y.k;
}   
void build(int l,int r,int p)
{
 l(p)=l,r(p)=r;
 if(l==r)
 {
  dat(p)=0;
  return;   
 }
 int mid=(l+r)/2;
 build(l,mid,2*p);
 build(mid+1,r,2*p+1);
 dat(p)=max(dat(2*p),dat(2*p+1));   
}
void spread(int p)
{
 dat(2*p)+=add(p),dat(2*p+1)+=add(p);
 add(2*p)+=add(p),add(2*p+1)+=add(p);
 add(p)=0;  
}
void change_add(int l,int r,int d,int p)
{
 if(l<=l(p)&&r>=r(p))
 {
 dat(p)+=d,add(p)+=d;   
 return;
 }
 spread(p);
 int mid=(l(p)+r(p))/2;
 if(mid>=l) change_add(l,r,d,2*p);
 if(mid<r)  change_add(l,r,d,2*p+1);
 dat(p)=max(dat(2*p),dat(2*p+1));
}
int ask(int l,int r,int p)
{
 if(l<=l(p)&&r>=r(p))
 return dat(p);
 spread(p);
 int mid=(l(p)+r(p))/2,ans=0;
 if(mid>=l) ans=max(ans,ask(l,r,2*p));
 if(mid<r)  ans=max(ans,ask(l,r,2*p+1));
 return ans;    
}
signed main()
{
    int T=read();
    while(T--)
    {
     memset(t,0,sizeof(t));
     memset(c,0,sizeof(c));
     memset(tree,0,sizeof(tree));
     memset(a,0,sizeof(a)); 
     int n=read(),w=read(),h=read();    
     for(int i=1;i<=n;i++)
     {
     int x1=read(),y1=read(),l=read(),y2=y1+h-1,x2=x1+w-1;
     c[(i<<1)-1]=y1,c[i<<1]=y2;
     t[i<<1]=(node1){x1,y1,y2,l},t[(i<<1)-1]=(node1){x2,y1,y2,-l};                                     
     }   
     sort(c+1,c+1+2*n);
     sort(t+1,t+1+2*n,cmp1);     
     cnt=unique(c+1,c+1+2*n)-c-1;
     for(int i=1;i<=2*n;i++)
     {
     int pos1=lower_bound(c+1,c+1+2*n,t[i].y1)-c-1;
     int pos2=lower_bound(c+1,c+1+2*n,t[i].y2)-c-1;
     t[i].y1=pos1,t[i].y2=pos2; 
     }   
     build(1,cnt-1,1);
     int ans=0;
     for(int i=1;i<=2*n;i++)
     {
     change_add(t[i].y1,t[i].y2,t[i].k,1);
     ans=max(ans,ask(1,cnt-1,1));    
     }
     cout<<ans<<endl;
    }
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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