知道这是扫描线,但是看了题目的
小卡买的窗户框是金属做的,所以在边框上的不算在内。
描述感到疑惑,就先没管,交了一发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);
}
}