| Fișierul intrare/ieșire | avioane.in, avioane.out | Sursă | Cerc informatică Vianu |
|---|---|---|---|
| Autor | Cătălin Frâncu | Cristian Frâncu | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 0.4 sec | Limită de memorie | 4096 KB |
| Scorul tău | N/A | Dificultate |
  4
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile 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.
