# PBinfo #3831 – Medians – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
Se dă un vector cu n elemente. Să se determine numărul de secvențe care au medianul valorilor egal cu k.

Date de intrare
Fișierul de intrare medians.in contine pe prima linie un număr N reprezentând numărul de elemente din vector și un număr k cu semnificația din enunț. Pe a doua linie se află N elemente , elementele vectorului.

Date de ieșire
Fișierul de ieșire medians.out contine pe prima linie răspunsul.

Restricții și precizări

N ≤ 100.000, K ≤ 1.000.000.000
Pentru teste in valoare de 10 puncte, N ≤ 100.
Pentru alte teste in valoare de 10 puncte, N ≤ 1000.
Pentru restul de teste se respecta restrictiile initiale.
Prin mediana unui vector de lungime N se intelege elementul de pe pozitia [(N+1)/2] dupa sortare.

Exemplu:
medians.in

2 2
1 2
medians.out

1
medians.in

3 5
5 1 5 
medians.out

3

## Cod sursă C++

```cpp
#include <bits/stdc++.h> 
#pragma warning (disable : 26451) 
#pragma warning (disable : 4996) 
using namespace std; 
ifstream fin("medians.in"); 
ofstream fout("medians.out"); 
#define MAXN 100005 
int a[MAXN], b[2 * MAXN]; 
int n; 
int query(int p) { 
    int t = 0; 
    for (int i = (p + MAXN); i; i -= (i & -i)) { 
        t += b[i]; 
    } 
    return t; 
} 
void update(int p, int val) { 
    for (int i = (p + MAXN); i < 2 * MAXN; i += (i & -i)) { 
        b[i] += val; 
    } 
} 
long long solve(long long k) { 
    long long s = 0; 
    for (int i = 0; i < 2 * MAXN; ++i) { 
        b[i] = 0; 
    } 
    long long total = 0; 
    update(0, 1); 
    for (int i = 0; i < n; ++i) { 
        s += (a[i] > k ? -1 : 1); 
        total += query(s); 
        update(s, 1); 
    } 
    return total; 
} 
int main() { 
    long long k; 
    fin >> n >> k; 
    for (int i = 0; i < n; ++i) { 
        fin >> a[i]; 
    } 
    fout << solve(k) - solve(k - 1); 
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3831)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3831/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3831/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)