Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | timetravel.in, timetravel.out | Sursă | Algoritmiada 2013, Runda Finala |
| Autor | Cosmin Gheorghe | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
Timetravel
Avem o structura de date care permite efectuarea operatiilor inainte si inapoi in timp. Structura de date accepta operatii de insert(time,val) si erase(time,val). Totodata, putem sa ne ducem inainte sau inapoi in timp pentru a sterge sau adauga una dintre aceste doua opertii. Periodic, mai avem operatii de query(time, val), pentru care trebuie sa raspundem, luand in considerare operatiile de pana acum, care este cel mai mic numar mai mare sau egal ca numarul val la momentul time pe axa temporala.
Date de intrare
Se da un numar natural M reprezentand numarul de operatii.
Pe urmatoarele M linii urmeaza descrierea fiecarei operatii. Operatiile sunt de 5 tipuri. Fiecare rand are prima valoare tipul operatie:
Daca avem operatie de tip 1, se adauga operatia insert(val). Aceasta operatie reprezinta inserarea valorii val la momentul de timp -infinit.
Daca avem operatie de tip 2, se adauga operatia erase(time, val). Acesta operatie reprezinta stergerea valorii val, daca exista, la momentul de timp time. Nu se garanteaza ca val exista, sau va exista vreodata.
Daca avem operatie de tip 3, se va sterge o operatie de insert(val) din structura. Se garanteaza ca exista o operatie de insert(val) cu aceasta valoare deja in structura.
Daca avem operatie de tipul 4, se va sterge o operatie de erase(time, val) din structura. Se garanteaza ca exista o operatie de erase cu aceste valori. In cazul in care sunt mai multe operatii de erase cu aceste valori, se va sterge una singura.
Daca avem operatie de tipul 5, trebuie sa raspundeti la intrebarea: care este cea mai mica valoare aflata in structura la timpul time mai mare sau egala ca val?
Date de ieşire
În fişierul de ieşire timetravel.out se va afisa pe linia i raspunsul la a i-a operatie de tip query.
Daca nu exista un astfel de numar se afiseaza "Time paradox" (fara ghilimele).
Restricţii
- 1 ≤ M ≤ 500.000
- 1 ≤ N ≤ 100.000 unde N e numarul de valori distincte cu care se apeleaza insert(-inf, val)
- Nu vor exista doua operatii de insert cu aceeasi valoare in acelasi timp.
- -1.000.000.000 ≤ time, val ≤ 1.000.000.000 pentru orice operatie
Exemplu
| timetravel.in | timetravel.out |
|---|---|
| 19 5 -100 100 1 100 2 20 100 2 10 50 2 10 50 5 0 50 5 0 101 5 5 100 5 15 100 5 20 0 1 50 5 0 50 5 5 51 5 9 50 5 10 50 4 10 50 5 10 50 4 10 50 5 10 50 | Time paradox 100 Time paradox 100 100 Time paradox 50 100 50 100 100 50 |
