fork download
copy 
  1. // http://stackoverflow.com/questions/38781428/how-do-you-solve-the-given-scenario-with-given-memory-constraints/38785766#38785766
  2. // 
  3.  
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11.  
  12. ll calc_in_range(ll pivot, const vector<ll> &p){
  13. 	int n = p.size();
  14. 	ll total = 0;
  15. 	for(int i = 0; i < n; i++){
  16. 		if (i == 0) total += static_cast<ll>(upper_bound(p.begin(), p.end(), pivot)-p.begin());
  17. 		else total += static_cast<ll>(upper_bound(p.begin() + i, p.end(), pivot + p[i-1]) - p.begin() - i);
  18. 	}
  19. 	return total;
  20. }
  21.  
  22.  
  23. ll calc_sum(ll pivot, const vector<ll> &p, const vector<ll> &pp){
  24. 	int n = p.size();
  25. 	ll sum = 0;
  26. 	int index;
  27. 	for(int i = 0; i < n; i++){
  28. 		if (i == 0) index = static_cast<ll>(upper_bound(p.begin(), p.end(), pivot)-p.begin());
  29. 		else index = static_cast<ll>(upper_bound(p.begin() + i, p.end(), pivot + p[i-1]) - p.begin() - i);
  30. 		index--;
  31. 		if (index == -1) continue;
  32. 		if (i == 0) sum += pp[index];
  33. 		else {
  34. 			ll shift = p[i-1];
  35. 			sum += pp[index+i]-pp[i-1]-shift*(index+1);
  36. 		}
  37. 	}
  38. 	return sum;
  39. }
  40.  
  41.  
  42. ll find_x(int a, const vector<ll> &p, const vector<ll> &pp){
  43. 	if (a == 0) return 0;
  44. 	ll answer = 0;
  45. 	ll l = 1;
  46. 	ll r = p[p.size()-1];
  47. 	int offset;
  48. 	while(l < r){
  49. 		ll mid = (l+r)/2;
  50. 		int cand = calc_in_range(mid, p);
  51. 		if (cand <= a){
  52. 			l = mid + 1;
  53. 			offset = a-cand;
  54. 		}
  55. 		else {
  56. 			r = mid;
  57. 			offset = 0;
  58. 		}
  59. 	}
  60. 	ll pivot = l;
  61. 	answer += offset * pivot;
  62. 	pivot--;
  63. 	answer += calc_sum(pivot, p, pp);
  64. 	return answer;
  65. }
  66.  
  67. int main(int argc, char const *argv[])
  68. {
  69. 	int n, q;
  70. 	cin >> n >> q;
  71. 	vector<int> x(n);
  72. 	vector<ll> p(n); //prefix array
  73. 	vector<ll> pp(n); //prefix sum of prefix array
  74. 	ll sum = 0;
  75. 	for(int i = 0; i < n; i++){
  76. 		cin >> x[i];
  77. 		sum += x[i];
  78. 		p[i] = sum;
  79. 		if (i == 0) pp[i] = p[i];
  80. 		else pp[i] = pp[i-1] + p[i];
  81. 	}
  82. 	for(int i = 0; i < q; i++){
  83. 		int a, b;
  84. 		cin >> a >> b;
  85. 		ll resa = find_x(a-1, p, pp);
  86. 		ll resb = find_x(b, p, pp);
  87. 		cout << (resb - resa) << endl;
  88. 	}
  89. 	return 0;
  90. }
  91.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
3 3
4 9 1
1 6
2 4
3 3
stdout
copy 
51
23
9
https://ideone.com/2JTw0X
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!