Submission #1195890

---

Source Code Expand

// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>

using namespace std;

#define rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool smin(T &a, const T &b)   { return a > b ? a = b : a;    }
template<typename T> inline bool smax(T &a, const T &b)   { return a < b ? a = b : a;    }

typedef long long LL;

const int N = (int) 1e6 + 6, mod = (int) 1e9 + 7;
vector<int> col[N];
int f[N], par[N], sz[N], inv[N];
map<int, int> c[N];
int fpm(int a, int b) { return b != 0 ? (LL) fpm((LL) a * a % mod, b >> 1) * (b & 1 ? a : 1) % mod: 1; }
pair<int, int> a[N];
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
void unite(int u, int v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	sz[u] += sz[v];
	par[v] = u;
}
int main() {
	f[0] = inv[0] = 1;
	for (int j = 1; j < N; ++j) {
		f[j] = f[j - 1] * (LL) j % mod;
		inv[j] = fpm(f[j], mod - 2);
	}
	ios_base::sync_with_stdio(0);
	int n, x, y;
	cin >> n >> x >> y;
	for (int j = 0; j < n; ++j) {
		par[j] = j;
		sz[j] = 1;
		cin >> a[j].second >> a[j].first;
	}
	sort(a, a + n);
	int cnt = 0;
	for (int j = 0; j < n; ++j) {
		col[a[j].second].push_back(j);	
		if ((j == 0 || a[j].second != a[j - 1].second) && cnt <= 10) {
			++cnt;
			for (int k = 0; k < n; ++k) if (k != j) {
				if (a[k].second == a[j].second) {
					if (a[k].first + a[j].first <= x) {
						unite(k, j);
					}
				} else {
					if (a[k].first + a[j].first <= y) {
						unite(k, j);
					}
				}
			}
		}
	}
	for (int j = 0; j < n; ++j) if ((int) col[j].size()) {
		int fst = col[j][0];
		for (int xx : col[j]) {
			if (a[fst].first + a[xx].first <= x) {
				unite(fst, xx);
			}
		}
	}
	for (int j = 0; j < n; ++j)
		c[find(j)][a[j].second]++;
	int res = 1;
	for (int j = 0; j < n; ++j)
		if (par[j] == j) {
			res = (LL) res * f[sz[j]] % mod;
			for (auto x : c[j]) {
				res = (LL) res * inv[x.second] % mod;
			}
		}
	cout << res << endl;
}

Submission Info

Judge Result