fork(9) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8.  
  9. typedef pair<int, int> pii;
  10.  
  11. typedef tree<
  12. pii,
  13. null_type,
  14. less<pii>,
  15. rb_tree_tag,
  16. tree_order_statistics_node_update>
  17. ordered_tree;
  18.  
  19.  
  20. int main(){
  21. int N, M;
  22. cin >> N >> M;
  23. vector<int> a;
  24. a.push_back(0);
  25. ordered_tree H;
  26. for (int i=0;i<N;i++){
  27.     int x;
  28.     cin >> x;
  29.     a.push_back(x);
  30. }
  31. int p = 0;
  32. int s = 0;
  33. for (auto i : a){
  34.     s+=i;
  35.     H.insert(pii(s,p++));
  36. }
  37. int res = 0;
  38. s = 0;
  39. for (auto i : a){
  40.     s += i;
  41.     auto q = lower_bound(H.begin(), H.end(), pii(s - M,-1));
  42.     res += H.order_of_key(*q);
  43. }
  44. cout << res<<endl;
  45. }
  46.  
Success #stdin #stdout 1.9s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/WuJMjz
language:
C++14 (gcc 8.3)
created:
7 years 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!