== include(page="template/taskheader" task_id="clasament2") ==
Poveste şi cerinţă...
Deoarece este ultimul baraj, comisia în sfârşit se va putea relaxa privind clasamentul concurenţilor în timp real de la probă. Însă, evident, asta nu îi satisface îndeajuns, aşa că ei mai vor să ştie, după fiecare schimbare de punctaj a unui concurent, de câte ori au mai fost concurenţii ordonaţi în ordinea respectivă de-a lungul concursului până în momentul respectiv.
h2. Date de intrare
Fişierul de intrare $clasament2.in$ ...
Fişierul de intrare $clasament2.in$ conţine pe prima linie numerele $N$ şi $M$, reprezentând numărul de concurenţi, respectiv numărul de modificări ale clasamentului. Pe următoarea linie se află $N$ numere, punctajele celor $N$ concurenţi înainte de probă (deoarece departajarea a fost foarte bine făcută, toate punctajele sunt diferite). Pe următoarele $M$ linii se află $M$ perechi de numere $x$ şi $y$ ce descriu în ordine cronologică schimbările de punctaj. A $i$-a pereche reprezintă faptul că scorul participantului $x$ a devenit $y$. Punctajul unui concurent la un moment de timp poate fi mai mic decât la începutul concursului, dar se garantează că nu va fi negativ.
h2. Date de ieşire
În fişierul de ieşire $clasament2.out$ ...
În fişierul de ieşire $clasament2.out$ se vor afişa $M$ linii, pe fiecare linie fiind răspunsul cerut.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 50 000$
* $1 ≤ M ≤ 200 000$
* $1 ≤ x ≤ N$
* Atât la începutul concursului, cât şi pe parcursul acestuia, punctajele concurenţilor vor fi numere întregi din intervalul $[0, 1 000 000 000]$
* Clasamentul este descrescător după scor.
* În cazul în care $2$ sau mai multe punctaje sunt egale la un moment de timp, concurenţii sunt departajaţi în funcţie de timpul ultimei modificări de punctaj, astfel încât concurentul care a obţinut punctajul mai devreme este clasat mai sus.
* Pentru $20%$ din teste $1 ≤ N, M ≤ 2000$
h2. Exemplu
table(example). |_. clasament2.in |_. clasament2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
table(example). |_. clasament2.in |_. clasament2.out |_. Explicatie |
| 3 6
10 12 8
1 13
2 15
3 10
1 17
2 20
1 20
| 0
1
2
1
3
4
| Moment 0: clasament: {2, 1, 3}, punctaje: {10, 12, 8}
Moment 1: clasament: {1, 2, 3}, punctaje: {13, 12, 8}
Moment 2: clasament: {2, 1, 3}, punctaje: {13, 15, 8}
(la fel ca în momentul 0)
Moment 3: clasament: {2, 1, 3}, punctaje: {13, 15, 10}
(la fel ca în momentele 0 şi 2)
Moment 4: clasament: {1, 2, 3}, punctaje: {17, 15, 10}
(la fel ca în momentul 1)
Moment 5: clasament: {2, 1, 3}, punctaje: {17, 20, 10}
(la fel ca în momentele 0, 2 şi 3)
Moment 6: clasament: {2, 1, 3}, punctaje: {20, 20, 10}
(la fel ca în momentele 0, 2, 3 şi 5)
Întrucât ultimul clasament e identic cu primul, putem spune că barajul a fost cam degeaba.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="clasament2") ==
