Fişierul intrare/ieşire:timetravel.in, timetravel.outSursăAlgoritmiada 2013, Runda Finala
AutorCosmin GheorgheAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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(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(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.intimetravel.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?