parcare2

Parcare2

În cel mai recent eveniment al companiei Tesla, Paul Musk a anunţat un nou produs inovativ: parcarea autonomată. Fiind cunoscut pentru lansările produselor incomplete, nici parcarea nu este completă, fiind nevoie de o automatizare pentru a atribui câte un loc maşinilor care vor să folosească parcarea.

Parcarea este formată din $N$ locuri, numerotate de la 1 la $N$ şi este deschisă timp de $T$ secunde, începând cu secunda $1$. Pe parcursul zilei, sosesc $M$ maşini care vor să folosească parcarea, pentru fiecare dintre acestea ştiindu-se timpul de sosire $s{~i~}$ şi timpul de plecare $p{~i~}$. Maşinile vin în ordinea timpului de sosire $s{~i~}$ şi ocupă locul de parcare în intervalul de timp [{$s{~i~}, p{~i~}$}]. Pentru fiecare dintre acestea, trebuie să afişaţi un loc liber de parcare (dacă sunt mai multe, se poate afişa oricare) în care aceasta se poate aşeza sau $−1$ dacă parcarea este plină în momentul venirii maşinii. Dacă o maşină nu are loc în parcare la timpul de sosire, aceasta nu va mai intra în parcare la niciun timp viitor.
 
La final, Paul este interesat de maşinile care mai sunt rămase în parcare la închiderea parcării, de aceea, vă cere să afişaţi configuraţia parcării la timpul $T$.
 

h2. Date de intrare

Fişierul de intrare $parcare2.in$ ...

Pe prima linie se găsesc trei numere întregi $N$, $M$ şi $T$ , reprezentând numârul de locuri din parcare, numărul de maşini care vin să folosească parcarea, respectiv numărul de secunde pentru care este deschisă parcarea.
 
Următoarele $M$ linii conţin fiecare câte două numere întregi $s{~i~}$, $p{~i~}$, reprezentând venirea unei maşini la secunda $s{~i~}$ care va pleca la secunda $p{~i~}$.
 
Maşinile apar în fişierul de intrare în ordine crescătoare după timpul de sosire $s{~i~}$.

h2. Date de ieşire

În fişierul de ieşire $parcare2.out$ ...

Se vor afişa $M + 1$ linii în total, primele $M$ linii conţinând fiecare câte un număr întreg între $1$ şi $N$ reprezentând locul de parcare pe care îl va ocupa maşina, sau $−1$ dacă nu există niciun loc de parcare disponibil.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ $N, M, T$ ≤ 200 000$
* $1 ≤ $s{~i~}$ ≤ T$
* $1 &le; $s{~i~}$ < $p{~i~}$ &le; 200 000$
* Considerând următoarele $2M$ valori: $s{~1~}$, $s{~2~}$, ..., $s{~M~}$, $p{~1~}$, $p{~2~}$, ..., $p{~M~}$, acestea sunt distincte două câte două.
* {*Dacă există mai multe soluţii, se poate afişa oricare dintre acestea.*}
 
h2. Punctare
 
table(example). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $24$ | s{~i~} + 1 = $p{~i + 1~}$, adică fiecare maşină stă exact o secundă.|
| $2$ | $26$ | $p{~i~} > s{~j~}$, adică toate maşinile vin înainte ca vreo maşină să plece. |
| $3$ | $26$ | $N &le; 1 000$ |
| $4$ | $24$ | $Fără restricţii suplimentare.$ |

h2. Exemplu

table(example). |_. parcare2.in |_. parcare2.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. parcare2.in |_. parcare2.out |_. Explicaţii |
| 2 4 6
  1 3
  2 10
  4 6
  5 8
| 2
  1
  2
  -1
  2 -1
| Prima maşină soseşte în secunda 1 şi este parcată pe locul 2.
  A doua maşină soseşte în secunda 2 şi este parcată pe locul 1.
  În secunda 3 se eliberează locul 2.
  Cea de-a treia maşină soseşte în secunda 4 şi ocupă locul 2.
  Maşina sosită în secunda 5 nu găseşte loc liber.
  În secunda 6 se eliberează locul 2.
  După închiderea parcării, pe locul 1 va fi parcată maşina venită în secunda 2, locul al doilea fiind liber.
|

== include(page="template/taskfooter" task_id="parcare2") ==