我使用的就是正解的扫描线算法,但是交了好几遍都是10pts,其中有一次ac的那个点还和之前不一样,有没有dalao给我看看?
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
#define ls (now<<1)
#define rs ((now<<1)|1)
#define mid ((l+r)>>1)
#define y1 wzqh_loves_zsq
#define y2 and_aks_ioi
#define int long long
int t,n,w,h,x[N],y[N],l[N],ans;
int rawx[N<<1],rawy[N<<1];
struct edge{
int x,y1,y2,f;
bool operator<(edge e){
return x<e.x;
}
} ed[N<<1];
int valx(int x){return lower_bound(rawx+1,rawx+(n<<1)+1,x)-rawx;}
int valy(int y){return lower_bound(rawy+1,rawy+(n<<1)+1,y)-rawy;}
void read_lisan(){
cin>>n>>w>>h;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i]>>l[i];
rawx[(i<<1)-1]=x[i],rawx[i<<1]=x[i]+w;
rawy[(i<<1)-1]=y[i],rawy[i<<1]=y[i]+h;
}
sort(rawx+1,rawx+(n<<1)+1);
sort(rawy+1,rawy+(n<<1)+1);
}
void sort_edge(){
for(int i=1;i<=n;i++){
ed[(i<<1)-1]={valx(x[i]),valy(y[i]),valy(y[i]+h),l[i]};
ed[i<<1]={valx(x[i]+w),valy(y[i]),valy(y[i]+h),-l[i]};
}
sort(ed+1,ed+(n<<1)+1);
}
int tr[N<<4],lazy[N<<4];
void pu(int now){
tr[now]=max(tr[ls],tr[rs]);
}
void pd(int now){
tr[ls]+=lazy[now],tr[rs]+=lazy[now];
lazy[rs]+=lazy[now],lazy[rs]+=lazy[now];
lazy[now]=0;
}
void modify(int now,int l,int r,int L,int R,int d){
if(L<=l&&r<=R){
tr[now]+=d;
lazy[now]+=d;
return;
}
if(lazy[now]) pd(now);
if(L<=mid) modify(ls,l,mid,L,R,d);
if(mid+1<=R) modify(rs,mid+1,r,L,R,d);
pu(now);
}
int query_root(){
if(lazy[1]) pd(1);
return tr[1];
}
void clear(){
n=w=h=ans=0;
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
memset(l,0,sizeof(l));
memset(rawx,0,sizeof(rawx));
memset(rawy,0,sizeof(rawy));
memset(ed,0,sizeof(ed));
memset(tr,0,sizeof(tr));
memset(lazy,0,sizeof(lazy));
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin>>t;
while(t--){
clear();
read_lisan();
sort_edge();
for(int i=1;i<(n<<1);i++){
modify(1,1,n<<1,ed[i].y1+1,ed[i].y2-1,ed[i].f);
ans=max(ans,query_root());
}
cout<<ans<<"\n";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
#define ls (now<<1)
#define rs ((now<<1)|1)
#define mid ((l+r)>>1)
#define y1 wzqh_loves_zsq
#define y2 and_aks_ioi
#define int long long
int t,n,w,h,x[N],y[N],l[N],ans;
int rawx[N<<1],rawy[N<<1];
struct edge{
int x,y1,y2,f;
bool operator<(edge e){
return x<e.x;
}
} ed[N<<1];
int valx(int x){return lower_bound(rawx+1,rawx+(n<<1)+1,x)-rawx;}
int valy(int y){return lower_bound(rawy+1,rawy+(n<<1)+1,y)-rawy;}
void read_lisan(){
cin>>n>>w>>h;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i]>>l[i];
rawx[(i<<1)-1]=x[i],rawx[i<<1]=x[i]+w;
rawy[(i<<1)-1]=y[i],rawy[i<<1]=y[i]+h;
}
sort(rawx+1,rawx+(n<<1)+1);
sort(rawy+1,rawy+(n<<1)+1);
}
void sort_edge(){
for(int i=1;i<=n;i++){
ed[(i<<1)-1]={valx(x[i]),valy(y[i]),valy(y[i]+h-1),l[i]};
ed[i<<1]={valx(x[i]+w-1),valy(y[i]),valy(y[i]+h-1),-l[i]};
}
sort(ed+1,ed+(n<<1)+1);
}
int tr[N<<4],lazy[N<<4];
void pu(int now){
tr[now]=max(tr[ls],tr[rs]);
}
void pd(int now){
tr[ls]+=lazy[now],tr[rs]+=lazy[now];
lazy[rs]+=lazy[now],lazy[rs]+=lazy[now];
lazy[now]=0;
}
void modify(int now,int l,int r,int L,int R,int d){
if(L<=l&&r<=R){
tr[now]+=d;
lazy[now]+=d;
return;
}
if(lazy[now]) pd(now);
if(L<=mid) modify(ls,l,mid,L,R,d);
if(mid+1<=R) modify(rs,mid+1,r,L,R,d);
pu(now);
}
int query_root(){
if(lazy[1]) pd(1);
return tr[1];
}
void clear(){
n=w=h=ans=0;
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
memset(l,0,sizeof(l));
memset(rawx,0,sizeof(rawx));
memset(rawy,0,sizeof(rawy));
memset(ed,0,sizeof(ed));
memset(tr,0,sizeof(tr));
memset(lazy,0,sizeof(lazy));
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin>>t;
while(t--){
clear();
read_lisan();
sort_edge();
for(int i=1;i<(n<<1);i++){
modify(1,1,n<<1,ed[i].y1,ed[i].y2,ed[i].f);
ans=max(ans,query_root());
}
cout<<ans<<"\n";
}
return 0;
}