Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Rezultatele filtrării | Rezultatele filtrării | Guguștiuc

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2022-04-13 21:06:44.
Revizia anterioară Revizia următoare

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

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 $({x}_{i}, {y}_{i})$ . 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 $({x}_{i}, {y}_{i})$ , dacă se respectă condiţia ${x}_{i}$ $<$ t $<$ ${y}_{i}$ , atunci şedinţa respectivă este eliminată şi înlocuită cu două şedinţe noi în intervalele de timp deschise la capete $({x}_{i}, t)$ şi $(t, {y}_{i})$
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 $({x}_{i}, {y}_{i})$ , dacă se respectă condiţia ${x}_{i}$ $<$ t $<$ ${y}_{i}$ , 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, ${x}_{i}, {y}_{i}$ 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 ${a}_{i}$ şi ${t}_{i}$ . Dacă ${a}_{i}$ este 1, atunci este descrisă o operaţie de tip split folosind valoarea ${t}_{i}$ . Dacă ${a}_{i}$ este 2, atunci este descrisă o operaţie de tip skip unde este folosită valoarea ${t}_{i}$ .