Submission #2834662

---

Source Code Expand

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define pb push_back
const int ha=1e9+7,N=200005;

inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}
inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}

inline int ksm(int x,int y){
	int an=1;
	for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;
	return an;
} 

inline int read(){
	int x=0; char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x;
}

vector<int> g[N],now;
int dfn[N],dc,num[N],jc[N],ni[N],ans=1,sz;
int n,X,Y,col[N],w[N],mn[N],p[N],pos[2],C;
bool v[N];

inline void ae(int x,int y){ g[x].pb(y),g[y].pb(x);}

inline void init(){
	// prepare n! and (n!)^(-1)
	jc[0]=1;
	for(int i=1;i<=n;i++) jc[i]=jc[i-1]*(ll)i%ha;
	ni[n]=ksm(jc[n],ha-2);
	for(int i=n;i;i--) ni[i-1]=ni[i]*(ll)i%ha;
	
	// prepare edges between different colors
	for(int i=1;i<=n;i++)
	    if(mn[i]<mn[pos[0]]) pos[1]=pos[0],pos[0]=i;
		else if(mn[i]<mn[pos[1]]) pos[1]=i;
	pos[0]=p[pos[0]],pos[1]=p[pos[1]];
	
	int yz=Y-w[pos[0]],yo=Y-w[pos[1]],cx=col[pos[0]],cy=col[pos[1]];
	
	for(int i=1;i<=n;i++){
		C=col[i];
		if(C!=cx&&w[i]<=yz) ae(i,pos[0]);
		if(C!=cy&&w[i]<=yo) ae(i,pos[1]);		
	}
	
	// prepare edges between the same colors
	for(int i=1;i<=n;i++){
		C=col[i];
	    if(i!=p[C]&&w[i]+w[p[C]]<=X) ae(i,p[C]);
	}
}

void dfs(int x){
	v[x]=1,sz++,C=col[x];
	if(dfn[C]!=dc) dfn[C]=dc,now.pb(C),num[C]=1;
	else num[C]++;
	
	for(int i:g[x]) if(!v[i]) dfs(i);
}

inline void solve(){
	// calculate
	for(int i=1;i<=n;i++) if(!v[i]){
		dc++,now.clear(),sz=0;
		dfs(i),ans=ans*(ll)jc[sz]%ha;
		for(int j:now) ans=ans*(ll)ni[num[j]]%ha;
	}
}

int main(){
	memset(mn,0x3f,sizeof(mn)),w[0]=1e9+233;
	
	n=read(),X=read(),Y=read();
	for(int i=1;i<=n;i++){
		C=col[i]=read(),w[i]=read();
		if(w[i]<mn[C]) mn[C]=w[i],p[C]=i;
	}
	
	init(),solve();
	
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result