列表

详情

NC17341. Skyline

描述

There are n points (not necessary distinct) on the plane. Suppose that each point (xi,yi) has an associated probability of existence pi ∈ (0, 1].
For a point set S={(x1,y1), (x2,y2), ..., (xm,ym)}, define F(S) as the number of integer points (x,y) that: there exists at least one index i that 0 < x ≤ xi and 0 < y ≤ yi.
Chiaki would like to know the expectation of F(S) of the n stochastic points.

输入描述

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 105) -- the number of points.
Each of the next n lines contains four integers xi, yi, ai and bi (1 ≤ xi, yi ≤ 109, 1 ≤ ai ≤ bi ≤ 109), where .
It is guaranteed that the sum of all n does not exceed 106.

输出描述

For each test case, output the answer as a value of a rational number modulo 109 + 7.
Formally, it is guaranteed that under given constraints the probability is always a rational number  (p and q are integer and coprime, q is positive), such that q is not divisible by 109 + 7. Output such integer a between 0 and 109 + 6 that p - aq is divisible by 109 + 7.

示例1

输入: 

2
3
1 2 1 1
1 2 1 1
1 2 1 1
4
1 2 1 2
1 3 1 2
2 1 1 2
3 1 1 2

输出: 

2
937500010

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 2904ms, 内存消耗: 68500K, 提交时间: 2018-07-31 14:59:08 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=4e5+7;
const int P=1e9+7;
const int lim=1e9;
struct node{
	int x,y,p,q;
	bool operator < (const node &A)const {
	   return x>A.x;
	}
}A[N];
//val[x]代表(1-p)的乘积 
int sum[N<<3],L[N<<3],R[N<<3],lazy[N<<3],tot=0,rt;
int newnode(int l,int r){
	++tot;
	sum[tot]=r-l+1;
	L[tot]=R[tot]=0;
	lazy[tot]=1;
	return tot;
}
int ksm(int x,int k){
	int ans=1;
	for(;k;k>>=1,x=1LL*x*x%P) if(k&1) ans=1LL*ans*x%P;
	return ans;
} 
void pw(int l,int r,int x){
	//printf("%d %d %d\n",l,r,x);
	if(lazy[x]!=1){
		int m=(l+r)>>1;
		if(!L[x]) L[x]=newnode(l,m);if(!R[x]) R[x]=newnode(m+1,r);
		lazy[L[x]]=1LL*lazy[L[x]]*lazy[x]%P,lazy[R[x]]=1LL*lazy[R[x]]*lazy[x]%P;
		sum[L[x]]=1LL*sum[L[x]]*lazy[x]%P;
		sum[R[x]]=1LL*sum[R[x]]*lazy[x]%P;
		lazy[x]=1;
		return;
	}
}
void update(int l,int r,int ql,int qr,int &x,int v){
	if(!x) x=newnode(ql,qr);
	if(l<=ql&&r>=qr){
		sum[x]=1LL*sum[x]*v%P;
		lazy[x]=1LL*lazy[x]*v%P;
		return;
	}
	pw(ql,qr,x);
	int m=(ql+qr)>>1;
	if(l<=m) update(l,r,ql,m,L[x],v);
	if(r>m)  update(l,r,m+1,qr,R[x],v);
	if(!L[x]) L[x]=newnode(ql,m);
	if(!R[x]) R[x]=newnode(m+1,qr);
	sum[x]=(sum[L[x]]+sum[R[x]])%P;
//	printf("%d %d %d %d %d\n",ql,qr,sum[x],sum[L[x]],sum[R[x]]);
}
int main(){
	int T,n;
	for(scanf("%d",&T);T--;){
		tot=rt=0;
		scanf("%d",&n);
		for(int i=1;i<=n;++i) {
			scanf("%d%d%d%d",&A[i].x,&A[i].y,&A[i].p,&A[i].q);
		}
		sort(A+1,A+n+1);
		int ans=0,last=A[1].x,l=1;
		for(;l<=n;){
			while(l<=n&&A[l].x==last) update(1,A[l].y,1,lim,rt,1LL*(A[l].q-A[l].p)*ksm(A[l].q,P-2)%P),++l;
			ans=(ans+1LL*(last-A[l].x)*(lim-sum[1])%P)%P;
			last=A[l].x;
		}
		//ans=(ans+1LL*(A[n].x-1)*sum[1]%P)%P;
		printf("%d\n",ans);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 2742ms, 内存消耗: 99296K, 提交时间: 2018-08-03 12:04:12 

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define dep(i,x,y) for(int i=(x);i>=(y);i--)
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define abs(x) ((x)<0?-(x):(x))
#define add(x,y) x=(x+(y))%mo
#define sqr(x) ((x)*(x))
#define gc getchar()
#define N 4000000
#define ll long long
#define inf 1000000000
#define Inf 1000000000000000000ll
#define mo 1000000007
#define eps 1e-8
using namespace std;
int T,n,tot,L[N],R[N],ls[N],rs[N];
ll ans,x,y,a[N],b[N];
struct pr{int x,y;ll z;}p[100010];
ll qk(ll x,int y){ll r=1;
	for(int z=(1<<30);z;z>>=1){
		r=r*r%mo;if(y&z)r=r*x%mo;
	}return r;
}
bool cmp(pr x,pr y){return x.x>y.x;}
void f(int x,int l,int r,ll y){
	if((l==L[x])&&(r==R[x])){
		a[x]=a[x]*y%mo;b[x]=b[x]*y%mo;return;
	}
	if(!ls[x]){
		ls[x]=++tot;L[tot]=L[x];R[tot]=(L[x]+R[x])/2;
		ls[tot]=rs[tot]=0;a[tot]=R[tot]-L[tot]+1;b[tot]=1;
		rs[x]=++tot;L[tot]=R[tot-1]+1;R[tot]=R[x];
		ls[tot]=rs[tot]=0;a[tot]=R[tot]-L[tot]+1;b[tot]=1;
	}
	if(r<L[rs[x]])f(ls[x],l,r,y);
	else if(l>R[ls[x]])f(rs[x],l,r,y);else{
		f(ls[x],l,R[ls[x]],y);f(rs[x],L[rs[x]],r,y);
	}
	a[x]=(a[ls[x]]+a[rs[x]])*b[x]%mo;
}
int main(){
	for(scanf("%d",&T);T;T--){
		tot=1;L[1]=1;R[1]=inf;ls[1]=rs[1]=0;
		a[1]=inf;b[1]=1;ans=0;scanf("%d",&n);
		rep(i,1,n){
			scanf("%d%d%lld%lld",&p[i].x,&p[i].y,&x,&y);
			x=(y-x)*qk(y,mo-2)%mo;p[i].z=x;
		}
		sort(p+1,p+n+1,cmp);p[0].x=inf;
		rep(i,1,n){
			ans=(ans+a[1]*(p[i-1].x-p[i].x))%mo;
			f(1,1,p[i].y,p[i].z);
		}
		ans=(ans+a[1]*p[n].x)%mo;
		ans=(Inf-ans)%mo;printf("%lld\n",ans);
	}
}

上一题

© 2024 nowcoder.com