Fişierul intrare/ieşire:flower.in, flower.outSursăLot Râmnicu Vâlcea 2015 - Baraj 1 Seniori
AutorVlad GavrilaAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test5.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Flower

"He can call me a flower if he wants to... I don't mind... "
După ce au ajutat la gonirea spiriduşilor de praf, Henry şi Hetty şi-au găsit o slujbă care să le testeze cu adevărat talentul la curăţenie. Mai exact, ei s-au angajat la o fermă de sconcşi nou înfiinţată. Aceasta este formată iniţial din N cuşti goale, dispuse in linie. Pentru a începe activitatea de creştere a sconcşilor, ei vor avea de făcut M operaţii de forma:

1 cnr mnr pnr: Henry şi Hetty aduc cel de-al nr-ulea sconcs la fermă, pe care îl pun în cuşca cnr. Acest sconcs are are miros mnr si coeficient de pierdere al mirosului pnr.

2 l r: Henry şi Hetty trebuie să afle care este mirosul minim dintr-o cuşcă aflată în intervalul [l, r]. Mirosul dintr-o cuşcă y (1 ≤ y ≤ N) se defineşte ca fiind max(mx-p x|y-cx|), pentru 1 ≤ x ≤ nr, nr fiind numărul de sconcşi aduşi la fermă până la operaţia curentă.

Date de intrare

Pe prima linie a fişierului de intrare flower.in se vor afla două numere naturale N şi M, cu semnificaţia din enunţ. Pe următoarele M linii se vor afla descrierile celor M operaţii. Primul număr de pe fiecare linie, tip, semnifică tipul operaţiei. Dacă tip = 1, pe linia respectivă se vor mai afla trei numere naturale cnr, mnr, pnr semnificând faptul că al nr-ulea sconcs, adus în cuşca cnr, are miros mnr şi coeficient de pierdere al mirosului pnr. Dacă tip = 2, pe linia respectivă se vor mai afla două numere naturale l r, semnificând faptul că Henry şi Hetty trebuie să afle care este mirosul minim dintr-o cusca aflată în intervalul [l, r].

Date de ieşire

În fişierul de ieşire flower.out se vor afişa în ordine, câte unul pe linie, răspunsurile la operaţiile de tip 2 citite din fişierul de intrare.

Restricţii

  • 1 ≤ N ≤ 200 000
  • 1 ≤ M ≤ 500 000
  • 1 ≤ cx ≤ N, pentru fiecare operaţie de tip 1.
  • 1 ≤ mx, px ≤ 1 000 000 000, pentru fiecare operaţie de tip 1.
  • 1 ≤ l ≤ r ≤ N, pentru fiecare operaţie de tip 2.
  • Fiecare sconcs adus la fermă are un coeficient de pierdere al mirosului mai mare sau egal cu cel al sconcsului adus anterior. Cu alte cuvinte px ≤ px+1 pentru orice x, 1 ≤ x < nr.
  • Într-o cuşcă se pot afla mai mulţi sconcşi la un moment dat.
  • Răspunsul la fiecare operaţie de tip 2 va putea fi reprezentat ca un întreg pe 64 de biţi cu semn.
  • Răspunsul la o operaţie de tip 2 poate fi şi negativ.
  • Pentru 20% din teste N ≤ 1000 şi M ≤ 3000.

Exemplu

flower.inflower.outExplicatie
4 6
1 3 5 2
1 1 8 3
2 1 4
1 4 10 4
2 3 4
2 1 2
3
6
5
Cele 6 operaţii au următoarele semnificaţii:
1. Este adus în cuşca 3 un sconcs care are mirosul 5 şi coeficient de pierdere al mirosului 2.
2. Este adus în cuşca 1 un sconcs care are mirosul 8 şi coeficient de pierdere al mirosului 3.
3. Acum, cuşca cu miros minim din intervalul [1, 4] este cuşca 4, în care mirosul are valoarea 3.
4. Este adus în cuşca 4 un sconcs care are mirosul 10 şi coeficient de pierdere al mirosului 4.
5. Acum, cuşca cu miros minim din intervalul [3, 4] este cuşca 3, în care mirosul are valoarea 6.
6. Acum, cuşca cu miros minim din intervalul [1, 2] este cuşca 2, în care mirosul are valoarea 5.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?