有没有大佬帮我调一下 球球各位了呜呜呜呜(悬关
查看原帖
有没有大佬帮我调一下 球球各位了呜呜呜呜(悬关
674793
luoguhandongheng楼主2023/9/2 12:13

rt WA 10pts

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+1; 
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
int mx[N<<3],tag[N<<3],n,w,h,yy[N<<1],t;
struct Scanline{
	int x,y1,y2,io;
}scanline[N<<1];
bool cmp(Scanline a,Scanline b){
	if(a.x==b.x)
		return a.io>b.io;
	return a.x<b.x; 
} 
void pushup(int p){
	mx[p]=max(mx[ls(p)],mx[rs(p)]); 
}
void pushdown(int p){
	if(tag[p]){
		mx[ls(p)]+=tag[p];
		mx[rs(p)]+=tag[p];
		tag[ls(p)]+=tag[p];
		tag[rs(p)]+=tag[p];
		tag[p]=0;
	}
} 
void update(int p,int pl,int pr,int l,int r,int io){
	if(pl<=l && pr>=r){
		 mx[p]+=io;
		 tag[p]+=io;
		 return; 
	}
	pushdown(p);
	int mid=(pl+pr)>>1;
	if(l<=mid)
		update(ls(p),pl,mid,l,r,io);
	if(r>mid)
		update(rs(p),mid+1,pr,l,r,io);
	pushup(p); 
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
    	memset(mx,0,sizeof(mx));
    	memset(tag,0,sizeof(tag));
    	cin>>n>>w>>h;
    	int cnt=0;
    	for(int i=1;i<=n;++i){
    		int x,y,l;
    		cin>>x>>y>>l;
    		scanline[++cnt]={x,y,y+h-1,l};
			yy[cnt]=y;
    		scanline[++cnt]={x+w-1,y,y+h-1,-l};
    		yy[cnt]=y+h-1;
		}
		sort(scanline+1,scanline+1+cnt,cmp);
		sort(yy+1,yy+1+cnt);
		int num=unique(yy+1,yy+1+cnt)-yy-1; 
		int ans=0;
		for(int i=1;i<=cnt;++i){
			int l=lower_bound(yy+1,yy+1+num,scanline[i].y1)-yy;
			int r=lower_bound(yy+1,yy+1+num,scanline[i].y2)-yy;
			update(1,0,num,l,r,scanline[i].io);
			ans=max(ans,mx[1]); 
		}
		cout<<ans<<endl;
	}
	return 0;
}

2023/9/2 12:13
加载中...