Submission #2093009

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

const ll INF = 1e17+7;


struct UnionFind{

	std::vector<int> data;
	// dataの各要素について
	// 負の値:その集合のルートであること示す。また、その絶対値は集合の要素数となっている。
	// 正の値:親ノードの番号(dataのインデックス)。root()を呼び出すたびに集合のルートを指すように書きなおされるので木はそんなに深くならない

	//初期化 size:最大要素数
	UnionFind(int size): data(size, -1) {}

	// 集合を併合する
	// すでに同じ集合だった場合は、falseが返る
	bool unite(int x, int y){
		x=root(x);
		y=root(y);
		if( x != y ){
			// 要素数の大きな方へ合併するためのswap
			if( data[y] < data[x] ) std::swap(x, y);
			// 要素数を加算する
			data[x] += data[y];
			// yの属する集合のルートをxに変更
			data[y] = x;
		}
		return x!=y;
	}

	// 同じ集合かどうか判定
	bool find(int x, int y){
		return root(x) == root(y);
	}

	// 集合の識別番号を返す
	int root(int x){
		// 負の値を持つものがその集合のルート
		// 正の値は同じ集合に属するものを指す(辿ればいずれルートへ着く)
		return (data[x] < 0)? x : data[x]=root(data[x]);
	}

	// 集合の要素数を返す
	int size(int x){
		return -data[ root(x) ];
	}
};

const ll MOD = 1e9+7;

// n^m%MOD を求める。O( log(m) )
ll modpow(ll n, int m){
	ll ret=1;
	for(int i=1; i<=m; i<<=1, (n*=n)%=MOD){
		if( m&i ) (ret *= n) %= MOD;
	}
	return ret;
}

// 逆元を求める
ll modinv(ll n){
	return modpow( n, MOD-2 );
}

// 階乗を求める。O(1)  準備O( n*log(n) )
// fact[n]     : nの階乗
// fact.inv[n] : nの階乗の逆元
class FACTORIAL{
public:
	vector<ll> fact, inv;
	FACTORIAL(int MAX_NUM): fact(MAX_NUM), inv(MAX_NUM) {
		fact[0] = inv[0] = 1;
		for(ll i=1; i<MAX_NUM; i++){
			fact[i] = (fact[i-1] * i) % MOD;
			inv[i] = modinv( fact[i] );
		}
	}
	const ll& operator [ ] ( const int i ) const {
		return fact[i];
	}
} fact(1000006); // nの最大値を指定


// 組み合わせ(Combinationを求める) O(1)
ll cmb(unsigned int n, unsigned int r){
	if( n < r ) return 0;
	return fact[n] * fact.inv[r] % MOD * fact.inv[n-r] % MOD;
}

int main(){
	ios_base::sync_with_stdio(false);
	ll N, X, Y;
	ll c[200005], w[200005];

	cin >> N >> X >> Y;
	rep(i,N){
		cin >> c[i] >> w[i];
		c[i]--;
	}

	pll mn[200005];
	Fill(mn, pll(INF,-1));
	rep(i,N) chmin(mn[ c[i] ], pll(w[i], i));

	UnionFind uf(200005);

	vector<pll> v;
	rep(i,N) if( mn[i].Y >= 0 ) v.push_back( mn[i] );
	sort(all(v));
	reps(i,1,v.size()){
		if( v[i-1].X + v[i].X <= Y ) uf.unite(v[i-1].Y, v[i].Y);
	}

	rep(i,N){
		auto p = c[i];
		if( mn[p].X + w[i] <= X ) uf.unite(mn[p].Y, i);
		if( c[ v[0].Y ] != p ){
			if( v[0].X + w[i] <= Y ) uf.unite(v[0].Y, i);
		}else if( v.size() > 1 ){
			if( v[1].X + w[i] <= Y ) uf.unite(v[1].Y, i);
		}
	}

	ll ans = 1;
	rep(i,N) if(uf.root(i) == i){
		ans *= fact[ uf.size(i) ];
		ans %= MOD;
	}

	map<pll,ll> count;
	{
		//ll count[200005]={};
		rep(i,N) count[ pll(uf.root(i),c[i]) ]++;

		//rep(i,N) if( count[i] > 1 ){
		for(auto p: count){
			ans *= fact.inv[ p.Y ];
			ans %= MOD;
		}
	}

	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result