gugustiuc

Time limit: 3.5s
Memory limit: 512MB
Input:
Output:

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)(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 (xi,yi)(x_i, y_i), dacă se respectă condiția xi<t<yix_i < t < y_i, atunci ședința respectivă este eliminată și înlocuită cu două ședințe noi în intervalele de timp deschise la capete (xi,t)(x_i, t) și (t,yi)(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 ședință din intervalul de timp (xi,yi)(x_i, y_i), dacă se respectă condiția xi<t<yix_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, xi,yix_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 aia_i și tit_i. Dacă aia_i este 1, atunci este descrisă o operație de tip split folosind valoarea tit_i. Dacă aia_i este 2, atunci este descrisă o operație de tip skip unde este folosită valoarea tit_i.

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
  • 1xi,yi,ti1 000 0001 ≤ x_i, y_i, t_i ≤ 1 \ 000 \ 000, oricare ar fi 1 ≤ i ≤ Q
  • 1ai21 ≤ a_i ≤ 2, oricare ar fi 1 ≤ i ≤ Q

Subtask 1 (9 puncte)

  • 1 ≤ N, Q ≤ 200

Subtask 2 (12 puncte)

  • N = 1

Subtask 3 (13 puncte)

  • N, Q ≤ 1 000

Subtask 4 (12 puncte)

  • xixi+1,yiyi+1x_i ≤ x_{i+1}, y_i ≤ y_{i+1} pentru 1 ≤ i < N

Subtask 5 (11 puncte)

  • 1 ≤ N ≤ 50 000 și xi,yi,ti50 000x_i, y_i, t_i ≤ 50 \ 000

Subtask 6 (19 puncte)

  • 1 ≤ N ≤ 100 000

Subtask 7 (24 puncte)

  • Nu există alte restricții

Exemple

stdin

2 3
1 10
4 10
1 3
1 6
2 5

stdout

10

Explicații

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.

Problem info

ID: 145

Editor: liviu

Author:

Source: ONI 2022 Baraj 2 Seniori: Problema 2

Tags:

ONI 2022 Baraj 2 Seniori

Log in or sign up to be able to send submissions!