RoAlgo Educational Round #3 | mogger

This was the problem page during the contest. Access the current page here.
Time limit: 3s Memory limit: 256MB Input: Output:

Cerință

Pentru un vector AA cu NN numere se definește costul unui interval în felul următor:

int f(int l, int r){
	int cost = 0;
	for(int i = l; i <= r; i += A[i])
    	cost += A[i];
	return cost;
}

Se dă un vector PP cu NN elemente și un număr QQ, iar voi trebuie să răspundeți la QQ întrebări de forma: pentru ll și rr date (lrl \leq r) calculați i=lrf(i,r)\displaystyle \sum_{i=l}^{r} f(i,r).

Date de intrare

Pe prima linie se află NN și QQ, numărul de elemente din vector respectiv numărul de întrebări. Pe următoarea linie se află NN numere naturale separate prin câte un spațiu. Pe următoarele QQ linii se află exact 22 numere ( ll și rr ).

Date de ieșire

Pe fiecare dintre cele QQ linii se va afla răspunsul la întrebarea respectivă.

Restricții și precizări

  • 1N,Q21051 \leq N,Q \leq 2 \cdot 10^5
  • 1Ai301 \leq A_i \leq 30

Exemplul 1

stdin

10 6
6 2 3 3 3 6 4 6 3 2 
3 9
1 7
3 7
3 9
5 10
2 6

stdout

44
48
29
44
30
26

Exemplul 2

stdin

19 13
1 3 2 4 1 1 3 2 4 4 6 1 4 2 2 6 5 1 3 
5 14
4 9
4 16
5 9
6 8
8 10
4 4
1 7
2 9
2 18
7 8
9 9
10 17

stdout

69 //nice
24
131
18
9
14
4
40
39
201
5
4
68 //😩😩😩😩😩😩😩😩😩😩😩😩😩😩

Log in or sign up to be able to send submissions!