Submission #1816693

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long s64;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 200000;
const int INF = 0x3f3f3f3f;
const int M = 1000000007;

inline int modpow(int a, const int &n)
{
	int res = 1;
	for (int i = n; i; i >>= 1)
	{
		if (i & 1)
			res = (s64)res * a % M;
		a = (s64)a * a % M;
	}
	return res;
}

int n, lx, ly;
int c[MaxN + 1], w[MaxN + 1];

int le[MaxN + 1];

int cnt[MaxN + 1];

int fact[MaxN + 1];
int rfact[MaxN + 1];

inline void init_fact(int n)
{
	fact[0] = 1;
	for (int i = 1; i <= n; ++i)
		fact[i] = (s64)fact[i - 1] * i % M;

	rfact[n] = modpow(fact[n], M - 2);
	for (int i = n; i; --i)
		rfact[i - 1] = (s64)rfact[i] * i % M;
}

int main()
{
	cin >> n >> lx >> ly;
	for (int i = 1; i <= n; ++i)
		c[i] = getint(), w[i] = getint();

	init_fact(n);

	for (int i = 1; i <= n; ++i)
		le[i] = INF;
	for (int i = 1; i <= n; ++i)
		le[c[i]] = min(le[c[i]], w[i]);

	int c1 = 0, c2 = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (!c1 || le[i] < le[c1])
			c2 = c1, c1 = i;
		else if (!c2 || le[i] < le[c2])
			c2 = i;
	}

	int all = 0;
	for (int i = 1; i <= n; ++i)
	{
		int delta = 0;
		if (c[i] == c1)
			delta = w[i] + le[c1] <= lx || (c2 && w[i] + le[c2] <= ly);
		else
			delta = w[i] + le[c1] <= ly || (w[i] + le[c[i]] <= lx && le[c1] + le[c[i]] <= ly);

		all += delta, cnt[c[i]] += delta;
	}

	int res = fact[all];
	for (int i = 1; i <= n; ++i)
		res = (s64)res * rfact[cnt[i]] % M;

	cout << res << endl;

	return 0;
}

Submission Info

Judge Result