| Fişierul intrare/ieşire: | alambicare.in, alambicare.out | Sursă | Summer Challenge 2019 |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.65 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Alambicare
Tanaka a inceput sa foloseasca un alambic pentru a distila niste lapte. Plictisindu-se, gaseste un lucru extraordinar pe care il poate face cu alambicul sau. Mai exact, pentru un sir de numere a1a2...an, el il poate imparti in 2 parti, cu putinta goale, b1...bk si c1...cn-k, le inverseaza, ele devenind bk...b1 si cn-k...c1, si le uneste, generand sirul bk...b1cn-k...c1. O astfel de operatie se numeste o alambicare.
Acum, varul sau, Uivlis, vrea sa foloseasca alambicul in scopuri ezoterice, pentru a sorta numere. Mai exact, Uivlis are un sir de N numere v1...vN, pe care va aplica Q operatii de cate 2 tipuri:
| Formatul operatiei | Efectul operatiei |
| 1 st dr x | Adaugam x la vst, ..., vdr |
| 2 st dr | Ne intrebam daca Tanaka poate sorta subsecventa vst, ..., vdr cu ajutorul alambicului sau. Daca poate, atunci vrem sa stim si numarul minim de alambicari de care este nevoie. |
Il puteti ajuta pe Uivlis ? Suntem siguri ca va va oferi 100 de puncte daca reusiti :)
Date de intrare
Fişierul de intrare alambicare.in va contine pe primul rand N si Q.
Pe cel de al doilea rand vor urma valorile initiale ale lui v, in ordine.
Pe urmatoarele Q randuri vom gasi operatiile lui Uivlis, in formatul din tabelul de mai sus.
Date de ieşire
În fişierul de ieşire alambicare.out se vor gasi raspunsurile pentru toate operatiile de tipul 2, cate unul pe un rand.
Randul unei interogarii pentru care nu este posibila sortarea va contine doar numarul -1.
Randul unei interogari pentru care este posibila sortarea va contine numarul de operatii folosite.
Restricţii
- 1 ≤ N ≤ 200.000
- 1 ≤ Q ≤ 200.000
- Pentru 10 puncte, N ≤ 20, Q ≤ 20.
- Pentru alte 10 puncte, N ≤ 1000, Q ≤ 1000.
- Pentru alte 30 puncte, sunt doar operatii de al 2-lea tip.
- Valorile lui v nu depasesc initial, ca valoare absoluta, 109.
- Valorile lui x nu depasesc 109 in valoare absoluta.
- Se recomanda consumul responsabil de lapte, si utilizarea alambicului doar de catre cei pregatiti corespunzator.
Exemplu
| alambicare.in | alambicare.out |
|---|---|
| 5 3 1 2 3 4 5 1 3 3 -10 2 2 4 2 1 5 | 1 -1 |
