Fişierul intrare/ieşire:brasov.in, brasov.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorVlad-Andrei MunteanuAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test5.5 secLimită de memorie64000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Brasov

Aflat la doar o saptamana inaintea inceperii etapei nationale a olimpiadei de informatica, un impatimit fan al acestei competitii, Georgel Tractorescu, isi depaneaza amintirile din anii ce-au trecut alaturi de prieteni la un pahar de suc in Centrul Vechi al orasului Brasov. Acesta isi aminteste cu placere de fiecare clipa petrecuta in acest mediu prielnic dezvoltarii atat pe plan academic, cat si pe plan personal, asa ca doreste sa inchine un pahar de apa in cinstea organizatorilor. Totusi, deoarece nimic nu este perfect, Georgel si-a dat seama de o eroare in regulamentul acestei competitii si vrea sa profite de aceasta pentru a manipula viitoarele rezultate si, cine stie, poate chiar sa va ofere voua locul 1. Fiind insa prea ocupat sa se relaxeze, acesta va propune urmatoarea afacere: oricine il ajuta pe Georgel sa isi duca la bun sfarsit planul, va primi de la acesta 100 de puncte in cadrul concursului "Adolescent Grigore Moisil" si poate 300 de puncte la viitoarea editie a olimpiadei nationale de informatica, iar cine nu, va fi nevoit sa se multumeasca cu un Guinness. Deoarece Georgel nu este usor de pacalit (fiti ca Georgel!) acesta nu va da propriu-zis greseala din regulament, ci va cere sa ii implementati un program care sa ii raspunda la un set de cerinte. Stiind ca initial se pleaca de la o functie care este definita pe multimea vida, cerintele sunt dupa cum urmeaza:

  • 1 a b - se insereaza intervalul [a, b] in domeniul functiei (Domeniu = Domeniu U [a, b])
  • 0 a b - se sterge intervalul (a, b) din domeniul functiei (Domeniu = Domeniu \ (a, b))
  • MAX - se cere sa se determinea lungimea maxima a unui interval continuu maximal din domeniu, iar in cazul in care nu exista niciun interval, se va afisa -1.
  • MIN - se cere sa se determine lungimea minima a unui interval continuu maximal din domeniu, iar in cazul in care nu exista niciun interval, se va afisa -1.
  • Diff_min - se cere sa se determina diferenta minima dintre lungimile a doua intervale continue maximale din domeniu, iar in cazul in care nu exista cel putin doua intervale, se va afisa -1.
  • Diff_max - se cere sa se determina diferenta maxima dintre lungimile a doua intervale continue maximale din domeniu, iar in cazul in care nu exista cel putin doua intervale, se va afisa -1.
  • 2 x y - se cere sa se determine cate intervale continue maximale au lungimea cuprinsa in intervalul [x, y]

Date de intrare

Fisierul de intrare brasov.in contine pe prima linie numarul q, reprezentand numarul de cerinte. Fiecare dintre urmatoarele q linii descrie unul dintre tipurile de cerinte prezentate mai sus.

Date de ieşire

În fişierul de ieşire brasov.out se vor afisa raspunsurile pentru fiecare cerinta, fiecare raspuns aflandu-se pe cate o linie separata si in ordinea din in care au fost citite cerintele.

Restricţii

  • 1 ≤ q ≤ 500.000.
  • -100.000.000 ≤ a ≤ 100.000.000.
  • -100.000.000 ≤ b ≤ 100.000.000.
  • 0 ≤ x ≤ 1.000.000.000.
  • 0 ≤ y ≤ 1.000.000.000.
  • Se garanteaza ca pentru fiecare cerinta de tipul 1 urmatoarea relatie este valabila: a ≤ b.
  • Se garanteaza ca pentru fiecare cerinta de tipul 0 urmatoarea relatie este valabila: a + 1 ≤ b.
  • Se garanteaza ca nu vor fi mai mult de 200.000 cerinte din tipul 1 si din tipul 2.
  • Un interval J este considerat continuu daca si numai daca poate fi scris sub forma [a, b].
  • Un interval continuu J este considerat maximal daca si numai daca nu exista niciun alt interval continuu [x, y] din domeniu cu proprietatea ca [a, b] este inclus in [x, y].

Exemplu

brasov.inbrasov.out
9
1 -1 2
MIN
MAX
Diff_min
Diff_max
2 0 3
0 -1 2
Diff_min
Diff_max
3
3
-1
-1
1
0
0

Explicaţie

  • Dupa prima cerinta, domeniul devine: Domeniu = [-1, 2].
  • Dupa cerinta a saptea, domeniul devine: Domeniu = [-1, -1] U [2, 2]
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?