| Fişierul intrare/ieşire: | avioane.in, avioane.out | Sursă | Cerc informatică Vianu |
| Autor | Catalin Francu, Cristian Francu | Adăugată de |  Catalin Francu •Catalin.Francu |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 4096 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Avioane
În nesfârşitul război dintre Agresivi şi Belicoşi, s-a ajuns ca luptele să se desfăşoare pe o linie a frontului, care este împărţită în N zone consecutive, aflate la înălţimile Y1, Y2, ..., YN (exprimate în metri). Agresivii au adoptat o nouă strategie: din anumite puncte P ale axei orizontale lansează avioane cu rolul de a culege informaţii despre zona de conflict. Fiecare avion se înalţă cu H metri faţă de punctul de lansare, apoi fotografiază toate zonele de luptă pe care le poate survola, menţinându-şi altitudinea constantă. Avionul poate zbura în stânga şi în dreapta până la cele mai apropiate zone i şi j de înălţimi Yi, Yj >= YP + H, unde se întoarce deoarece nu se poate înălţa. Dacă nu există o astfel de zonă într-una din direcţii, avionul poate zbura până la marginea frontului în acea direcţie.
Pentru a contracara avantajul tehnologic pe care îl au Agresivii, Belicoşii îşi doresc să afle cât mai rapid cât de multe zone de conflict poate vedea fiecare avion la lansare. Cunoscând atât harta liniei frontului (numărul zonelor de conflict şi înălţimea fiecăreia dintre acestea), cât şi numărul de lansări şi datele caracteristice fiecărei lansări (numărul de ordine P al zonei din care este lansat avionul şi înălţimea H la care acesta se înalţă, înălţime care se va adăuga la YP), calculaţi numărul de zone de conflict care sunt vizibile la fiecare lansare.
Date de intrare
Fişierul de intrare avioane.in conţine pe prima linie N = numărul de zone şi Q = numărul de lansări, separate printr-un spaţiu. Pe cea de-a doua linie se află N numere naturale, separate prin câte un spaţiu, reprezentând înălţimile Y1, Y2, ..., YN ale zonelor de luptă. Pe liniile 3, 4, ..., Q + 2 se află câte două numere naturale P şi H reprezentând poziţia şi respectiv înălţimea corespunzătoare fiecărei lansări.
Date de ieşire
Fişierul de ieşire avioane.out va conţine Q linii. Pe fiecare dintre acestea se va afla numărul de zone care pot fi văzute la lansarea corespunzătoare: pe linia 1 se va afla numărul de zone văzute de primul avion, pe linia 2 numărul de zone văzute de cel de-al doilea avion etc.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ Q ≤ 100.000
- 0 ≤ Yi ≤ 1.000.000.000, pentru fiecare 1 ≤ i ≤ N
- 1 ≤ P ≤ N pentru fiecare poziţie de lansare P
- 0 ≤ H ≤ 1.000.000.000 pentru fiecare înălţime la care va zbura un avion, înălţime calculată faţă de cea a punctului de lansare
Exemplu
| avioane.in | avioane.out |
|---|---|
| 5 4 4 0 5 7 3 3 2 2 1 4 1 2 1000000000 | 3 1 5 5 |
Explicaţie
Avionul lansat de pe poziţia 3 ajunge la înălţimea 5 + 2 = 7, de unde poate vedea zonele 1, 2, şi 3. El nu poate survola zona 4.
Al doilea avion, lansat de pe poziţia 2, ajunge la înălţimea 0 + 1 = 1, de unde nu vede decât zona 2.
Al treilea avion, lansat de pe poziţia 4, ajunge la înălţimea 7 + 1 = 8, de unde vede toate zonele.
Al patrulea avion, lansat de pe poziţia 2, ajunge la înălţimea 0 + 1000000000 = 1000000000, de unde vede toate zonele.
