infinitywar

Infinitywar

Cele $N$ lumi sunt aranjate secvenţial: prima lume are indexul $1$, în timp ce ultima are indexul $N$.

!>problema/infinitywar?marvel.png!
 

h2. Cerinţă
Thanos este destul că sigur că poate câştiga războiul şi distruge universul, însă doreşte să se distreze în timp ce face asta. Aşadar, el a pregătit $Q$ întrebări. Pentru fiecare întrebare se dau doi indici $x$ şi $y$ şi trebuie găsit numărul de soldaţi care ar supravieţui bătăliei dintre armatele cu indicii $x$, $x+1$, $x+2$, ..., $y$.

h2. Date de ieşire

În fişierul de ieşire $infinitywar.out$ ...

Fişierul de ieşire $infinitywar.out$ trebuie să conţină $Q$ linii. Fiecare linie trebuie să conţină un singur număr, raspunul pentru întrebarea corespunzătoare.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 50.000$
* $1 ≤ P ≤ 10.000$
* $1 ≤ Q ≤ 100.000$
* $K{~1~} + K{~2~} + ... + K{~N~} ≤ 300.000$
* $1 ≤ x ≤ y ≤ N$ pentru fiecare întrebare.
* Pentru $30%$ dintre teste $N ≤ 10.000$, $P ≤ 500$ şi $Q ≤ 10.000$
* Pentru alte $40%$ dintre teste $P ≤ 5.000$ şi $Q ≤ 30.000$

h2. Exemplu
table(example). |_. infinitywar.in |_. infinitywar.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|4 3
2 1 2
3 1 3 97
2 1 341
5 4 2 981 341 97
1 3
2 4
1 4
|5
4
4

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="infinitywar") ==