Fişierul intrare/ieşire:alambicare.in, alambicare.outSursăSummer Challenge 2019
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1.3 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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 va aplica Q operatii de cate 2 tipuri:

Formatul operatieiEfectul operatiei
1 st dr xAdaugam x la vst, ..., vdr
2 st drNe 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.inalambicare.out
5 3
1 2 3 4 5
1 3 3 -10
2 2 4
2 1 5
1
-1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?