fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fastio ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
  4. #define ll long long
  5. #define int ll
  6. const int mxn = (int)2e5+7;
  7. const int MOD = 998244353;
  8. #define isON(n, k) (((n) >> (k)) & 1)
  9.  
  10. void GETAC(){
  11.  
  12.     int n, k, q;
  13.     cin >> n >> k;
  14.     vector<int> a(n);
  15.     for (int& i : a) cin >> i;
  16.  
  17.     cin >> q;
  18.     vector<int> pre(n+1); // preprocess subarray sums
  19.     for (int i(1); i <= n; ++i)
  20.         pre[i] = pre[i-1] + a[i-1];
  21.  
  22.     while (q--)
  23.     {
  24.  
  25.         int L, R, ans(0);
  26.         cin >> L >> R;
  27.         /*
  28.          *  for (int l(L); l <= R; ++l) 
  29.                 for (int r(l); r <= R; ++r) 
  30.                     if (pre[r] - pre[l-1] == k) 
  31.                         ++ans;
  32.          * 
  33.          */
  34.         map<int, int> f; // key : sum, value : frequency sum appears
  35.         f[pre[L-1]] = 1;
  36.         for (int r(L); r <= R; ++r) { // right ends
  37.             if (pre[r] - k >= 0)
  38.                 ans += f[pre[r] - k]; // left ends satisfy pre[r] - pre[l-1] == k
  39.             ++f[pre[r]];
  40.         }
  41.         cout << ans << '\n';
  42.     }
  43. }
  44.  
  45. signed main()
  46. {
  47.     fastio
  48.     int t(1); cin >> t;
  49.     while(t--) GETAC(), cout << '\n';
  50. }
  51.  
  52.  
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
1
10 5
2 3 0 0 0 2 3 1 1 0
7
1 2
1 3
1 7
1 10
2 7
2 6
3 8
stdout
copy 
1
2
9
11
5
1
4
https://ideone.com/KzPiis
language:
C++ (gcc 8.3)
created:
1 year 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!