边界改成x+w-1和y+h-1反而wa了
查看原帖
边界改成x+w-1和y+h-1反而wa了
523864
paradoxxd楼主2021/11/24 19:32

知道这是扫描线,但是看了题目的

小卡买的窗户框是金属做的,所以在边框上的不算在内。

描述感到疑惑,就先没管,交了一发ac了,然后我看题解发现大佬们都是处理成边界-1,我以为是数据弱了,改了下代码交了一发,结果wa了...
这是为啥

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e4+100;
struct node{
	int x;
	int yu,yd;
	int val;
	int flag;
};
vector<node>ys;
vector<int>xs;
bool cmp(node a,node b){
	return a.x<b.x;
}
struct{
	int l,r;
	long long val;
	long long state;
}st[maxn*8];
void build(int l,int r,int rt){
	st[rt].l=xs[l-1];
	st[rt].r=xs[r-1];
	if(l+1==r) return;
	int m=l+r>>1;
	build(l,m,rt*2);
	build(m,r,rt*2+1);
}
inline void pushup(int rt){
	st[rt].val=max(st[rt*2].val,st[rt*2+1].val)+st[rt].state;
}
void update(int rt,int s,int e,int c,int flag){
	int l=st[rt].l;
	int r=st[rt].r;
	if(s<=l&&r<=e){
		st[rt].state+=flag*c;
		pushup(rt);
		return;
	}
	int m=st[rt*2].r;
	if(s<m)update(rt*2,s,e,c,flag);
	if(m<e)update(rt*2+1,s,e,c,flag);
	pushup(rt);
}
int main(){
	int t;
	scanf("%d",&t);
	int n,w,h;
	int x,y,l;
	while(t--){
		memset(st,0,sizeof(st));
		ys.clear();
		xs.clear();
		scanf("%d%d%d",&n,&w,&h);
		for(int i=0;i<n;i++){
			scanf("%d%d%d",&x,&y,&l);
			ys.push_back({x,y+h-1,y,l,1});
			ys.push_back({x+w-1,y+h-1,y,l,-1});
			xs.push_back(y);
			xs.push_back(y+h-1);
		}
		sort(xs.begin(),xs.end());
		sort(ys.begin(),ys.end(),cmp);
		xs.erase(unique(xs.begin(),xs.end()),xs.end());
		build(1,xs.size(),1);
		int last=-1;
		long long ans=0;
		for(auto it:ys){
			if(it.x!=last) ans=max(ans,st[1].val);
			update(1,it.yd,it.yu,it.val,it.flag);
			last=it.x;
		}
		ans=max(ans,st[1].val);
		printf("%lld\n",ans);
	}
}
2021/11/24 19:32
加载中...