# PBinfo #4285 – Report – Rezolvare C++

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

## Enunț

Se dă un șir a1, a2, …, an de numere întregi și m operații, fiecare operație fiind dată printr-o pereche de numere op și k: dacă op = 1 atunci primele k elemente din șir se ordonează crescător, iar dacă op = 2 atunci primele k elemente din șir se ordonează descrescător.

Cerința
Să se afișeze elementele șirului după efectuarea tuturor celor m operații.

Date de intrare
Fișierul de intrare report.in conține pe prima linie numerele n și m, iar pe a doua linie, separate prin câte un spațiu, sunt elementele șirului a1, a2, …, an. Pe următoarele m linii se află câte două numere op k reprezentând câte o operație. Dacă op = 1, atunci primele k elemente din șir se ordonează crescător, iar dacă op = 2 atunci primele k elemente din șir se ordonează descrescător.

Date de ieșire
Fișierul de ieșire report.out va conține pe prima linie, separate prin câte un spațiu, elementele șirului după efectuarea celor m operații.

Restricții și precizări

1 ≤ n, m ≤ 200.000
-1.000.000.000 ≤ a[i] ≤ 1.000.000.000

Exemplu:
report.in

4 2
1 2 4 3
2 3
1 2
report.out

2 4 1 3
Explicație
Șirul inițial este 1 2 4 3. Prima operație este 2 3, adică primele trei elemente se ordonează descrescător, deci șirul devine 4 2 1 3. A doua operație este 1 2, adică primele două elemente se ordonează crescător, deci șirul devine 2 4 1 3.

## Cod sursă C++

```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = (int)2e5 + 1;
int n, m;
int a[N], ti, ri;
int t[N], r[N], s;
int b[N], bl, br;
int main()
{
    freopen("report.in", "r", stdin);
    freopen("report.out", "w", stdout);
    scanf("%d%d", &n, &m), s = 0;
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &ti, &ri);
        while (s > 0 && ri >= r[s - 1])
            --s;
        t[s] = ti, r[s] = ri, ++s;
    }
    bl = 0, br = r[0], r[s] = 0, ++s;
    for (int i = 0; i < br; ++i)
        b[i] = a[i];
    sort(b, b + br);
    for (int i = 1; i < s; ++i)
        for (int j = r[i - 1]; j > r[i]; --j)
            a[j - 1] = (t[i - 1] == 1) ? b[--br] : b[bl++];
    for (int i = 0; i < n; ++i)
        printf("%d ", a[i]);
    return 0;
}
```

## Resurse

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