fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. const long double PI = 3.14159265359;
  7.  
  8. template <class T>
  9. struct BIT
  10. {
  11.     // 1-indexed
  12.     int n;
  13.     vector<T> t;
  14.  
  15.     BIT()
  16.     {
  17.     }
  18.  
  19.     BIT(int _n)
  20.     {
  21.         n = _n;
  22.         t.assign(n + 1, 0);
  23.     }
  24.  
  25.     T query(int i)
  26.     {
  27.         T ans = 0;
  28.         for (; i >= 1; i -= (i & -i))
  29.             ans += t[i];
  30.         return ans;
  31.     }
  32.  
  33.     void upd(int i, T val)
  34.     {
  35.         if (i <= 0)
  36.             return;
  37.         for (; i <= n; i += (i & -i))
  38.             t[i] += val;
  39.     }
  40.     void upd(int l, int r, T val)
  41.     {
  42.         upd(l, val);
  43.         upd(r + 1, -val);
  44.     }
  45.     T query(int l, int r)
  46.     {
  47.         return query(r) - query(l - 1);
  48.     }
  49. };
  50.  
  51. void solve()
  52. {
  53.     int n, l, r;
  54.     cin >> n >> l >> r;
  55.     vector<int> arr(n);
  56.     for (auto &val : arr)
  57.         cin >> val;
  58.  
  59.     vector<int> pref(n + 1, 0);
  60.     for (int i = 1; i <= n; i++)
  61.         pref[i] = pref[i - 1] + arr[i - 1];
  62.  
  63.     BIT<int> bit(n + 5);
  64.     vector<int> vals = pref;
  65.  
  66.     sort(vals.begin(), vals.end());
  67.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  68.  
  69.     int first = lower_bound(vals.begin(), vals.end(), pref[0]) - vals.begin();
  70.     bit.upd(first + 1, 1);
  71.  
  72.     int ans = 0;
  73.     for (int i = 1; i <= n; i++)
  74.     {
  75.         int low = pref[i] - r;
  76.         int high = pref[i] - l;
  77.  
  78.         int low_cond = lower_bound(vals.begin(), vals.end(), low) - vals.begin();
  79.         int high_cond = upper_bound(vals.begin(), vals.end(), high) - vals.begin();
  80.  
  81.         ans += (bit.query(high_cond) - bit.query(low_cond));
  82.  
  83.         int new_pref_cond = lower_bound(vals.begin(), vals.end(), pref[i]) - vals.begin();
  84.         bit.upd(new_pref_cond + 1, 1);
  85.     }
  86.     cout << ans << '\n';
  87. }
  88.  
  89. signed main(void)
  90. {
  91.     ios_base::sync_with_stdio(0);
  92.     cin.tie(0);
  93.     cout.tie(0);
  94.     if (fopen("input.txt", "r"))
  95.     {
  96.         freopen("input.txt", "r", stdin);
  97.         freopen("output.txt", "w", stdout);
  98.     }
  99.     int t = 1;
  100.     // cin >> t;
  101.     while (t--)
  102.     {
  103.         solve();
  104.     }
  105.     return 0;
  106. }
Success #stdin #stdout 0.01s 5348KB
comments (?)
stdin
copy 
5 -2 3
3 -1 -4 -1 5
stdout
copy 
8
https://ideone.com/8lp4gG
language:
C++ (gcc 8.3)
created:
7 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!