fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define VuDucNam ios_base::sync_with_stdio(false);
  3. #define Lop9a6 cin.tie(NULL);
  4. #define THCSPhamVanDong cout.tie(NULL);
  5. #define ll long long
  6. #define el cout << '\n'
  7. #define sz(a) (ll)a.size()
  8. #define all(a) a.begin(), a.end()
  9. #define file(name)                         \
  10.     if (fopen(name ".inp", "r"))           \
  11.     {                                      \
  12.         freopen(name ".inp", "r", stdin);  \
  13.         freopen(name ".out", "w", stdout); \
  14.     }
  15. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  16. #define RUNTIME cerr << "\nRuntime: " << TIME << "s.\n"
  17.  
  18. using namespace std;
  19.  
  20. const int N5 = 1e5 + 5;
  21.  
  22. int n;
  23. ll s, pre[N5], cnt;
  24. map<ll, int> freq; // Lưu tần suất các giá trị pre[j]
  25.  
  26. void solve()
  27. {
  28.     cin >> n >> s;
  29.  
  30.     for (int i = 1; i <= n; ++i)
  31.     {
  32.         ll x;
  33.         cin >> x;
  34.         pre[i] = pre[i - 1] + x;
  35.     }
  36.  
  37.     // Thêm pre[0] = 0 vào map
  38.     freq[0]++;
  39.  
  40.     for (int i = 1; i <= n; ++i)
  41.     {
  42.         // Tìm số phần tử nhỏ hơn pre[i] - s
  43.         auto it1 = freq.lower_bound(pre[i] - s);
  44.         if (it1 != freq.begin())
  45.         {
  46.             cnt += distance(freq.begin(), it1);
  47.         }
  48.  
  49.         // Tìm số phần tử lớn hơn pre[i] + s
  50.         auto it2 = freq.upper_bound(pre[i] + s);
  51.         if (it2 != freq.end())
  52.         {
  53.             cnt += distance(it2, freq.end());
  54.         }
  55.  
  56.         // Thêm pre[i] vào map
  57.         freq[pre[i]]++;
  58.     }
  59.  
  60.     cout << cnt;
  61.     el;
  62. }
  63.  
  64. int main()
  65. {
  66.     VuDucNam Lop9a6 THCSPhamVanDong
  67.     file("code");
  68.     solve();
  69.     RUNTIME;
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout #stderr 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Runtime: 0.006082s.
https://ideone.com/bQcpl7
language:
C++ (gcc 8.3)
created:
31 days 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!