fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. // Count number of subarrays of `v` whose sum is exactly S
  6. ll count_subarrays_with_sum(const vector<ll>& v, ll S) {
  7.     unordered_map<ll,int> cnt;
  8.     cnt.reserve(v.size()*2);
  9.     cnt[0] = 1;
  10.     ll pref = 0, ans = 0;
  11.     for (ll x : v) {
  12.         pref += x;
  13.         auto it = cnt.find(pref - S);
  14.         if (it != cnt.end()) ans += it->second;
  15.         cnt[pref]++;
  16.     }
  17.     return ans;
  18. }
  19.  
  20. int main(){
  21.     ios::sync_with_stdio(false);
  22.     cin.tie(nullptr);
  23.  
  24.     int T;
  25.     cin >> T;
  26.     while (T--) {
  27.         int n;
  28.         ll S, X;
  29.         cin >> n >> S >> X;
  30.         vector<ll> a(n);
  31.         for (int i = 0; i < n; i++) {
  32.             cin >> a[i];
  33.         }
  34.  
  35.         ll answer = 0;
  36.         int i = 0;
  37.         while (i < n) {
  38.             // skip any element > X, they cannot belong to a valid segment
  39.             if (a[i] > X) {
  40.                 i++;
  41.                 continue;
  42.             }
  43.  
  44.             // gather the maximal block [i..j) in which all a[k] <= X
  45.             int j = i;
  46.             vector<ll> block;
  47.             while (j < n && a[j] <= X) {
  48.                 block.push_back(a[j]);
  49.                 j++;
  50.             }
  51.  
  52.             // 1) Count all subarrays in this block whose sum == S
  53.             ll total_in_block = count_subarrays_with_sum(block, S);
  54.  
  55.             // 2) Subtract those that NEVER hit X (i.e., all elements < X)
  56.             //    split `block` on positions where block[k] == X
  57.             ll noX_count = 0;
  58.             int k = 0, B = block.size();
  59.             while (k < B) {
  60.                 if (block[k] == X) {
  61.                     k++;
  62.                     continue;
  63.                 }
  64.                 int l = k;
  65.                 vector<ll> sub;
  66.                 while (l < B && block[l] != X) {
  67.                     sub.push_back(block[l]);
  68.                     l++;
  69.                 }
  70.                 noX_count += count_subarrays_with_sum(sub, S);
  71.                 k = l;
  72.             }
  73.  
  74.             answer += (total_in_block - noX_count);
  75.             i = j;  // move past this block
  76.         }
  77.  
  78.         cout << answer << "\n";
  79.     }
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
9
1 0 0
0
1 -2 -1
-2
3 -1 -1
-1 1 -1
6 -3 -2
-1 -1 -1 -2 -1 -1
8 3 2
2 2 -1 -2 3 -1 2 2
9 6 3
1 2 3 1 2 3 1 2 3
13 7 3
0 -1 3 3 3 -2 1 2 2 3 -1 0 3
2 -2 -1
-2 -1
2 -2 -1
-1 -2
stdout
copy 
1
0
2
0
2
7
8
0
0
https://ideone.com/TAwF1E
language:
C++ (gcc 8.3)
created:
9 hours 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!