Diferențe pentru problema/avioane între reviziile #5 si #11

avioane

Avioane

== include(page="template/taskheader" task_id="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 $Y[~1~], Y[~2~], ..., Y[~N~]$ (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 $Y[~i~], Y[~j~] >= Y[~P~] + 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.

Î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 $Y[~1~], Y[~2~],$ ..., $Y[~N~]$ (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 $Y[~i~], Y[~j~] >= Y[~P~] + 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 $Y[~P~]$), calculați numărul de zone de conflict care sunt vizibile la fiecare lansare.

h2. Restricții

* $1 ≤ N ≤ 1.000.000$
* $1 ≤ Q ≤ 1.000.000$

* $1 ≤ N ≤ 100.000$
* $1 ≤ Q ≤ 100.000$

* $0 ≤ Y[~i~]  ≤ 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

table(example).
|_. avioane.in |_. avioane.out |
| 5 4

  4 0 5 7 3
  3 2
  2 1
  4 1
  2 1000000000

4 0 5 7 3
3 2
2 1
4 1
2 1000000000

| 3

  1
  5
  5

1
5
5

|
h3. Explicație