Submission #1844920

---

Source Code Expand

#include <cstdio>
#include <algorithm>
typedef long long ll;
inline int Get() {
	char ch;
	while ((ch = getchar()) < '0' || ch > '9');
	int Num = ch - '0';
	while ((ch = getchar()) >= '0' && ch <= '9')
		Num = (Num << 3) + (Num << 1) + ch - '0';
	return Num;
}
const int N = 2e5 + 5;
const int inf = 1e9 + 9;
const int Mod = 1e9 + 7;
int n, X, Y, c[N], w[N], idx[N], id[N], vis[N], que[N], qn, cnt[N], a[N], len;
int tot, first[N], next[N << 3], end[N << 3], ans, fac[N], Ifac[N];
inline bool compare(const int &x, const int &y) {
	return w[idx[x]] < w[idx[y]];
}
inline void AddEdge(int x, int y) {
	next[++tot] = first[x], first[x] = tot, end[tot] = y;
	next[++tot] = first[y], first[y] = tot, end[tot] = x;
} 
inline int calc(int n, int m) {
	return (ll)fac[n] * Ifac[m] % Mod * Ifac[n - m] % Mod;
}
inline int pow(int x, int k) {
	ll res = 1, r = x;
	for (; k; k >>= 1, r = r * r % Mod)
		if (k & 1) res = res * r % Mod;
	return res;
}
inline void solve(int x) {
	vis[x] = true, que[qn = 1] = x;
	for (int ql = 1, u; u = que[ql], ql <= qn; ++ql)
		for (int k = first[u], v; v = end[k], k; k = next[k])
			if (!vis[v]) vis[v] = true, que[++qn] = v;
		
	len = 0;
	for (int ql = 1, u; u = que[ql], ql <= qn; ++ql) 
		if (++cnt[c[u]] == 1) a[++len] = c[u];
	
	for (int i = 1, total = qn; i <= len; ++i) 
		ans = (ll)ans * calc(total, cnt[a[i]]) % Mod, total -= cnt[a[i]];
	
	for (int ql = 1, u; u = que[ql], ql <= qn; ++ql) --cnt[c[u]];
}
int main() {
	n = Get(), X = Get(), Y = Get();
	for (int i = 1; i <= n; ++i) c[i] = Get(), w[i] = Get();
	
	for (int i = 1; i <= n; ++i)
		if (!idx[c[i]] || w[idx[c[i]]] > w[i]) idx[c[i]] = i;
	
	w[0] = inf;
	for (int i = 1; i <= n; ++i) id[i] = i;
	std :: sort(id + 1, id + n + 1, compare);
	
	for (int i = 1; i <= n; ++i) {
		if (w[i] + w[idx[c[i]]] <= X) AddEdge(i, idx[c[i]]);
		if (c[i] != id[1] && w[i] + w[idx[id[1]]] <= Y) AddEdge(i, idx[id[1]]);
		if (c[i] != id[2] && w[i] + w[idx[id[2]]] <= Y) AddEdge(i, idx[id[2]]);
	}
	
	
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % Mod;
	Ifac[n] = pow(fac[n], Mod - 2);
	for (int i = n; i; --i) Ifac[i - 1] = (ll)Ifac[i] * i % Mod;
		
	ans = 1;
	for (int i = 1; i <= n; ++i) if (!vis[i]) solve(i);
	
	printf("%d\n", ans);
}

Submission Info

Judge Result