啊,救命命,只有40分
查看原帖
啊,救命命,只有40分
934569
Adam_Eden楼主2023/1/27 18:59
#include<bits/stdc++.h>
using namespace std;

#define FOR(i,start,end) for(int i=start;i<=end;i++)
#define ROF(i,start,end) for(int i=start;i>=end;i--)
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define mm0(x) memset(x,0,sizeof(x))
#define mm_1(x) memset(x,-1,sizeof(x))
#define mm3f(x) memset(x,0x3f,sizeof(x))
#define db1(a) cout<<#a<<"="<<a<<endl
#define db2(a,i) cout<<#a<<"["<<i<<"]="<<a[i]<<endl
#define db3(a,i,j) cout<<#a<<"["<<i<<"]["<<j<<"]="<<a[i][j]<<endl
typedef long long ll;
typedef pair<int,int> pii;

// begin code
int T,n,W,H;
const int N=1e5+5;
struct node{
	int tag;
	int val;
}tr[N<<5];
void pushdown(int u){
	if(tr[u].tag!=0){
		tr[u<<1].tag+=tr[u].tag;
		tr[u<<1|1].tag+=tr[u].tag;
		tr[u<<1].val+=tr[u].tag;
		tr[u<<1|1].val+=tr[u].tag;
		tr[u].tag=0;
	}
}
void pushup(int u){
	tr[u].val=max(tr[u<<1].val,tr[u<<1|1].val);
//	cout<<"修改"<<u<<"号节点的值为"<<tr[u].val<<endl; 
}
void build(int u,int l,int r){
	if(l==r){
		tr[u].tag=0;
		tr[u].val=0;
		return;
	}
	int m=l+(r-l)/2;
	build(u<<1,l,m);
	build(u<<1|1,m+1,r);
	pushup(u);
}
void update(int u,int l,int r,int st,int en,int k){
	if(st>r||en<l)return;
	if(st<=l&&r<=en){
		tr[u].val+=k;
		tr[u].tag+=k;
//		cout<<"修改"<<u<<"号节点的值为"<<tr[u].val<<endl; 
		return;
	}
	if(l!=r)pushdown(u);
	int m=l+(r-l)/2;
	if(st<=m)update(u<<1,l,m,st,en,k);
	if(en>m)update(u<<1|1,m+1,r,st,en,k);
	pushup(u);
}
struct _star{
	int x,y,light;
	bool operator<(const _star& t) const{
		if(x==t.x)return light<t.light;
		else return x<t.x;
	}
} star[N];
// end code

//#define DEBUG
int main() {
	//提高cin,cout的速度
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#ifdef DEBUG
	freopen("P1502.in","r",stdin);
//	freopen("P1502.ans","w",stdout);
#endif

// begin main code
	cin>>T;
	while(T--){
		cin>>n>>W>>H;
		int x,y,light;
		int maxy=0;
		FOR(i,1,n){
			cin>>x>>y>>light;
			maxy=max(maxy,y);
			star[2*i-1].x=x;
			star[2*i-1].y=y;
			star[2*i-1].light=light;
			star[2*i].x=x+W;
			star[2*i].y=y;
			star[2*i].light=-light;
		}
		sort(star+1,star+n*2+1);
		star[2*n+1].x=-1;
//		db1(maxy+H);
		build(1,1,maxy+H);
		int ans=0;
		FOR(i,1,2*n){
//			cout<<star[i].y<<"到"<<star[i].y+H-1<<"加上"<<star[i].light<<endl;
			update(1,1,maxy+H,star[i].y,star[i].y+H-1,star[i].light);
			if(star[i].x!=star[i+1].x){
				ans=max(ans,tr[1].val);
			}
		}
		cout<<ans<<endl;
	}
// end code

#ifdef DEBUG
	fclose(stdin);
//	fclose(stdout);
#endif
	return 0;
}

各位大佬可以帮忙看看嘛,为什么只有40分,呜呜呜

2023/1/27 18:59
加载中...