PROG-1110: มัธยฐาน (Median)

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;
const int INF = 1e9;
using lli = long long;
unordered_map < int , int > LeftOdd, LeftEven;
int ar[N], qs[N];
int n;

int main(){

    int med;
    scanf("%d%d", &n, &med);

    int cur = -1;
    for(int i=1;i<=n;i++){
        scanf("%d", &ar[i]);
        if(ar[i] == med) cur = i;
        else if(ar[i] < med) qs[i] = -1;
        else qs[i] = 1;
    }

    for(int i=cur-1;i>=1;i--)
        qs[i] += qs[i+1];
    for(int i=cur+1;i<=n;i++)
        qs[i] += qs[i-1];

    for(int i=1;i<=cur;i++){
        if(i % 2 == 1) LeftOdd[ qs[i] ] ++;
        else LeftEven[ qs[i] ] ++;
    }

    /// query
    lli cnt = 0;
    for(int i=cur;i<=n;i++){
        if(i % 2 == 1) cnt += (lli) LeftOdd[ -qs[i] ];
        else cnt += (lli) LeftEven[ -qs[i] ];
    }

    printf("%lld", cnt);

    return 0;
}