fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. ll a[400001];
  25. const int LG = 60;
  26. ii st[LG][200001];
  27. int n;
  28.  
  29. ll getl(int l, int r)
  30. {
  31. 	if(l > r) return 0;
  32. 	if(l == 0) return a[r];
  33. 	return (a[r] - a[l-1]);
  34. }
  35.  
  36. const ll INF = ll(2e18);
  37.  
  38. int dist(int l, int r)
  39. {
  40. 	if(l <= r) return r - l;
  41. 	r += n;
  42. 	return r - l;
  43. }
  44.  
  45. ll x, y;
  46.  
  47. void computest()
  48. {
  49. 	for(int i = 0; i < n; i++)
  50. 	{
  51. 		ll cycles = x/a[n-1];
  52. 		ll rem = x%a[n-1];
  53. 		if(rem<getl(i,i))
  54. 		{
  55. 			st[0][i] = mp(cycles, i);
  56. 			//cerr<<cycles<<' '<<i<<'\n';
  57. 			continue;
  58. 		}
  59. 		int lo = i + 1; int hi = n + i - 1;
  60. 		int ans = i;
  61. 		while(lo<=hi)
  62. 		{
  63. 			int mid = (lo+hi)>>1;
  64. 			if(getl(i, mid - 1) <= rem)
  65. 			{
  66. 				ans = mid;
  67. 				lo = mid + 1;
  68. 			}
  69. 			else
  70. 			{
  71. 				hi = mid - 1;
  72. 			}
  73. 		}
  74. 		if(ans >= n) ans -= n;
  75. 		st[0][i] = mp(cycles, ans);
  76. 	}
  77. 	for(int i = 1; i < LG; i++)
  78. 	{
  79. 		for(int j = 0; j < n; j++)
  80. 		{
  81. 			int p2 = st[i-1][j].se;
  82. 			//catch a bug here if possible
  83. 			st[i][j] = mp(st[i-1][j].fi+st[i-1][p2].fi, st[i-1][p2].se);
  84. 			//careful about overflow
  85. 			//j -> p2 -> st[i-1][p2].se
  86. 			int totd = dist(j, p2) + dist(p2, st[i-1][p2].se);
  87. 			if(totd >= n)
  88. 			{
  89. 				st[i][j].fi++;
  90. 			}
  91. 			if(st[i][j].fi > INF) st[i][j].fi = INF;
  92. 		}
  93. 	}
  94. }
  95.  
  96.  
  97. ll test(ll mid)
  98. {
  99. 	ii res = mp(0, 0);
  100. 	ll totdist = 0;
  101. 	for(int i = 0; i < LG; i++)
  102. 	{
  103. 		if(mid&(1LL<<i))
  104. 		{
  105. 			ii tmp = st[i][res.se];
  106. 			//res.se -> tmp.se
  107. 			int l = res.se; int r = tmp.se;
  108. 			if(l>r) r += n;
  109. 			totdist += getl(l,r-1);
  110. 			res.se = tmp.se;
  111. 			res.fi += tmp.fi;
  112. 			if(res.fi>INF) res.fi=INF;
  113. 			if(totdist>INF) totdist = INF;
  114. 		}
  115. 	}
  116. 	ll totd = 0;
  117. 	if(res.fi>(INF/a[n-1])) return INF;
  118. 	totd = res.fi*a[n-1];
  119. 	totd += totdist;
  120. 	return totd;
  121. }
  122.  
  123. int main()
  124. {
  125. 	ios_base::sync_with_stdio(0); cin.tie(0);
  126. 	cin >> n;
  127. 	for(int i = 0; i < n; i++)
  128. 	{
  129. 		cin >> a[i];
  130. 		a[n+i] = a[i];
  131. 	}
  132. 	cin >> x >> y;
  133. 	for(int i = 1; i < 2*n; i++)
  134. 	{
  135. 		a[i] += a[i-1];
  136. 	}
  137. 	computest();
  138. 	ll lo = 1; ll hi = ll(1e18);
  139. 	ll ans = -1; //covered fail case
  140. 	while(lo <= hi)
  141. 	{
  142. 		ll mid = (lo+hi)/2;
  143. 		if(test(mid) >= y)
  144. 		{
  145. 			ans = mid;
  146. 			hi = mid - 1;
  147. 		}
  148. 		else
  149. 		{
  150. 			lo = mid + 1;
  151. 		}
  152. 	}
  153. 	cout << ans << '\n';
  154. }
  155.  
Runtime error #stdin #stdout 0s 194112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Dqv0Ly
language:
C++14 (gcc 8.3)
created:
7 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!