PROG-T1110: Median

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 1e6;

int qsum[N + 1];
map<int, int> mp[2];

int main(){

    int nNumber, tr;
    scanf("%d%d", &nNumber, &tr);
    for(int i = 1; i <= nNumber; ++i){
        int x;
        scanf("%d", &x);
        if(x > tr){
            qsum[i] = 1;
        } else if(x == tr){
            qsum[i] = 0;
        } else {
            qsum[i] = -1;
        }
        qsum[i] += qsum[i - 1];
    }

    lli sum = 0;
    ++mp[0][0];
    for(int i = 1; i <= nNumber; ++i){
        int curr = i % 2;
        int prev = curr ^ 1;
        map<int, int>::iterator itr = mp[prev].find(qsum[i]);
        if(itr != mp[prev].end()){
            sum += itr -> second;
        }
        ++mp[curr][qsum[i]];
    }
    cout << sum;

    return 0;
}