Nu aveti permisiuni pentru a descarca fisierul grader_test17.ok
Diferente pentru problema/timetravel intre reviziile #16 si #1
Diferente intre titluri:
Timetravel
timetravel
Diferente intre continut:
== include(page="template/taskheader" task_id="timetravel") ==
Avem ostructura dedate care permiteefectuarea 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.
Poveste şi cerinţă...
h2. 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$?
Fişierul de intrare $timetravel.in$ ...
h2. 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).
În fişierul de ieşire $timetravel.out$ ...
h2. 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
* $... ≤ ... ≤ ...$
h2. Exemplu table(example). |_. 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
| This is some text written on multiple lines. | This is another text written on multiple lines.
|
h3. Explicaţie ...
== include(page="template/taskfooter" task_id="timetravel") ==
== include(page="template/taskfooter" task_id="timetravel") ==