Submission #2381760

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const ll MOD = 1000000007;
const int MN = 200010;

ll mod_pow(ll x, ll k)
{
	ll res = 1;
	for (; k; k /= 2, x = x * x % MOD) {
		if (k & 1) {
			res = res * x % MOD;
		}
	}
	return res;
}

int N, X, Y;
vi vec[MN];

ll fac[MN], ifac[MN];
ll comb(int n, int k) {
	if (k < 0 || k > n) return 1;
	return fac[n] * ifac[k] % MOD * ifac[n-k] % MOD;
}

int main() {
	fac[0] = ifac[0] = 1;
	for (int i = 1; i < MN; ++i) {
		fac[i] = fac[i-1] * i % MOD;
		ifac[i] = ifac[i-1] * mod_pow(i, MOD - 2) % MOD;
	}

	cin >> N >> X >> Y;

	rep(i, N) {
		int c, w;
		cin >> c >> w; --c;
		vec[c].pb(w);
	}

	rep(i, N) sort(ALL(vec[i]));

	vector<pii> mns;
	rep(i, N) if (vec[i].size()) {
		mns.eb(vec[i][0], i);
		int p = 1;
		while (p < vec[i].size() && vec[i][p] + vec[i][0] <= X) {
			vec[i][p] = vec[i][0];
			++p;
		}
	}
	
	sort(ALL(mns));

	if (mns.size() == 1) {
		puts("1");
		return 0;
	}

	vi nums;
	for (int i = 1; i < mns.size(); ++i) {
		int id = mns[i].se;
		if (mns[i].fi + mns[0].fi <= Y) {
			int p = upper_bound(ALL(vec[id]), Y - mns[0].fi) - vec[id].begin();
			nums.pb(p);
		}
	}

	int id = mns[0].se;
	if (mns[0].fi + mns[1].fi <= Y) {
		int p = upper_bound(ALL(vec[id]), Y - mns[1].fi) - vec[id].begin();
		nums.pb(p);		
	}

	int sum = 0;
	for (int x:nums) {
		sum += x;
	}

	ll t = fac[sum];

	for (int x:nums) {
		t = t * ifac[x] % MOD;
	}
	cout << t << endl;
	return 0;
}

Submission Info

Judge Result