fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. template <typename T> bool maximize(T &res, const T &val){if(res < val) return res = val, true; return false;}
  6. template <typename T> bool minimize(T &res, const T &val){if(res > val) return res = val, true; return false;}
  7.  
  8. #define ll long long
  9. #define fi first
  10. #define se second
  11. #define pb push_back
  12. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  13. #define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; i--)
  14. #define REP(i, n) for(int i = 0, _n = (n); i < _n; i++)
  15. #define C make_pair
  16. #define MASK(i) (1LL << (i))
  17. #define TURN_ON(i, x) ((x) | MASK(i))
  18. #define TURN_OFF(i, x) ((x) & ~MASK(i))
  19. #define RE(i, x) ((x) ^ MASK(i))
  20.  
  21. const ll mod = 1e9 + 7;
  22. const ll INF = 1e15;
  23. const int maxn = 1e5 + 5;
  24. typedef pair<int, int> pi;
  25. typedef pair<int, pair<int,int>> pii;
  26. typedef pair<ll, ll> pl;
  27. typedef pair<ll, pair<ll,ll>>pll;
  28.  
  29. struct edge{
  30.     int u,v,w;
  31.     edge(int u = 0, int v = 0, int w = 0)
  32.     {
  33.         this->u = u;
  34.         this->v = v;
  35.         this->w = w;
  36.     }
  37. };
  38. struct matrix{
  39.     ll val[3][3];
  40.     matrix(){
  41.         memset(val, 0, sizeof(val));
  42.     }
  43. };
  44.  
  45. ll n, k, a[maxn], BIT[maxn], sum[maxn], b[maxn], ans;
  46.  
  47. void update(int x, int val){
  48. 	for(; x <= n + 3; x += x & -x) BIT[x] += val;
  49. }
  50. int get(int x){
  51. 	int s = 0;
  52. 	for(; x > 0; x -= x & -x) s += BIT[x];
  53. 	return s;
  54. }
  55. void sub1()
  56. {
  57.     long long dem = 0;
  58.     for(int i = 0; i < n; i++)
  59.     {
  60.         for(int j = i+1; j <= n; j++)
  61.         {
  62.             if(sum[j] - sum[i] >= 0) dem++;
  63.         }
  64.     }
  65.     cout << dem;
  66. }
  67. void nhap(){
  68. 	cin >> n >> k;
  69. 	FOR(i, 1, n){
  70. 		cin >> a[i];
  71. 		a[i] -= k;
  72. 		sum[i] = sum[i - 1] + a[i];
  73. 		b[i + 1] = sum[i];
  74. 	}
  75. }
  76. void solve(){
  77. 	sort(b + 1, b + 2 + n);
  78. 	FOR(i, 0, n){
  79. 		int tmp = lower_bound(b + 1, b + 2 + n, sum[i]) - b;
  80. 		ans = ans + 1LL * get(tmp);
  81. 		update(tmp, 1);
  82. 	}
  83. 	cout << ans;
  84. }
  85. int main(){
  86.     ios_base::sync_with_stdio(0);
  87.     cin.tie(0); cout.tie(0);
  88.     nhap();
  89.     solve();
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
1 1
12
stdout
copy 
11
https://ideone.com/1oolEq
language:
C++14 (gcc 8.3)
created:
38 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!