Submission #1674733

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
	x=0;int 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();}
	x*=f;
}
inline void judge(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
const int maxn=200005;
int X,Y,n;
struct info{
	int w,c;
	inline void init(){read(c);read(w);}
}a[maxn];
inline bool operator < (const info &a,const info &b){
	return a.c<b.c||(a.c==b.c&&a.w<b.w);
}
priority_queue<pin,vector<pin>,greater<pin> > heap;
int fa[maxn],v[maxn],id2,lv1,lv2;
int fac[maxn],facinv[maxn];
const int mod=1e9+7;
inline int powmod(int a,int b){
	int res=1;for(;b;b>>=1){
		if(b&1)res=1ll*res*a%mod;
		a=1ll*a*a%mod;
	}return res;
}
inline void prprpr(){
	fac[0]=1;
	rep(i,1,200000)fac[i]=1ll*fac[i-1]*i%mod;
	facinv[200000]=powmod(fac[200000],mod-2);
	per(i,200000-1,0)facinv[i]=1ll*facinv[i+1]*(i+1)%mod;
}
inline int find(int n){
	int step=n,x;
	while(step!=fa[step])step=fa[step];
	while(n!=step)x=fa[n],fa[n]=step,n=x;return n;
}
map<int,int> tot[maxn];
vector<int> wt;
inline void maintain(){
	while(heap.size()>=2){
		pin x=heap.top();heap.pop();
		pin y=heap.top();heap.pop();
		if(x.w1+y.w1<=Y){
			fa[y.w2]=x.w2;
			heap.push(x);
		}else{
			heap.push(x);
			heap.push(y);
			break;
		}
	}
}
int main(){
    prprpr();
    read(n);read(X);read(Y);
    rep(i,1,n)a[i].init();
    sort(a+1,a+1+n);
    rep(i,1,n){
    	if(a[i].c!=a[i-1].c){
    		if(id2){
    			v[id2]=min(v[id2],lv2);
    			heap.push(mk(v[id2],id2));
    			assert(heap.top()==mk(v[id2],id2));
    			if(v[id2]==lv2)
    			maintain();
    			id2=0;lv1=0;lv2=0;
    		}
    		for(int x:wt){
    			heap.push(mk(v[x],x));
    		}
    		wt.clear();
    	}
    	if(id2){
    		if(a[i].w+lv2<=X){
    			fa[i]=id2;
    			continue;
    		}
    		if(a[i].w+lv1<=Y){
    			fa[i]=id2;
    			continue;
    		}
    		v[i]=a[i].w;
    		fa[i]=i;
  	 		// heap.push(mk(v[i],i));
  	 		wt.pb(i);
    		continue;
    	}
    	pin x=mk(0,0);
    	if(heap.size())x=heap.top();
    	if(x==mk(0,0)){
    		v[i]=a[i].w;
    		fa[i]=i;
    		lv1=1e9;id2=i;lv2=a[i].w;
    		continue;
    	}
    	if(a[i].w+v[x.w2]<=Y){
    		id2=x.w2;fa[i]=id2;
    		lv2=a[i].w;lv1=v[id2];
    		heap.pop();
    		continue;
    	}
    	v[i]=a[i].w;
    	fa[i]=i;id2=i;lv2=a[i].w;lv1=1e9;
    }
    rep(i,1,n)tot[find(i)][a[i].c]++;
    int res=1;
    rep(i,1,n){
    	int sum=0;
    	for(pin x:tot[i]){
    		res=1ll*res*facinv[x.w2]%mod;
    		sum+=x.w2;
    	}
    	res=1ll*res*fac[sum]%mod;
    }
    printf("%d\n",res);
    return 0;
}

Submission Info

Judge Result