Fişierul intrare/ieşire:clasament2.in, clasament2.outSursăLot Măgurele 2016 - Baraj 6 Seniori
AutorDenis-Gabriel MitaAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test7.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Clasament2

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.

Date de intrare

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.

Date de ieşire

În fişierul de ieşire clasament2.out se vor afişa M linii, pe fiecare linie fiind răspunsul cerut.

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

Exemplu

clasament2.inclasament2.outExplicatie
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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?