Infoleague PreOJI 2023 9-10 | JumpSum

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

Cerință

Se dă un șir a1,a2,,ana_1, a_2, \dots, a_n.

Primiți qq întrebări de tipul x,yx, y. Pentru fiecare întrebare voi va trebui să afișați i=x,i=yi1ai\sum_{i=x,i-=y}^{i \ge 1} a_i. Mai exact, afișați ax+axy+ax2y++axkya_x + a_{x-y} + a_{x-2y} + \dots + a_{x-ky} cu kk maxim astfel încât xky>=1x-ky>=1 pentru fiecare întrebare.

Date de intrare

Se va citi nn urmat, pe a doua linie, de cele nn valori ale șirului. Pe a treia linie se află qq iar pe următoarele qq linii se vor afla câte 2 numere xx și yy cu semnificația din enunț.

Date de ieșire

Se vor afișa qq linii. Pe a ii-a linie se va afla răspunsul pentru întrebarea ii, în ordinea citirii.

Restricții și precizări

  • 1n,q1051 \le n, q \le 10^5;
  • 1x,yn1 \le x, y \le n, pentru fiecare qq;
  • 109ai109-10^9 \le a_i \le 10^9;
  • Pentru 2020 de puncte, 1n,q1031 \le n, q \le 10^3;
  • Pentru alte 2020 de puncte, 1y101 \le y \le 10, pentru fiecare qq.

Exemplu

stdin

8
3 2 -1 4 8 1 6 6
4
3 2
8 3
4 3
6 1

stdout

2
16
7
17

Explicatie

Pentru prima interogare se cere a3+a1a_3 + a_1.
Pentru a doua interogare se cere a8+a5+a2a_8 + a_5 + a_2.
Pentru a treia interogare se cere a4+a1a_4 + a_1.
Pentru a patra interogare se cere a6+a5+a4+a3+a2+a1a_6 + a_5 + a_4 + a_3 + a_2 + a_1.

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