本人OI萌新,开了2倍边,8倍树,还是RE,烦请诸位大佬帮看看
查看原帖
本人OI萌新,开了2倍边,8倍树,还是RE,烦请诸位大佬帮看看
363495
我爱杨帆楼主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;
	}
}
2020/10/23 17:35
加载中...