导弹拦截求条
查看原帖
导弹拦截求条
1015770
Arteg楼主2024/9/14 20:42

全wa,2pts。

/*
 前之君待,湿露月九。
 问有我无,谁为方彼。
*/
#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define ld long double
#define lb(x) (x&-x)
#define mid ((l+r)>>1)

const int maxn=50010;
const int mo=1000000007;
const int inf=0x7f7f7f7f7f7f7f7f;

inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

void write(int x){
	if(x<0)
		x=-x;
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
	return ;
}

int n,ans,dp1[maxn],dp2[maxn];
ld f1[maxn],f2[maxn],sum;

struct node{
	int h,v,t,dp;
	ld f;
}q[maxn];

bool cmp1(node x,node y){
	if(x.h!=y.h)
		return x.h>y.h;
	if(x.v!=y.v)
		return x.v>y.v;
	return x.t<y.t;
}

bool cmp2(node x,node y){
	if(x.h!=y.h)
		return x.h<y.h;
	if(x.v!=y.v)
		return x.v<y.v;
	return x.t<y.t;
}

bool cmp3(node x,node y){
	if(x.v!=y.v)
		return x.v>y.v;
	if(x.t!=y.t)
		return x.t<y.t;
	return x.h>y.h;
}

bool cmp4(node x,node y){
	if(x.v!=y.v)
		return x.v<y.v;
	if(x.t!=y.t)
		return x.t<y.t;
	return x.h<y.h;
}

struct st{
	#define ls (p<<1)
	#define rs (p<<1|1)
	int ma[maxn<<2],an1;
	ld num[maxn<<2],an2;
	st(){
		memset(ma,0,sizeof(ma));
		memset(num,0,sizeof(num));
		return ;
	}
	void up(int p){
		ma[p]=max(ma[ls],ma[rs]);
		num[p]=0;
		if(ma[p]==ma[ls])
			num[p]+=num[ls];
		if(ma[p]==ma[rs])
			num[p]+=num[rs];
		return ;
	}	
	void update(int p,int l,int r,int q,int v,ld v1){
		if(l==r){
			ma[p]=v;
			num[p]=v1;
			return ;
		}
		if(q<=mid)
			update(ls,l,mid,q,v,v1);
		else
			update(rs,mid+1,r,q,v,v1);
		up(p);
		return ;
	}
	void ask(int p,int l,int r,int s,int t){
		if(l>=s&&r<=t){
			if(ma[p]==an1)
				an2+=num[p];
			else if(ma[p]>an1){
				an1=ma[p];
				an2=num[p];
			}
			return ;
		}
		if(s<=mid)
			ask(ls,l,mid,s,t);		
		if(t>mid)
			ask(rs,mid+1,r,s,t);
		return ;
	}
	void clear(int p,int l,int r){
		if(l==r){
			ma[p]=0;
			num[p]=0;
			return ;
		}
		if(ma[ls])
			clear(ls,l,mid);
		if(ma[rs])
			clear(rs,mid+1,r);
		up(p);
		return ;
	}
}tr;

bool check(int i,int j,int op){
	if(op==1)
		return q[i].v>=q[j].v;
	else
		return q[i].v<=q[j].v;
}

void cdq(int l,int r,int op){
	if(l==r)
		return ;
	cdq(l,mid,op);
	if(op==1){
		sort(q+l,q+mid+1,cmp3);
		sort(q+mid+1,q+r+1,cmp3);
	}
	else{
		sort(q+l,q+mid+1,cmp4);
		sort(q+mid+1,q+r+1,cmp4);		
	}
	int i=l,j=mid+1;
	while(i<=mid&&j<=r){
		if(check(i,j,op)){
			tr.update(1,1,n,q[i].t,q[i].dp,q[i].f);
			i++;
		}
		else{
			tr.an1=0;
			tr.an2=0;
			tr.ask(1,1,n,1,q[j].t);
			int vv=tr.an1+1;
			ld nn=tr.an2;
			if(q[j].dp==vv)	
				q[j].f+=nn;		
			else if(q[j].dp<vv){
				q[j].dp=vv;
				q[j].f=nn;
			}
			j++;
		}
	}
	while(j<=r){
		tr.an1=0;
		tr.an2=0;
		tr.ask(1,1,n,1,q[j].t);
		int vv=tr.an1+1;
		ld nn=tr.an2;
		if(q[j].dp==vv)	
			q[j].f+=nn;		
		else if(q[j].dp<vv){
			q[j].dp=vv;
			q[j].f=nn;
		}
		j++;		
	}
	tr.clear(1,1,n);
	if(op==1)
		sort(q+mid+1,q+r+1,cmp1);
	else
		sort(q+mid+1,q+r+1,cmp2);
	cdq(mid+1,r,op);
	return ;
}

signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		q[i].h=read();
		q[i].v=read();
		q[i].t=i;
		q[i].dp=q[i].f=1;
	}
	sort(q+1,q+n+1,cmp1);
	cdq(1,n,1);
	for(int i=1;i<=n;i++){
		dp1[q[i].t]=q[i].dp;
		f1[q[i].t]=q[i].f;
		ans=max(ans,dp1[q[i].t]);
	}
	for(int i=1;i<=n;i++){
		q[i].t=n-q[i].t+1;
		q[i].dp=q[i].f=1;		
	}
	sort(q+1,q+n+1,cmp2);
	cdq(1,n,2);
	for(int i=1;i<=n;i++){
		dp2[n-q[i].t+1]=q[i].dp;
		f2[n-q[i].t+1]=q[i].f;
		if(dp2[n-q[i].t+1]==ans)
			sum+=f2[n-q[i].t+1];
	}
	write(ans);
	putchar('\n');
	for(int i=1;i<=n;i++){
		if(dp1[i]+dp2[i]==ans+1){
			printf("%.6Lf ",f1[i]*f2[i]/sum);			
		}							
		else
			printf("0.000000 ");
	}
	putchar('\n');
	return 0;
}
2024/9/14 20:42
加载中...