fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>  
  3. #include <ext/pb_ds/tree_policy.hpp> 
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds; 
  7. #define ll long long
  8.  
  9.  
  10. typedef tree<pair<ll,ll>, null_type,  
  11.         less<pair<ll,ll>>, rb_tree_tag, 
  12.         tree_order_statistics_node_update> 
  13.         ordered_set_pair; 
  14.  
  15. const int MAXN = 1e5 + 11;
  16. int n;
  17. ll a[MAXN], k;
  18. ordered_set_pair f;
  19.  
  20. int main() {
  21. 	ios_base::sync_with_stdio(false);
  22. 	cin.tie(NULL);
  23. 	cin >> n >> k;
  24.  
  25. 	for(int i = 1; i <= n; ++i) {
  26. 		cin >> a[i];
  27. 		a[i] -= k;
  28. 	}
  29.  
  30. 	ll res = 0;
  31. 	for(int i = 1; i <= n; ++i) {
  32. 		a[i] += a[i - 1];
  33. 		if(a[i] >= 0) ++res;
  34. 		res += ((int) f.size()) - f.order_of_key({0, -1e9});
  35. 		f.insert({a[i], i});
  36. 	}
  37.  
  38. 	cout << res;
  39. 	return 0;
  40. }
  41.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
5 1
2 3 4 5 6
stdout
copy 
15
https://ideone.com/egpw3q
language:
C++ (gcc 8.3)
created:
13 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!