fork(5) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4. #define fo(i,n) for(i=0;i<n;i++)
  5. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  6. #define ll long long
  7. #define si(x) scanf("%d",&x)
  8. #define sl(x) scanf("%lld",&x)
  9. #define ss(s) scanf("%s",s)
  10. #define pi(x) printf("%d\n",x)
  11. #define pl(x) printf("%lld\n",x)
  12. #define ps(s) printf("%s\n",s)
  13. #define pb push_back
  14. #define mp make_pair
  15. #define F first
  16. #define S second
  17. #define all(x) x.begin(), x.end()
  18. #define clr(x) memset(x, 0, sizeof(x))
  19. #define sortall(x) sort(all(x))
  20. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  21. #define PI 3.1415926535897932384626
  22. typedef pair<int, int> pii;
  23. typedef pair<ll, ll> pl;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vl;
  26. typedef vector<pii> vpii;
  27. typedef vector<pl> vpl;
  28. typedef vector<vi> vvi;
  29. typedef vector<vl> vvl;
  30. int mpow(int base, int exp);
  31. void ipgraph(int m);
  32. void dfs(int u, int par);
  33. const int mod = 1000000007;
  34. const int N = 3e5, M = N;
  35. //=======================
  36.  
  37. vi g[N];
  38. int a[N], col[N], w[N]; ll fac[N], inv[N];
  39. bool f(int x, int y){
  40. return w[x] < w[y];
  41. }
  42. map<int, int> cnt[N];
  43. int par[N], sz[N];
  44. int rep(int x){
  45. if(x == par[x]) return x;
  46. return par[x] = rep(par[x]);
  47. }
  48. void unite(int x, int y){
  49. x = rep(x);
  50. y = rep(y);
  51. if(x == y) return;
  52. if(sz[x]>sz[y]) swap(x, y);
  53. par[x] = y;
  54. sz[y] += sz[x] == sz[y];
  55. }
  56. int minof[N];
  57. int tot[N];
  58. int main()
  59. {
  60. ios_base::sync_with_stdio(false);
  61. cin.tie(NULL);
  62. int i,n,k,j,x,y;
  63. fac[0] = inv[0] = 1;
  64. Fo(i, 1, N){
  65. fac[i] = (i*fac[i-1])%mod;
  66. inv[i] = (mpow(i, mod-2)*inv[i-1])%mod;
  67. par[i] = i;
  68. sz[i] = 1;
  69. }
  70. cin >> n >> x >> y;
  71. Fo(i, 1, n+1){
  72. cin >> col[i] >> w[i];
  73. g[col[i]].pb(i);
  74. }
  75. Fo(i, 1, n+1){
  76. //uniting of color[i]
  77. minof[i] = mod;
  78. if(g[i].empty()) continue;
  79. sort(all(g[i]), f);
  80. int base = g[i][0];
  81. minof[i] = w[base];
  82. for(int v: g[i]){
  83. if(w[v]+w[base] <= x) unite(v, base);
  84. }
  85. }
  86. minof[0] = mod;
  87. int mn1, mn2 = 0;
  88. mn1 = col[1];
  89. Fo(i, 1, n+1){
  90. if(minof[col[i]] <= minof[mn1])
  91. mn1 = col[i];
  92. }
  93. Fo(i, 1, n+1){
  94. if(col[i] != mn1) mn2 = col[i];
  95. }
  96. Fo(i, 1, n+1){
  97. if(col[i]!=mn1 and minof[col[i]] <= minof[mn2])
  98. mn2 = col[i];
  99. }
  100. int pos1, pos2 = -1;
  101. Fo(i, 1, n+1){
  102. if(col[i] == mn1 and w[i] == minof[mn1]) pos1 = i;
  103. if(col[i] == mn2 and w[i] == minof[mn2]) pos2 = i;
  104. }
  105. //mn1, mn2 colors ki hai minimum
  106. Fo(i, 1, n+1){
  107. if(col[i] != mn1){
  108. if(w[i]+minof[mn1] <= y) unite(i, pos1);
  109. }
  110. else if (pos2!=-1){
  111. if(w[i]+minof[mn2] <= y) unite(i, pos2);
  112. }
  113. }
  114. Fo(i, 1, n+1){
  115. tot[rep(i)]++;
  116. cnt[rep(i)][col[i]]++;
  117. }
  118. ll ans = 1, cur = 0;
  119. Fo(i, 1, n+1){
  120. if(i == rep(i)){
  121. ans *= fac[tot[i]];
  122. ans %= mod;
  123. for(auto it: cnt[i]){
  124. ans *= inv[it.S];
  125. ans %= mod;
  126. }
  127. }
  128. }
  129. cout << ans << endl;
  130.  
  131. return 0;
  132. }
  133.  
  134. int mpow(int base, int exp) {
  135. base %= mod;
  136. int result = 1;
  137. while (exp > 0) {
  138. if (exp & 1) result = ((ll)result * base) % mod;
  139. base = ((ll)base * base) % mod;
  140. exp >>= 1;
  141. }
  142. return result;
  143. }
Success #stdin #stdout 0.05s 49216KB
stdin
21 77 68
16 73
16 99
19 66
2 87
2 16
7 17
10 36
10 68
2 38
10 74
13 55
21 21
3 7
12 41
13 88
18 6
2 12
13 87
1 9
2 27
13 15
stdout
129729600