Submission #1863056

---

Source Code Expand

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200200,M=2002000,P=1000000007;
int i,j,k,n,m,En,X,Y,ch,ff,mi1,mi2,An,ans;
int c[N],w[N],h[N],mi[N],A[N],z[N],Jc[N],Jc_[N];
struct edge { int s,n;} E[M];
void R(int &x) {
	ff=x=0;ch=getchar();
	while (ch<'0' || '9'<ch) { if (ch=='-') ff=1;ch=getchar();}
	while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar();
	if (ff) x=-x;
}
void E_add(int x,int y) {
	E[++En].s=y;E[En].n=h[x];h[x]=En;
	E[++En].s=x;E[En].n=h[y];h[y]=En;
}
void dfs(int x) {
	A[++An]=c[x];z[x]=1;
	for (int k=h[x];k;k=E[k].n) if (!z[E[k].s]) dfs(E[k].s);
}
int ksm(int x,int y) {
	int z=1;
	for (;y;y>>=1,x=(ll) x*x%P) if (y&1) z=(ll) z*x%P;
	return z;
}
void pre(int n) {
	int i;
	Jc[0]=Jc_[0]=1;
	for (i=1;i<=n;i++) Jc[i]=(ll) Jc[i-1]*i%P;
	Jc_[n]=ksm(Jc[n],P-2);
	for (i=n-1;i;i--) Jc_[i]=(ll) Jc_[i+1]*(i+1)%P;
}
int main() {
	R(n);R(X);R(Y);
	w[0]=P;
	pre(n);
	for (i=1;i<=n;i++) {
		R(c[i]);R(w[i]);
		if (c[i]<w[mi[c[i]]]) mi[c[i]]=i;
	}
	for (i=1;i<=n;i++) if (mi[i]) {
		if (w[mi[i]]<w[mi1]) mi2=mi1,mi1=mi[i];
		else {
			if (w[mi[i]]<w[mi2]) mi2=mi[i];
		}
	}
	for (i=1;i<=n;i++) {
		if (w[i]+w[mi[c[i]]]<=X) E_add(i,mi[c[i]]);
		if (c[i]!=c[mi1] && w[i]+w[mi1]<=Y) E_add(i,mi1);
		if (c[i]!=c[mi2] && w[i]+w[mi2]<=Y) E_add(i,mi2);
	}
	ans=1;
	for (i=1;i<=n;i++) if (!z[i]) {
		An=0;
		dfs(i);
		sort(A+1,A+An+1);
		ans=(ll) ans*Jc[An]%P;
		for (j=1;j<=An;j++) {
			k=j;
			while (k<An && A[k+1]==A[j]) k++;
			ans=(ll) ans*Jc_[k-j+1]%P;
			j=k;
		}
	}
	printf("%d\n",ans);
}

Submission Info

Judge Result