Advertisement
goshansmails

Untitled

Apr 21st, 2020
272
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <set>
  5. #include <unordered_set>
  6. #include <map>
  7. #include <unordered_map>
  8. #include <algorithm>
  9. #include <cmath>
  10.  
  11. using namespace std;
  12.  
  13. typedef long long ll;
  14.  
  15. int main() {
  16.     ios_base::sync_with_stdio(0);
  17.     cin.tie(0);
  18.  
  19.     ll n, x;
  20.     cin >> n >> x;
  21.  
  22.     vector<ll> a(n + 1);
  23.     vector<ll> part_sum(n + 1);
  24.     map<ll, vector<ll>> indices_for_part_sum;
  25.  
  26.     part_sum[0] = 0;
  27.     indices_for_part_sum[0].push_back(0);
  28.     for (ll i = 1; i <= n; ++i) {
  29.         cin >> a[i];
  30.         part_sum[i] = part_sum[i - 1] + a[i];
  31.         indices_for_part_sum[part_sum[i]].push_back(i);
  32.     }
  33.  
  34.     ll res = 0;
  35.     for (const auto& [ps, indices] : indices_for_part_sum) {
  36.         ll required_value = ps - x;
  37.         if (indices_for_part_sum.count(required_value) != 0) {
  38.             for (const ll& index : indices) {
  39.                 auto tmp = lower_bound(
  40.                         indices_for_part_sum[required_value].begin(),
  41.                         indices_for_part_sum[required_value].end(),
  42.                         index
  43.                 );
  44.                 res += tmp - indices_for_part_sum[required_value].begin();
  45.             }
  46.         }
  47.     }
  48.  
  49.     cout << res << endl;
  50.  
  51.     return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement