fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Count number of subarrays having sum <= x
  5. long long p(long long b[], int n, long long x)
  6. {
  7.     long long sum = 0;
  8.     long long c = 0;
  9.  
  10.     int j = 0;
  11.  
  12.     for(int i = 0; i < n; i++)
  13.     {
  14.         // Add current element
  15.         sum += b[i];
  16.  
  17.         // Remove elements from left if sum becomes > x
  18.         while(sum > x && j <= i)
  19.         {
  20.             sum -= b[j];
  21.             j++;
  22.         }
  23.  
  24.         // Number of valid subarrays ending at i
  25.         c += (i - j + 1);
  26.     }
  27.  
  28.     return c;
  29. }
  30.  
  31. // Find sum of all subarrays having sum <= x
  32. long long f(long long b[], int n, long long x)
  33. {
  34.     long long sum = 0;
  35.     long long t = 0;
  36.  
  37.     int j = 0;
  38.  
  39.     for(int i = 0; i < n; i++)
  40.     {
  41.         // Add current element
  42.         sum += b[i];
  43.  
  44.         // Keep the subarray sum <= x
  45.         while(sum > x && j <= i)
  46.         {
  47.             sum -= b[j];
  48.             j++;
  49.         }
  50.  
  51.         // Add the current valid sum
  52.         t += sum;
  53.     }
  54.  
  55.     return t;
  56. }
  57.  
  58. int main()
  59. {
  60.     int n;
  61.     cin>>n;
  62.  
  63.     // G = required position in sorted subarray sums
  64.     long long G;
  65.     cin>>G;
  66.  
  67.     long long b[n];
  68.  
  69.     // low = smallest possible subarray sum
  70.     // high = largest possible subarray sum
  71.     long long low = 1e18;
  72.     long long high = 0;
  73.  
  74.     for(int i=0; i<n; i++)
  75.     {
  76.         cin>>b[i];
  77.  
  78.         if(b[i] < low)
  79.         {
  80.             low = b[i];
  81.         }
  82.  
  83.         high += b[i];
  84.     }
  85.  
  86.     // Binary search to find the first number
  87.     // where number of subarrays with sum <= number is >= G
  88.  
  89.     long long l = low;
  90.     long long r = high;
  91.  
  92.     while(l < r)
  93.     {
  94.         long long mid = l + (r-l)/2;
  95.  
  96.         // Count subarrays having sum <= mid
  97.         long long c = p(b,n,mid);
  98.  
  99.         if(c >= G)
  100.         {
  101.             // Answer can be mid or smaller
  102.             r = mid;
  103.         }
  104.         else
  105.         {
  106.             // Need a bigger value
  107.             l = mid + 1;
  108.         }
  109.     }
  110.  
  111.     // First value where count >= G
  112.     long long i = l;
  113.  
  114.     // Count subarrays having sum <= i
  115.     long long c = p(b,n,i);
  116.  
  117.     // Sum of all subarrays having sum <= i
  118.     long long t = f(b,n,i);
  119.  
  120.     // Remove extra subarrays
  121.     // so that exactly G smallest subarray sums remain
  122.     t = t - i*(c-G);
  123.  
  124.     cout<<t<<endl;
  125.  
  126.  
  127.     // Q queries
  128.     // Find sum from index Li to Ri
  129.     // Both indices are inclusive
  130.  
  131.     int Q;
  132.     cin>>Q;
  133.  
  134.     // Prefix sum array
  135.     long long prefix[n+1];
  136.  
  137.     prefix[0] = 0;
  138.  
  139.     for(int i=0; i<n; i++)
  140.     {
  141.         prefix[i+1] = prefix[i] + b[i];
  142.     }
  143.  
  144.     // Answer each query in O(1)
  145.     for(int q=1; q<=Q; q++)
  146.     {
  147.         int Li, Ri;
  148.         cin>>Li>>Ri;
  149.  
  150.         // Sum from Li to Ri
  151.         long long ans = prefix[Ri+1] - prefix[Li];
  152.  
  153.         cout<<ans<<endl;
  154.     }
  155.  
  156.     return 0;
  157. }
  158.  
  159.  
  160.  
  161. /*
  162. Input
  163.  
  164. 3
  165. 4
  166. 1 2 3
  167. 3
  168. 0 1
  169. 1 2
  170. 0 2
  171.  
  172. Explanation:
  173.  
  174. Array:
  175.  
  176. [1, 2, 3]
  177.  
  178. All subarray sums:
  179.  
  180. 1
  181. 2
  182. 3
  183. 3
  184. 5
  185. 6
  186.  
  187. G = 4, so the 4th smallest subarray sum is 3.
  188.  
  189. For queries:
  190.  
  191. 0 1 → 1 + 2 = 3
  192. 1 2 → 2 + 3 = 5
  193. 0 2 → 1 + 2 + 3 = 6
  194.  
  195. Output
  196.  
  197. 9
  198. 3
  199. 5
  200. 6
  201. */
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8064262447366491392
https://ideone.com/Uwwyoa
language:
C++ (gcc 8.3)
created:
34 days 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!