Solution to http://usaco.org/index.php?page=viewproblem2&cpid=91

AboveTheMedian.cpp

#include <iostream>

typedef long long int64;

template<typename T>
T read() {
    T var;
    std::cin >> var;
    return var;
}

const int kMax = 100005;
int H[kMax];
int S[kMax];

int table[2*kMax];

inline int lowestOneBit(int n) {
    return n & -n;
}

int read(int index) {
    int sum = 0;
    while (index > 0) {
        sum += table[index];
        index -= lowestOneBit(index);
    }
    return sum;
}

void update(int index, int delta) {
    while (index < 2 * kMax) {
        table[index] += delta;
        index += lowestOneBit(index);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    const int N = read<int>();
    const int X = read<int>();

    for (int i = 1; i <= N; i++) {
        H[i] = read<int>();
        S[i] = S[i-1];
        if (H[i] >= X) {
            S[i] += 1;
        } else {
            S[i] -= 1;
        }
    }

    int64 answer = 0;
    for (int i = 1; i <= N; i++) {
        int sum = S[i] + kMax;
        int r = read(sum);
        answer += r;
        if (sum >= kMax) {
            answer++;
        }
        update(sum, 1);
    }
    std::cout << answer << std::endl;
    return 0;
}