Why WA 10pts?
查看原帖
Why WA 10pts?
1155762
TCIC_4294967296楼主2024/7/15 18:13

我使用的就是正解的扫描线算法,但是交了好几遍都是10pts,其中有一次ac的那个点还和之前不一样,有没有dalao给我看看?

AC第一个点的代码:

#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;
} 

AC第二个点的代码:

#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;
} 
2024/7/15 18:13
加载中...