Fişierul intrare/ieşire:avioane.in, avioane.outSursăCerc informatică Vianu
AutorCatalin Francu, Cristian FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.4 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inavioane.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici