fork(5) download
copy 
  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
comments (?)
stdin
copy 
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
copy 
129729600
https://ideone.com/OPD2Fr
atcoder, math, combinatorics, dsu
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!