fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  5. #define long long long
  6.  
  7. const int N = 1e6+10;
  8.  
  9. class FenwickTree {
  10. private:
  11.     long t[N][2];
  12. public:
  13.     void update(int x, int type) {
  14.         for (; x <= N; x += x & -x)
  15.             t[x][type]++;
  16.     }
  17.     long get(int x, int type) {
  18.         long res = 0;
  19.         for (; x > 0; x -= x & -x)
  20.             res += t[x][type];
  21.         return res;
  22.     }
  23. } BIT;
  24.  
  25. int n, m, k;
  26. int a[N], f[N], b[N];
  27.  
  28. void Enter() {
  29.     scanf("%d%d", &n, &k);
  30.     FOR(i, 1, n) scanf("%d", &a[i]);
  31. }
  32.  
  33. long calc(int x, int type) {
  34.     m = 0;
  35.     for (int i = 1; i <= n; ++i) {
  36.         f[i] = f[i-1] + (a[i] >= x);
  37.         b[++m] = 2 * f[i] - i - 1;
  38.         b[++m] = 2 * f[i-1] - i;
  39.     }
  40.  
  41.     sort(b + 1, b + m + 1);
  42.  
  43.     long res = 0;
  44.     FOR(i, 1, n) {
  45.         int cur = lower_bound(b + 1, b + m + 1, 2 * f[i - 1] - i) - b;
  46.         BIT.update(cur, type);
  47.         cur = lower_bound(b + 1, b + m + 1, 2 * f[i] - i - 1) - b;
  48.         res += BIT.get(cur, type);
  49.     }
  50.     return res;
  51. }
  52.  
  53. void Process() {
  54.     long res = calc(k, 0) - calc(k + 1, 1);
  55.     double ans = 1ll * n * (n + 1) / 2;
  56.     ans = res / ans;
  57.     printf("%.6lf", ans);
  58. }
  59.  
  60. int main() {
  61.  //   freopen("input.in", "r", stdin);
  62.  
  63.     Enter();
  64.     Process();
  65.  
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0s 43408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-nan
https://ideone.com/D2dy0F
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!