# PBinfo #2218 – Set – Rezolvare C++

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

## Enunț

Domnul Set vă oferă – ce altceva? – o mulțime de numere naturale A, inițial vidă. Pe mulțimea A se definesc următoarele operații:


1 x – introduce valoarea x în A (dacă x este deja în A, atunci operația nu se efectuează)
2 x – interogare: care valoare din A este cea mai mică, dar mai mare sau egală cu x (dacă o asemenea valoare nu există, sau dacă A este vidă, se va afișa -1)
3 x y – șterge din A toate numerele din intervalul [x, y].

Cerința
Dându-se N operații, trebuie să afișați răspunsul la fiecare operație de tip 2.

Date de intrare
Fișierul de intrare set.in conține pe prima linie N. Pe următoarele N linii sunt date cele N operații.

Date de ieșire
În fișierul de ieșire set.out se vor afișa pe câte o linie răspunsurile la operațiile de tip 2.

Restricții și precizări

1 ≤ N ≤ 200 000
Va exista cel puțin o operație de tip 2
0 ≤ x ≤ y ≤ 2 000 000 000

Exemplu:
set.in

15
1 10
1 20
1 30
1 40
1 50
1 60
1 70
1 80
1 90
2 39
2 70
3 30 100
2 30
1 3
2 2
set.out

40
70
-1
3
Explicație
Se introduc mai întâi în A valorile 10, 20, 30, 40, 50, 60, 70, 80, 90. Urmează: 
Întrebarea (2, 39): Numărul cel mai mic mai mare sau egal cu 39 este 40. 
Întrebarea (2, 70): Numărul cel mai mic mai mare sau egal cu 70 este 70. 
Operația (3 30 100): Se șterg numerele din intervalul [30,100], adică se șterg valorile 30, 40, 50, 60, 70, 80, 90.
Întrebarea (2 30): Nu există număr mai mare sau egal cu 30, deci afișăm -1.
Operația (1 3): Se introduce 3 în mulțime.
Întrebarea (2, 2): Numărul cel mai mic mai mare sau egal cu 2 este 3.

## Cod sursă C++

```cpp
/// O(N log N)
#include <bits/stdc++.h>
using namespace std;
int main ()
{
    int N, x, y, op;
    set<int> s;
    set<int>::iterator it, A, B;
    ifstream  fin("set.in");
    ofstream fout("set.out");
    fin >> N;
    while (N--)
    {
        fin >> op;
        if (op == 1)
        {
            fin >> x;
            s.insert(x);
        }
        else if (op == 2)
        {
            fin >> x;
            if (s.empty()) {fout << "-1\n"; continue;}
            it = s.lower_bound(x);
            if (it == s.end()) fout << "-1\n";
            else fout << *it << "\n";
        }
        else
        {
            fin >> x >> y;
            if (s.empty()) continue;
            A = s.lower_bound(x);
            B = s.lower_bound(y + 1);
            s.erase(A, B);
        }
    }
    fin.close();
    fout.close();
    return 0;
}
```

## Resurse

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