Fişierul intrare/ieşire:kth.in, kth.outSursăAlgoritmiada 2017, Runda Finala, Juniors
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test1 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Kth

Se da un vector V cu N elemente. Asupra acestui vector aplicam M operatii de 2 tipuri:

  • Operatia de tip 0: se da un interval [A, B] si un numar K. Sortam elementele din interval in ordine crescatoare dupa valoare, dupa care le inlocuim cu cea de a K-a valoare din acest interval.
  • Operatia de tip 1: se da un interval [A, B] si un numar K. Toate elementele din acest interval sunt inlocuite cu valoarea K

Sa se afiseze vectorul de N elemente la finalul celor M operatii.

Date de intrare

Fişierul de intrare kth.in va contine pe prima linie 2 numere naturale N si M. Pe a 2-a linie vor fi N numere naturale, reprezentand vectorul initial. Urmatoarele M linii descriu update-urile. Un update consta din 4 numere: tip_update, A, B si K

Date de ieşire

Fişierul de ieşire kth.out va contine N numere naturale aflate pe o singura linie, reprezentand vectorul V in urma celor M update-uri.

Restricţii

  • 1 ≤ N, M ≤ 100.000
  • 1 ≤ K ≤ B - A + 1 pentru operatiile de tip 0
  • Valorile initiale din vector, precum si valorile K de la operatiile de tip 1 vor fi cuprinse in intervalul [1, 100.000]

Exemplu

kth.inkth.out
5 3
1 3 2 3 4
0 2 4 2
0 4 5 2
1 3 4 10
1 3 10 10 4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?