# PBinfo #4394 – fotbal2 – Rezolvare C++

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

## Enunț

Cei N copii de la școala generală vor să formeze o echipă de fotbal compusă din K elevi, dintre care cel puțin unul stângaci și cel puțin unul dreptaci. Pentru fiecare copil i (de la 0 la N-1) se cunoaște intervalul de timp în care acesta este disponibil pentru a face parte din echipă, sub forma unei perechi, [starti, endi], cât și dacă este stângaci sau dreptaci. K copii pot juca în aceeași echipa dacă intervalele de timp în care aceștia sunt disponibili se suprapun în cel puțin un punct (moment de timp).

Cerința
Se cere numărul de moduri în care se poate alcătui o echipă cu K dintre cei N elevi; deoarece acest număr poate să fie foarte mare, el se va afișa modulo 1.000.000.009.

Date de intrare
Pe prima linie din fișierul fotbal.in se găsesc numerele N și K. Pe următoarele N linii, se găsesc câte 3 numere naturale, starti endi fi, unde [starti, endi] reprezintă intervalul de timp în care al i-lea copil este disponibil pentru a face parte din echipă, iar fi reprezintă piciorul cu care joacă al i-lea copil, fi =1 dacă al i-lea copil este dreptaci și fi =0 dacă al i-lea copil este stângaci.

Date de ieșire
Fișierul de ieșire fotbal.out va conține doar numărul de moduri cerut, în forma precizată în cerință. 

Restricții și precizări

2 ≤ K ≤ N ≤ 100.000
0 ≤ starti ≤ endi ≤ 1.000.000.000, pentru orice i de la 0 la N − 1
fi ∈ {0, 1}, pentru orice i de la 0 la N − 1
Pentru 25 de puncte, K = 2 și 2 ≤ N ≤ 1000
Pentru 17 de puncte, K = 2 și există cel mult 5 copii care sunt stângaci
Pentru 33 de puncte, 2 ≤ K ≤ N ≤ 1000
Pentru 25 de puncte, fără restricții suplimentare

Exemplu:
fotbal.in

5 2
1 8 0
2 5 1
3 7 0
0 9 1
6 12 0
fotbal.out

5
Explicație
Posibilele echipe sunt (0, 1), (0, 3), (1, 2), (2, 3), (3, 4). Nu putem forma, de exemplu, echipa (2, 4) deoarece ambii copii sunt stângaci. Totodată, nu putem forma echipa (1, 4), deoarece intervalele de timp în care cei doi copii sunt disponibili nu se suprapun în niciun punct.

## Cod sursă C++

```cpp
// Popa Sebastian
#include <bits/stdc++.h>
using namespace std;
const int mod = 9 + 1e9;
const int nmax = 5 + 1e5;
ifstream f("fotbal.in");
ofstream g("fotbal.out");
struct str
{
    int st, dr, tip;
    bool operator<(const str &other) const
    {
        return st < other.st;
    }
} v[nmax];
vector<long> fact(nmax, 1), inv_fact(nmax, 1);
void precompute();
int nCk(const int &, const int &);
int n, k, rez, c[2];
priority_queue<pair<int, bool>> pq;
int main()
{
    precompute();
    f >> n >> k;
    for (int i = 1; i <= n; i++)
        f >> v[i].st >> v[i].dr >> v[i].tip;
    sort(v + 1, v + n + 1);
    for (int i = 1; i <= n; i++)
    {
        while (!pq.empty() && -pq.top().first < v[i].st)
            c[pq.top().second]--, pq.pop();
        if (pq.size() >= k - 1 && c[!v[i].tip])
            rez = (rez + nCk(pq.size(), k - 1)) % mod,
            rez = (rez - nCk(c[v[i].tip], k - 1) + mod) % mod;
        c[v[i].tip]++;
        pq.push({-v[i].dr, v[i].tip});
    }
    g << rez;
    return 0;
}
void precompute()
{
    vector<int> inv(nmax, 1);
    for (int i = 2; i < nmax; i++)
    {
        inv[i] = mod - (1ll * (mod / i) * inv[mod % i]) % mod;
        fact[i] = (1ll * fact[i - 1] * i) % mod;
        inv_fact[i] = (1ll * inv_fact[i - 1] * inv[i]) % mod;
    }
}
int nCk(const int &n, const int &k)
{
    if (!n || k > n)
        return 0;
    if (!k || k == n)
        return 1;
    static int rez;
    rez = (1ll * fact[n] * inv_fact[k]) % mod;
    return (1ll * rez * inv_fact[n - k]) % mod;
}
```

## Resurse

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