Submission #1678897

---

Source Code Expand

// tzl ak IOI! 
 
#include<bits/stdc++.h>
 
#define HEAP priority_queue
#define rep(i, n) for(int i = 0, _end_ = (n); i < _end_; ++i)
#define per(i, n) for(int i = (n) - 1; i >= 0 ; --i)
#define forn(i, l, r) for(int i = (l), _end_ = (r); i <= _end_; ++i)
#define nrof(i, r, l) for(int i = (r), _end_ = (l); i >= _end_; --i)
#define FOR(a, b) for(auto (a): (b))
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define X first
#define Y second
#define eps 1e-6
#define pi 3.1415926535897932384626433832795
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(), x.end()
#define FILL(a, b) memset((a), (b), sizeof((a)))
#define MCPY(a, b) memcpy((a), (b), sizeof((b)))
 
using namespace std;
 
typedef long long LL;
typedef double flt;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef pair<int,int> pii;
typedef pair<int,LL> pil;
typedef pair<LL,int> pli;
typedef pair<LL,LL> pll;
typedef vector<pil> vil;
typedef vector<pii> vii;
typedef vector<pli> vli;
typedef vector<pll> vll;
 
const int iinf = 1e9 + 7;
const LL linf = 1ll << 60;
const flt dinf = 1e60;
 
template <typename T>
inline void scf(T &x)
{
	bool f = 0; x = 0; char c = getchar();
	while((c < '0' || c > '9') && c != '-') c = getchar();
	if(c == '-') { f = 1; c = getchar(); }
	while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
	if(f) x = -x; return;
}
 
template <typename T1, typename T2>
void scf(T1 &x, T2 &y) { scf(x); return scf(y); }
 
template <typename T1, typename T2, typename T3>
void scf(T1 &x, T2 &y, T3 &z) { scf(x); scf(y); return scf(z); }
 
template <typename T1, typename T2, typename T3, typename T4>
void scf(T1 &x, T2 &y, T3 &z, T4 &w) { scf(x); scf(y); scf(z); return scf(w); }
 
inline char mygetchar(){ char c = getchar(); while(c == ' ' || c == '\n') c = getchar(); return c; }
 
template <typename T>
void chkmax(T &x, const T &y){ if(y > x) x = y; return; }
 
template <typename T>
void chkmin(T &x, const T &y){ if(y < x) x = y; return; }
 
#ifdef ONLINE_JUDGE
#define debug(x,c) ;
#else
#define DEBUG
#define debug(x,c) cerr<<#x<<"="<<x<<c;
#endif
 
void TZL();
 
void RANK1();
 
#define tzl int
#define ak main
#define IOI ()
tzl ak IOI
{
#undef tzl
#undef ak
#undef IOI
 
	TZL();
	RANK1();
 
#define tzl return
#define caisi 0
#define myy ;
	tzl caisi myy
#undef tzl
#undef caisi
#undef myy
}
 
//---------------------------head----------------------------
 
const int mod = 1e9 + 7;
const int N = 2e5 + 100;
 
int mn1, mn2, rem1, rem2;
int n, X, Y;
int col[N], w[N];
vi all;
 
struct color
{
	int mn, mx, cnt;
	vi apr;
 
	void init()
	{
		cnt = 0, mx = 0, mn = iinf;
		for(int i: apr)
		{
			chkmin(mn, w[i]);
			chkmax(mx, w[i]);
		}
		return;
	}
 
	void work(int o_mn)
	{
		for(int i: apr)
		{
			int w = ::w[i];
			if(w + mn <= X || w + o_mn <= Y) ++cnt;
		}
		return;
	}
}a[N];
 
int fac[N], ifac[N];
 
int pow_mod(int x, int n)
{
	int ret = 1;
	while(n)
	{
		if(n & 1) ret = 1ll * ret * x % mod;
		x = 1ll * x * x % mod;
		n >>= 1;
	}
	return ret;
}
 
int C(int n, int m)
{
	if(n < m || n < 0 || m < 0) return 0;
	return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
 
void TZL()
{
	scf(n, X, Y);
	forn(i, 1, n) scf(col[i], w[i]);
	forn(i, 1, n) a[col[i]].apr.pb(i), all.pb(col[i]);
	sort(ALL(all)); all.resize(unique(ALL(all)) - all.begin());
	for(int c: all) a[c].init();
 
	mn1 = iinf, mn2 = iinf;
	for(int c: all)
	{
		int mn = a[c].mn;
		if(mn < mn1) mn2 = mn1, rem2 = rem1, mn1 = mn, rem1 = c;
		else if(mn < mn2) mn2 = mn, rem2 = c;
	}
 
	for(int c: all)
	{
		if(c == rem1) a[c].work(mn2); else a[c].work(mn1);
	}
	
	fac[0] = 1;
	forn(i, 1, n) fac[i] = 1ll * i * fac[i - 1] % mod;
	forn(i, 0, n) ifac[i] = pow_mod(fac[i], mod - 2);
	return;
}
 
vi lft;
 
void RANK1()
{
	int sum = 0, ans = 1;
	for(int c: all)
	{
		int o_mn;
		if(c == rem1) o_mn = mn2; else o_mn = mn1;
		if(o_mn + a[c].mn <= Y) lft.pb(a[c].cnt), sum += a[c].cnt;
	}
 
	for(int x: lft)
	{
		ans = 1ll * ans * C(sum, x) % mod;
		sum -= x;
	}
	printf("%d\n", ans);
	return;
}

Submission Info

Judge Result