求助40ptsWA
查看原帖
求助40ptsWA
768195
ty_mxzhn楼主2023/6/30 15:50
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define int long long
using namespace std;

struct Star{
	int x,y,l;
}a[100007];
struct Tseg{
	int data,tag;
}tr[200007<<2];
struct Oper{
	int x1,x2,y,typ;
}b[200007];
int t,n,W,H,ans,c[200007];
map<int,int> mp;
void dtag(int k,int lcnt,int ucnt){
	tr[k<<1].tag+=tr[k].tag;
	tr[k<<1|1].tag+=tr[k].tag;
	tr[k<<1].data+=tr[k].tag;
	tr[k<<1|1].data+=tr[k].tag;
	tr[k].tag=0;
}
void upd(int k,int a,int b,int x,int lb=1,int ub=2*n){//k->lt
	//tr[k].lb=tr[lt].lb,tr[k].data=tr[lt].data,tr[k].ls=tr[lt].ls,tr[k].lz=tr[lt].lz,tr[k].ub=tr[lt].ub,tr[k].us=tr[lt].us;
	if(a<=lb&&ub<=b){
		tr[k].tag=tr[k].tag+x;
		tr[k].data=tr[k].data+x;
		return;
	}
	int mid=lb+ub>>1;
	dtag(k,mid-lb+1,ub-mid);
	if(a<=mid) upd(k<<1,a,b,x,lb,mid);
	if(b>mid) upd(k<<1|1,a,b,x,mid+1,ub);
	tr[k].data=max(tr[k<<1].data,tr[k<<1|1].data);
}
int query(int k,int a,int b,int lb=1,int ub=2*n){
	if(a<=lb&&ub<=b){
		return tr[k].data;
	}
	int mid=lb+ub>>1,ans=0;
	dtag(k,mid-lb+1,ub-mid);
	if(a<=mid) ans=max(ans,query(k<<1,a,b,lb,mid));
	if(b>mid) ans=max(ans,query(k<<1|1,a,b,mid+1,ub));
	return ans;
}
bool Ysort(Oper a,Oper b){ if(a.y!=b.y) return a.y<b.y; return a.typ>b.typ; }
signed main(){
	scanf("%lld",&t);
	while(t--){
		mp.clear();ans=0;
		memset(b,0,sizeof b);
		memset(c,0,sizeof c);
		scanf("%lld%lld%lld",&n,&W,&H);
		for(int i=1;i<=4*n;i++) tr[i].data=tr[i].tag=0;
		for(int i=1;i<=n;i++){
			scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].l);
			b[i].x1=b[n+i].x1=c[i]=a[i].x; b[i].x2=b[n+i].x2=c[n+i]=a[i].x+W-1;
			b[i].y=a[i].y; b[n+i].y=a[i].y+H-1;
			b[i].typ=a[i].l; b[n+i].typ=-a[i].l;
		}
		//printf("I");
		sort(c+1,c+2*n+1);
		c[0]=-1;
		for(int i=1;i<=2*n;i++) mp[c[i]]=mp[c[i-1]]+(c[i-1]<c[i]);
		sort(b+1,b+2*n+1,Ysort);
		for(int i=1;i<=2*n;i++){
			upd(1,mp[b[i].x1],mp[b[i].x2],b[i].typ);ans=max(ans,tr[1].data);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

有大佬能帮忙看一下吗

2023/6/30 15:50
加载中...