TSSPC Contest 1 P3 - Candy Machine

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

After going out to trick or treat, Adam's plan for getting candies has worked wonderfully! Now he has an abundance of candies, but needs a machine to count these candies. Being very picky, he wants the machine to be able to answer queries about his candies.

Given N candies, each with a value v_i, the machine must be able to answer queries about his candies, Q times.

Each query consists of a range (1 \le l_i \le r_i \le N), you are to find the sum of all the values within the range, inclusive.

Input Specification

The first line will contain the integers N and Q. (1 \le N, Q \le 100\,000)

The following N lines will contain the values of each candy.

The next Q lines after that will consist of the integers l_i and r_i, the leftmost and rightmost index of each query.

Output Specification

For each query, output the sum of the values on a separate line.

Sample Input

Copy
5 4
8
10
123
1
999
1 3
2 4
1 5
5 5

Sample Output

Copy
141
134
1141
999

Comments

There are no comments at the moment.