| Fişierul intrare/ieşire: | gugustiuc.in, gugustiuc.out | Sursă | ONI 2022 Baraj Seniori Ziua 2 |
| Autor | Tinca Matei | Adăugată de |  Lorintz Alexandru •Alex_tz307 |
| Timp execuţie pe test | 4 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Guguștiuc
Gimi Guguştiucul tocmai a ajuns intr-o situaţie destul de complicată. El are de participat la N şedinţe, a i-a şedinţă desfaşurându-se în intervalul de timp deschis la capete (xi, yi). El poate participa la mai multe şedinţe simultan, fiind online.
Pentru a-şi simplica programul, Gimi a decis să ia nişte pauze şi să elimine cateva şedinţe (să nu mai participe deloc la ele). El a aplicat o listă de Q operaţii, nu neapărat foarte inspirate:
- split t: Gimi va lua o pauză la momentul de timp t. Deci, pentru fiecare şedinţa din intervalul de timp (xi, yi), dacă se respectă condiţia xi < t < yi, atunci şedinţa respectivă este eliminată şi înlocuită cu două şedinţe noi în intervalele de timp deschise la capete (xi, t) şi (t, yi).
- skip t: Gimi nu va mai participa deloc la toate şedinţele care sunt în plină desfaşurare la momentul de timp t. Cu alte cuvinte, pentru fiecare fiecare şedinţă din intervalul de timp (xi, yi), dacă se respectă condiţia xi < t < yi, atunci Gimi va elimina şedinţa.
Gimi vrea să ştie dupa cele Q operaţii care este suma duratelor tuturor şedinţelor ramase. Durata unei şedinţe din intervalul de timp (x, y) se defineşte ca fiind y − x. Duratele şedinţelor se adună în întregime, chiar dacă există intervale de timp pe care acestea se suprapun.
Date de intrare
Pe prima linie se găsesc două numere N şi Q. Pe următoarele N linii se găsesc câte două numere, xi, yi pe fiecare linie, acestea reprezentând câte un interval în care se desfăşoară o şedinţă. Pe următoarele Q linii se găsesc câte două numere ai şi ti. Dacă ai este 1, atunci este descrisă o operaţie de tip split folosind valoarea ti. Dacă ai este 2, atunci este descrisă o operaţie de tip skip unde este folosită valoarea ti.
Date de ieşire
Se va afişa un singur număr reprezentând suma duratelor tuturor şedinţelor ramase, după aplicarea celor Q operaţii.
Restricţii
- 1 ≤ N, Q ≤ 500 000
- 1 ≤ xi, yi, ti ≤ 1 000 000, oricare ar fi 1 ≤ i ≤ Q.
- 1 ≤ ai ≤ 2, oricare ar fi 1 ≤ i ≤ Q.
| # | Punctaj | Restricţii |
|---|---|---|
| 1 2 3 4 5 6 7 | 9 12 13 12 11 19 24 | 1 ≤ N, Q ≤ 200 N = 1 N, Q ≤ 1000 xi ≤ xi+1, yi ≤ yi+1 pentru 1 ≤ i < N. 1 ≤ N ≤ 50 000 şi xi, yi, ti ≤ 50 000. 1 ≤ N ≤ 100 000 Nu există alte restricţii. |
Exemplu
| gugustiuc.in | gugustiuc.out |
|---|---|
| 2 3 1 10 4 10 1 3 1 6 2 5 | 10 |
Explicaţie
Gimi are două şedinţe în intervalele de timp (1, 10) şi (4, 10).
După prima operaţie, el elimină şedinţa din intervalul (1, 10) şi adăugă două şedinţe noi în intervalele de timp (1, 3) şi (3, 10). Acum are trei şedinţe la intervalele de timp (1, 3), (3, 10) şi (4, 10).
După a doua operaţie, Gimi elimină şedinţa din intervalul (3, 10) şi adăugă două şedinţe noi în intervalele de timp (3, 6) şi (6, 10). De asemenea, Gimi elimină şedinţa din intervalul (4, 10) şi se adaugă şedinţele (4, 6) şi (6, 10). Acum are cinci şedinţe la intervalele de timp (1, 3), (3, 6) şi (6, 10), (4, 6) şi (6, 10).
După ultima operaţie, Gimi elimină şedinţa de la intervalul de timp (3, 6) şi şedinţa de la intervalul de timp (4, 6). Rămân şedinţele de la intervalele de timp (1, 3), (6, 10) şi încă una tot la intervalul de timp (6, 10).
Suma duratelor tuturor şedinţelor ramase va fi (3 − 1) + (10 − 6) + (10 − 6) = 10.
