Submission #1722189

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int MOD=1e9+7;
ll fact[200001];
ll ifact[200001];

ll mult(ll a, ll b)
{
	return (a*b)%MOD;
}

ll modpow(ll a, ll b)
{
	ll r=1;
	while(b)
	{
		if(b&1) r=(r*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return r;
}

ll inv(ll a)
{
	return modpow(a,MOD-2);
}

map<int,int> dsu[200001];
int par[200001];

int rt(int u)
{
	if(par[u]<0) return u;
	return (par[u]=rt(par[u]));
}

void merge(int u, int v)
{
	u=rt(u);v=rt(v);
	if(u==v) return ;
	if(dsu[u].size()<dsu[v].size()) swap(u,v);
	for(mit it = dsu[v].begin();it!=dsu[v].end();it++)
	{
		dsu[u][it->fi]+=it->se;
	}
	par[v]=u;
	//par[u]=-1;
}

ll solve(int x)
{
	if(x!=rt(x)) return 1;
	ll tot = 0;
	ll ans = 1;
	for(mit it = dsu[x].begin();it!=dsu[x].end();it++)
	{
		//cerr<<it->fi<<' '<<it->se<<'\n';
		tot+=it->se;
		ans=(ans*ifact[it->se])%MOD;
	}
	ans=mult(ans,fact[tot]);
	return ans;
}

vector<ii> adj[200001];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	fact[0]=1;ifact[0]=1;
	for(int i=1;i<=200000;i++)
	{
		fact[i]=mult(fact[i-1],i);
		ifact[i]=inv(fact[i]);
	}
	memset(par,-1,sizeof(par));
	int n; cin>>n;
	ll a,b;cin>>a>>b;
	vector<pair<ii,int> > vec;
	for(int i=0;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		x--;
		adj[x].pb(mp(y,i));
		vec.pb(mp(mp(y,x),i));
		dsu[i][x]++;
	}
	sort(vec.begin(),vec.end());
	for(int i=0;i<n;i++)
	{
		sort(adj[i].begin(),adj[i].end());
		for(int j=1;j<adj[i].size();j++)
		{
			if(adj[i][0].fi+adj[i][j].fi<=a)
			{
				//cerr<<adj[i][0].se<<' '<<adj[i][j].se<<'\n';
				merge(adj[i][0].se,adj[i][j].se);
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		if(vec[0].fi.se!=vec[i].fi.se&&vec[0].fi.fi+vec[i].fi.fi<=b)
		{
			//cerr<<vec[0].se<<' '<<vec[i].se<<'\n';
			merge(vec[0].se,vec[i].se);
		}
	}
	int ptr=0;
	while(ptr<n&&vec[0].fi.se==vec[ptr].fi.se) ptr++;
	if(ptr<n)
	{
		for(int i=0;i<n;i++)
		{
			if(vec[ptr].fi.se!=vec[i].fi.se&&vec[ptr].fi.fi+vec[i].fi.fi<=b)
			{
				//cerr<<vec[ptr].se<<' '<<vec[i].se<<'\n';
				merge(vec[ptr].se,vec[i].se);
			}
		}
	}
	ll ans = 1;
	for(int i=0;i<n;i++)
	{
		ans=mult(ans,solve(i));
	}
	cout<<ans<<'\n';
}	

Submission Info

Judge Result