Fişierul intrare/ieşire:vaporeon.in, vaporeon.outSursăLot Seniori Alexandria, 2017, baraj 6
AutorAdrian BudauAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1.5 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Vaporeon

Blanche, liderul echipei Mystic, a fost capturată de echipa Lacheta! Ea a fost adusă într-o bază a echipei care conţine N obstacole numerotate de la 1 la N, fiecare obstacol i având rezistenţa R[i]. Iniţial, Blanche este plasată în dreptul celui de-al x-lea obstacol. Încercând să scape, ea îl eliberează pe Vaporeon care distruge al x-lea obstacol şi capătă puterea de atac A egală cu R[x].
Pentru a evada, Vaporeon trebuie să distrugă toate obstacolele rămase. La un moment de timp la care Vaporeon a distrus toate obstacolele din intervalul [x, y], el poate executa exact una din mişcările:

  • Hydro Pump pe obstacolul x-1, dacă x-1 ≥ 1 şi R[x-1] ≤ A.
  • Hydro Pump pe obstacolul y+1, dacă y+1 ≤ N şi R[y+1] ≤ A.
  • Work Up, care creşte puterea de atac A la valoarea minimă dintre R[x-1] şi R[y+1]. Dacă doar unul din obstacole există, puterea de atac creşte la valoarea rezistenţei acestuia.

O mişcare Hydro Pump necesită efort 1, în timp ce o mişcare Work Up necesită efort K. Notăm cu E[x] efortul necesar evadării pornind din al x-lea obstacol. E[x] este egal cu suma minimă a eforturilor necesare pentru a distruge cele N obstacole, dacă Vaporeon a început din al x-lea obstacol.
Echipa Lacheta a anticipat această strategie, aşa că studiază diferite aranjamente ale obstacolelor, cât şi diferite poziţii în care să o plaseze iniţial pe Blanche. Ei vă vor da numărul de obstacole N, efortul K necesar unei mişcări şi rezistenţele celor N obstacole. Apoi, ei vă vor cere să efectuaţi următoarele operaţii:

  • Să schimbaţi două obstacole adiacente x şi x+1.
  • Să spuneţi, pentru doi indici x şi y, care este suma E[x] + E[x+1] + … + E[y] pentru aranjamentul actual al obstacolelor.

Date de intrare

Primul rând al fişierului de intrare vaporeon.in va conţine pe N şi K.
Următorul rând va conţine valorile lui R, separate prin câte un spaţiu.
Vor urma descrierile operaţiilor, una pe câte un rând. Daca P este răspunsul celei mai recente operaţii de al doilea tip (sau 0 dacă nu au fost încă astfel de operaţii), atunci operaţiile se vor codifica astfel:

  • 1 X reprezintă interschimbarea lui X xor P şi (X xor P) + 1
  • 2 X Y reprezintă o operaţie de găsire a sumei E[X xor P] + … + E[Y xor P]

Date de ieşire

Fişierul de ieşire vaporeon.out va conţine răspunsurile pentru toate operaţiile de al doilea tip, câte una pe un rând.

Restricţii şi precizări

  • 1 ≤ N ≤ 100.000
  • 1 ≤ K ≤ 1.000.000
  • 1 ≤ R[i] ≤ 1.000.000.000
  • Numărul total de operaţii este mai mic sau egal cu 200.000
  • Pentru 20% din teste, N ≤ 1.000 şi numărul total de apeluri la funcţiile exchange şi query nu depăşeşte 2.000.

Exemplu

vaporeon.invaporeon.out
5 3
2 3 1 4 1
2 2 2
2 6 2
1 36
2 36 36
2 12 8
7
38
13
41

Explicaţie

Operaţiile efectuate sunt:

  • Una de al doilea tip pentru a calcula E[2]
  • Una de al doilea tip pentru a calcula E[1] + E[2] + E[3] + E[4] + E[5]
  • Una de primul tip asupra lui 2
  • Una de al doilea tip pentru a calcula E[2]
  • Una de al doilea tip pentru a calcula E[1] + E[2] + E[3] + E[4] + E[5]
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?