萌新求助
查看原帖
萌新求助
341034
abcde777楼主2021/4/8 13:48

第9个点WA了,萌新百思不得其解 QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define I inline
#define nnq nanachi
#define int long long
#define lson k<<1
#define rson k<<1|1
#define mid (l+r>>1)
using namespace std ;

const int N = 20010;
struct L {
	int type,xpos,val,st,ed;
}line[N<<1];
struct node {
	int tag,maxx;
}tr[N<<2];
int n,w,h,x1,y1,l1,tot,ans;
int Y[N<<1];

I bool cmp(L a1,L a2) {
	if(a1.xpos^a2.xpos) return a1.xpos<a2.xpos;
	return a1.type>a2.type;
}
I void update(int k) {
	tr[k].maxx=max(tr[lson].maxx,tr[rson].maxx);
}
I void pushdown(int k) {
	if(tr[k].tag) {
		tr[lson].tag+=tr[k].tag;
		tr[lson].maxx+=tr[k].tag;
		tr[rson].tag+=tr[k].tag;
		tr[rson].maxx+=tr[k].tag;
		tr[k].tag=0;
	}
}
void change(int l,int r,int nl,int nr,int k,int val) {
	if(Y[r+1]<=nl||Y[l]>=nr) return ;
	if(Y[r+1]<=nr&&Y[l]>=nl) {
		tr[k].tag+=val;
		tr[k].maxx+=val;
		return ;
	}
	pushdown(k);
	change(l,mid,nl,nr,lson,val);
	change(mid+1,r,nl,nr,rson,val);
	update(k);
}
I void clear() {
	tot=ans=0;
	memset(Y,0,sizeof(Y));
	memset(tr,0,sizeof(tr));
	memset(line,0,sizeof(line));
}
I int read() {
	int ret=0,w=1; char ch;
	while((ch=getchar())>'9'||ch<'0'&&ch!='-'); if(ch=='-') w=-1; else ret=ch-'0';
	while((ch=getchar())>='0'&&ch<='9') ret=ret*10+ch-'0';
	return ret*w;
}
#define mk1 (i<<1)
#define mk2 (i<<1)-1
signed main()
{
	int T; T=read();
	for(int nnq=1;nnq<=T;++nnq) {
		clear();
		n=read(); w=read()-1; h=read()-1;
		for(int i=1;i<=n;++i) {
			x1=read()+1000002; y1=read()+1000002; l1=read();
			Y[mk1]=y1; Y[mk2]=y1+h;
			line[mk1].type=1; line[mk1].st=y1; line[mk1].ed=y1+h; line[mk1].xpos=x1-w;
			line[mk2].type=-1; line[mk2].st=y1; line[mk2].ed=y1+h; line[mk2].xpos=x1;
			line[mk1].val=line[mk2].val=l1;
		}
		sort(line+1,line+1+(n<<1),cmp);
		sort(Y+1,Y+1+(n<<1));
		tot=unique(Y+1,Y+1+(n<<1))-Y-1;
		for(int i=1;i<=(n<<1);++i) {
			change(1,tot-1,line[i].st,line[i].ed,1,line[i].type*line[i].val);
			ans=max(ans,tr[1].maxx);
		}
		cout<<ans<<endl;
	}
}
2021/4/8 13:48
加载中...