fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll=long long;
  4.  
  5. bool isValid(ll mid,vector<ll>&nums,ll pos){
  6. //count the number of subarrays with sum mid
  7. ll count=0;
  8. ll st=0;
  9. ll n=nums.size();
  10. ll sum=0;
  11. for(int end=0;end<n;end++){
  12. sum+=nums[end];
  13.  
  14. while(sum>mid){
  15. sum-=nums[st];
  16. st++;
  17. }
  18.  
  19. count+=(end-st+1);
  20. }
  21. return count>=pos;
  22. }
  23.  
  24. pair<ll,ll>countAndTotal(ll k,vector<ll>&nums){
  25. ll count=0;
  26. ll total=0;
  27.  
  28. ll n=nums.size();
  29. vector<ll>pref(n+1,0);
  30. vector<ll>pp(n+1,0);//prefix of prefix it is used to calculate all teh left sums at O(1)
  31. //insted of the standard for loop
  32.  
  33. for(int i=0;i<n;i++){
  34. pref[i+1]=pref[i]+nums[i];
  35. }
  36.  
  37. //pp
  38. for(int i=0;i<=n;i++){
  39. pp[i]=((i>0)?pp[i-1]:0)+pref[i];
  40. }
  41.  
  42. ll st=0;
  43. ll sum=0;
  44. for(int end=0;end<n;end++){
  45. sum+=nums[end];
  46.  
  47. while(sum>k){
  48. sum-=nums[st];
  49. st++;
  50. }
  51.  
  52. ll len=end-st+1;
  53.  
  54. count+=len;
  55.  
  56. ll left=(st>0)?pp[st-1]:0;
  57. total+=(pref[end+1]*len)-(pp[end]-left);
  58. }
  59. return {count,total};
  60.  
  61. }
  62.  
  63.  
  64. ll solve(int pos,vector<ll>&nums){
  65. //first we have to find out what is teh element that comes in that pos
  66. //after that we have to find out the sum until that element
  67. int n=nums.size();
  68. ll st=0;
  69. ll end=accumulate(nums.begin(),nums.end(),0LL);
  70. ll ans=-1;
  71. while(st<=end){
  72. ll mid=st+(end-st)/2;
  73.  
  74. if(isValid(mid,nums,pos)){
  75. ans=mid;
  76. end=mid-1;
  77. }else{
  78. st=mid+1;
  79. }
  80. }
  81. pair<ll,ll>pr=countAndTotal(ans,nums);
  82. ll total=pr.second;
  83. ll count=pr.first;
  84. //because total is the all the subarrays sum and count is total subarrays
  85. //and pos is the cur pos we want so we are subtracting the extra eleemnts
  86. //by the positions sum in it
  87. return total-((count-pos)*ans);
  88. }
  89.  
  90. int main() {
  91.  
  92. int n;
  93. cin>>n;
  94. vector<ll>nums(n);
  95. for(int i=0;i<n;i++){
  96. cin>>nums[i];
  97. }
  98.  
  99. //given queries we have to find the sum of them in rnage so sum(l-r)
  100. //so pref[r]-pref[l-1];
  101. ll stPos;
  102. ll endPos;
  103. cin>>stPos>>endPos;
  104.  
  105. cout<<solve(endPos,nums)-solve(stPos-1,nums)<<endl;
  106. return 0;
  107.  
  108. }
Success #stdin #stdout 0s 5312KB
stdin
3 1 2 3 3 4
stdout
6