Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | flower.in, flower.out | Sursă | Lot Râmnicu Vâlcea 2015 - Baraj 1 Seniori |
| Autor | Vlad Gavrila | Adăugată de |  Tatomir Alex •atatomir |
| Timp execuţie pe test | 5.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | flower.out | Explicatie |
|---|---|---|
| 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. |
