fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const int M = 1e6 + 239;
  8. const int MS = (1 << 16);
  9. const int L = 31;
  10. const int two = 2;
  11.  
  12. int n, a[M], k, p, id[M], s[two][M];
  13. ll w[two][L];
  14. int cur, pos[M];
  15.  
  16. inline bool cmp(int i, int j)
  17. {
  18. 	return (a[i] < a[j]);
  19. }
  20.  
  21. inline ll merge_our(int c, int x, int y, int z)
  22. {
  23. 	int p1 = x;
  24. 	int p2 = y;
  25. 	int dl = y;
  26. 	int pos = x - 1;
  27. 	ll ans = 0;
  28. 	while (p1 != y || p2 != z)
  29. 	{
  30. 		pos++;
  31. 		if (p1 != y && (p2 == z || s[c][p1] < s[c][p2]))
  32. 		{
  33. 		        ans += (ll)(p2 - dl);
  34. 			s[1 - c][pos] = s[c][p1];
  35. 			p1++;
  36. 		}
  37. 		else
  38. 		{
  39. 			s[1 - c][pos] = s[c][p2];
  40. 			p2++;
  41. 		}	
  42. 	}
  43. 	return ans;	
  44. }
  45.  
  46. inline void init()
  47. {        
  48. 	for (int i = 0; i < n; i++)
  49. 		s[0][i] = id[i];                               
  50. 	for (int t = 0; t < k; t++)
  51. 	{
  52. 		int ms = (1 << k) - (1 << (t + 1));
  53. 		cur = 0;
  54. 		for (int x = 1; x < n; x++)
  55. 		{
  56. 			if ((a[id[x - 1]] & ms) == (a[id[x]] & ms)) continue;
  57. 			pos[cur] = x;
  58. 			cur++;
  59. 		}
  60. 		pos[cur] = n;
  61. 		cur++;
  62. 		w[0][t] = 0;
  63. 		w[1][t] = 0;
  64. 		int ls = 0;
  65. 		for (int i = 0; i < cur; i++)
  66. 		{
  67. 			int u = ls;
  68. 			for (int x = ls; x < pos[i]; x++)
  69. 				if (((a[id[x]] >> t) & 1) == 0)
  70. 					u++;
  71. 			ll nw = merge_our(t & 1, ls, u, pos[i]);
  72. 			w[0][t] += nw;
  73. 			w[1][t] += (ll)(pos[i] - u) * (ll)(u - ls) - nw;
  74. 			ls = pos[i];			
  75. 		}		
  76. 	}
  77. }
  78.  
  79. pair<ll, int> ar[two][MS];
  80. int as, bs, eq[MS];
  81.  
  82. ll getkol(ll h)
  83. {
  84. 	ll ans = 0;
  85. 	int r = 0;
  86. 	while (r < (1 << bs))
  87. 	{
  88. 		if (ar[0][0].first + ar[1][r].first >= h) break;
  89. 		r++;
  90. 	}
  91. 	for (int i = 0; i < (1 << as); i++)
  92. 	{
  93. 		ans += (ll)r;
  94. 		if (i == (1 << as) - 1) continue;
  95. 		while (r > 0)
  96. 		{
  97. 			if (ar[0][i + 1].first + ar[1][r - 1].first < h) break;
  98. 			r--;
  99. 		}
  100. 	}
  101. 	return ans;
  102. }
  103.  
  104. int gett(ll h, int p)
  105. {
  106. 	for (int i = 0; i < (1 << bs); i++)
  107. 	{
  108. 		if (i == 0 || ar[1][i].first != ar[1][i - 1].first)
  109. 			eq[i] = i;
  110. 		else
  111. 			eq[i] = eq[i - 1];
  112. 	}
  113. 	int r = 0;
  114. 	while (r < (1 << bs))
  115. 	{
  116. 		if (ar[0][0].first + ar[1][r].first > h) break;
  117. 		r++;
  118. 	}	
  119. 	vector<pair<int, int> > ps;
  120. 	for (int i = 0; i < (1 << as); i++)
  121. 	{
  122. 		if (r > 0 && ar[0][i].first + ar[1][r - 1].first == h) ps.push_back(make_pair(ar[0][i].second, r - eq[r - 1]));
  123. 		if (i == (1 << as) - 1) continue;
  124. 		while (r > 0)
  125. 		{
  126. 			if (ar[0][i + 1].first + ar[1][r - 1].first <= h) break;
  127. 			r--;
  128. 		}
  129. 	}
  130. 	sort(ps.begin(), ps.end());
  131. 	for (pair<int, int> t : ps)
  132. 	{                                                         
  133. 		if (t.second > p)
  134. 		{
  135. 			ll W = 0;
  136. 			for (int i = 0; i < (1 << as); i++)
  137. 				if (ar[0][i].second == t.first)
  138. 				{
  139. 					W = ar[0][i].first;
  140. 					break;
  141. 				}
  142. 			vector<int> st;
  143. 			for (int i = 0; i < (1 << bs); i++)
  144. 				if (ar[1][i].first == h - W)
  145. 					st.push_back(ar[1][i].second);
  146. 			sort(st.begin(), st.end());
  147. 			return ((t.first << bs) | st[p]);	
  148. 		}
  149. 		else
  150. 			p -= t.second;
  151. 	}
  152. }
  153.  
  154. void solve()
  155. {
  156. 	cin >> n >> k >> p;
  157. 	p--;
  158. 	for (int i = 0; i < n; i++)
  159. 		cin >> a[i];
  160. 	for (int i = 0; i < n; i++)
  161. 		id[i] = i;
  162. 	sort(id, id + n, cmp);          
  163. 	init();                       
  164. 	as = (k / 2);
  165. 	bs = k - as;
  166. 	for (int ms = 0; ms < (1 << as); ms++)
  167. 	{
  168. 		ll f = 0;
  169. 		for (int x = 0; x < as; x++)
  170. 			f += w[(ms >> x) & 1][bs + x];
  171. 		ar[0][ms] = make_pair(f, ms);
  172. 	}
  173. 	for (int ms = 0; ms < (1 << bs); ms++)
  174. 	{
  175. 		ll f = 0;
  176. 		for (int x = 0; x < bs; x++)
  177. 			f += w[(ms >> x) & 1][x];
  178. 		ar[1][ms] = make_pair(f, ms);
  179. 	}   
  180. 	sort(ar[0], ar[0] + (1 << as));
  181. 	sort(ar[1], ar[1] + (1 << bs));
  182. 	ll l = 0;
  183. 	ll r = (((ll)n * (ll)(n + 1)) / 2LL) + 1;
  184. 	while (r - l > 1)
  185. 	{
  186. 		ll h = (l + r) >> 1;
  187. 		if (getkol(h) <= p)
  188. 			l = h;
  189. 		else
  190. 			r = h;
  191. 	}                    
  192. 	p -= getkol(l);
  193. 	cout << gett(l, p) << "\n";
  194. }
  195.  
  196. int main()
  197. {
  198. 	ios::sync_with_stdio(0);
  199. 	int T;
  200. 	cin >> T;
  201. 	for (int z = 0; z < T; z++)
  202. 		solve();
  203. 	return 0;
  204. }
Success #stdin #stdout 0s 4344KB
comments (?)
stdin
copy 
3
4 3 5
2 0 3 7
2 2 1
2 0
6 3 2
7 5 3 4 1 2
stdout
copy 
4
2
5
https://ideone.com/QppabP
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!