Submission #1196774

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
static const int MOD = 1000000007;

template <typename T>
static std::pair<T, T> extended_gcd(T a, T b){
	if(b == 0){ return std::pair<T, T>(1, 0); }
	const auto p = extended_gcd(b, a % b);
	return std::pair<T, T>(p.second, p.first - a / b * p.second);
}

template <int MOD>
class modulus_integer {

public:
	typedef modulus_integer<MOD> self_type;

private:
	int m_value;

	static self_type unsafe_construct(int x) noexcept {
		self_type y;
		y.m_value = x;
		return y;
	}

public:
	modulus_integer() noexcept
		: m_value(0)
	{ }

	modulus_integer(int x) noexcept
		: m_value(x % MOD)
	{
		if(m_value < 0){ m_value += MOD; }
	}


	int operator*() const noexcept { return m_value; }


	self_type& operator=(const self_type& x) noexcept {
		m_value = x.m_value;
		return *this;
	}


	bool operator==(const self_type& x) const noexcept {
		return m_value == x.m_value;
	}

	bool operator!=(const self_type& x) const noexcept {
		return m_value != x.m_value;
	}

	bool operator<(const self_type& x) const noexcept {
		return m_value < x.m_value;
	}

	bool operator<=(const self_type& x) const noexcept {
		return m_value <= x.m_value;
	}

	bool operator>(const self_type& x) const noexcept {
		return m_value > x.m_value;
	}

	bool operator>=(const self_type& x) const noexcept {
		return m_value >= x.m_value;
	}


	self_type operator+() const noexcept {
		return *this;
	}

	self_type operator-() const noexcept {
		return unsafe_construct(m_value > 0 ? MOD - m_value : 0);
	}


	self_type operator+(const self_type& x) const noexcept {
		const int y = m_value + x.m_value;
		return unsafe_construct(y >= MOD ? y - MOD : y);
	}

	self_type operator-(const self_type& x) const noexcept {
		const int y = m_value - x.m_value;
		return unsafe_construct(y < 0 ? y + MOD : y);
	}

	self_type operator*(const self_type& x) const noexcept {
		return unsafe_construct(
			static_cast<long long>(m_value) * x.m_value % MOD);
	}

	self_type operator/(const self_type& x) const {
		return (*this) * self_type(extended_gcd(x.m_value, MOD).first);
	}


	self_type& operator+=(const self_type& x) noexcept {
		return (*this = *this + x);
	}

	self_type& operator-=(const self_type &x) noexcept {
		return (*this = *this - x);
	}

	self_type& operator*=(const self_type& x) noexcept {
		return (*this = *this * x);
	}

	self_type& operator/=(const self_type& x){
		return (*this = *this / x);
	}


	self_type& operator++() noexcept {
		if(++m_value >= MOD){ m_value = 0; }
		return *this;
	}

	self_type& operator--() noexcept {
		if(--m_value < 0){ m_value = MOD - 1; }
		return *this;
	}

	self_type operator++(int) noexcept {
		self_type t = *this;
		if(++m_value >= MOD){ m_value = 0; }
		return t;
	}

	self_type operator--(int) noexcept {
		self_type t = *this;
		if(--m_value < 0){ m_value = MOD - 1; }
		return t;
	}

};

using mint = modulus_integer<MOD>;

inline mint modulus_factorial(int n){
	static std::vector<mint> table(1, 1);
	while(static_cast<int>(table.size()) <= n){
		const mint x(static_cast<int>(table.size()));
		table.push_back(x * table.back());
	}
	return table[n];
}

inline mint modulus_inv_factorial(int n){
	static std::vector<mint> table(1, 1);
	while(static_cast<int>(table.size()) <= n){
		const mint x(static_cast<int>(table.size()));
		table.push_back(table.back() / x);
	}
	return table[n];
}

inline mint modulus_combination(int n, int k){
	if(k < 0 || n < k){ return 0; }
	const mint a = modulus_factorial(n);
	const mint b = modulus_inv_factorial(n - k);
	const mint c = modulus_inv_factorial(k);
	return a * b * c;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, x, y;
	cin >> n >> x >> y;
	vector<ll> fact(n + 1);
	fact[0] = 1ll;
	for(int i = 1; i <= n; ++i){
		fact[i] = (fact[i - 1] * i) % MOD;
	}
	vector<vector<int>> raw_balls(n);
	for(int i = 0; i < n; ++i){
		int c, w;
		cin >> c >> w;
		--c;
		raw_balls[c].push_back(w);
	}
	vector<vector<int>> balls;
	for(auto& b : raw_balls){
		if(b.empty()){ continue; }
		sort(b.begin(), b.end());
		balls.emplace_back(move(b));
	}
	const int m = balls.size();
	sort(
		balls.begin(), balls.end(),
		[](const vector<int>& a, const vector<int>& b){ return a[0] < b[0]; });
	int outer_l = 0, outer_r = m;
	while(outer_l < outer_r){
		const int c = outer_l + (outer_r - outer_l) / 2;
		if(balls[0][0] + balls[c][0] <= y){
			outer_l = c + 1;
		}else{
			outer_r = c;
		}
	}
	int outer_count = 0;
	mint answer = 1;
	for(int i = 0; i < outer_l; ++i){
		int limit = x - balls[i][0];
		if(i == 0){
			if(outer_l >= 2){ limit = max(limit, y - balls[1][0]); }
		}else{
			limit = max(limit, y - balls[0][0]);
		}
		int l = 0, r = balls[i].size();
		while(l < r){
			const int c = l + (r - l) / 2;
			if(balls[i][c] <= limit){
				l = c + 1;
			}else{
				r = c;
			}
		}
		answer *= modulus_combination(outer_count + l, l);
		outer_count += l;
	}
	cout << *answer << endl;
	return 0;
}

Submission Info

Judge Result