萌新求助,#9WA,#2#10RE
查看原帖
萌新求助,#9WA,#2#10RE
218752
smy2006楼主2022/8/31 21:39
#include<bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
inline ll read() {
	ll q=0;
	char ch=' ';
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch<='9' && ch>='0') q=q*10+ch-'0',ch=getchar();
	return q;
}
const int MAXN = 8e5+25;
ll T,n,W,H,X[MAXN],ans;
struct Star {
	ll x,y,l;
}
star[MAXN];
struct Line {
	ll l,r,y,w;
}
line[MAXN];
inline bool cmp(Line a,Line b) {
	return a.y<b.y;
}
struct Segment_Tree {
	ll maxn,tag;
}
tre[MAXN<<2];
inline void push_down(int l,int r,int p) {
	if(tre[p].tag==0) {
		return;
	}
	int mid=(l+r)>>1;
	tre[p*2].maxn+=tre[p].tag,tre[p*2+1].maxn+=tre[p].tag;
	tre[p*2].tag+=tre[p].tag,tre[p*2+1].tag+=tre[p].tag;
	tre[p].tag=0;
	return;
}
void change(int l,int r,int p,int a,int b,ll k) {
	if(a<=l && r<=b) {
		tre[p].maxn+=k,tre[p].tag+=k;
		return;
	}
	int mid=(l+r)>>1;
	push_down(l,r,p);
	if(a<=mid) change(l,mid,p*2,a,b,k);
	if(b>mid) change(mid+1,r,p*2+1,a,b,k);
	tre[p].maxn=max(tre[p*2].maxn,tre[p*2+1].maxn);
	return;
}
inline void solve() {
	n=read(),W=read(),H=read();
	memset(tre,0,sizeof(tre));
	ans=0;
	for (int i=1; i<=n; i++) {
		star[i].x=read(),star[i].y=read(),star[i].l=read();
	}
	for (int i=1; i<=n; i++) X[i]=star[i].x,X[i+n]=star[i].x+W-1;
	sort(X+1,X+2*n+1);
	int len=unique(X+1,X+2*n+1)-X-1;
	for (int i=1; i<=n; i++) {
		line[i].l=line[i+n].l=lower_bound(X+1,X+2*n+1,star[i].x)-X+1;
		line[i].r=line[i+n].r=lower_bound(X+1,X+2*n+1,star[i].x+W-1)-X+1;
		line[i].y=star[i].y;
		line[i+n].y=star[i].y+H-1;
		line[i].w=star[i].l;
		line[i+n].w=-star[i].l;
	}
	sort(line+1,line+2*n+1,cmp);
	//	for(int i=1; i<=2*n; i++){
	//		cout<<line[i].l<<" "<<line[i].r<<" "<<line[i].w<<" "<<line[i].y<<endl;
	//	}
	//    cout<<len<<endl;
	for (int i=1; i<=2*n; i++) {
		ans=max(ans,tre[1].maxn);
		change(1,len,1,line[i].l,line[i].r,line[i].w);
		//		cout<<tre[1].maxn<<endl;
	}
	cout<<ans<<endl;
}
signed main() {
	//	freopen("data.txt","r",stdin);
	//	freopen("my.txt","w",stdout);
	T=read();
	while(T--) {
		solve();
	}
	return 0;
}

扩大空间了n倍还是RE,真的破防了QAQ

2022/8/31 21:39
加载中...