Lil' Jami

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.4s
Memory limit: 16M
PyPy 2 128M
PyPy 3 128M

Problem type
Vincent Massey SS - 2014 Senior Contest #1

Lil' Jami is playing with a set of N cups numbered 0, 1, \dots, N-1 and an infinite number of stones. Each cup initially has 0 stones in it. Since he has an infinite amount of free time, Lil' Jami plays a game where he repeatedly adds a stone to a cup. He does this k times.

Following this, there will be Q queries (1 \le Q \le 1\,000\,000) of the form a b (0 \le a \le b < N). For each query, find the sum of the stones in cups numbered a, a+1, \dots, b-1, b.

Input Specification

The first line will contain the integers N and K (1 \le N, K \le 1\,000\,000) separated by a space.
The next K lines will each contain a single integer k_i (0 \le k_i < N) meaning to add a stone to the cup with index k_i (for 0 \le i < N).
The next line will contain the single integer Q.
The next Q lines will contain two space-separated integers a and b.

Output Specification

For each query, print the sum of the number of stones in each of the cups in the range [a, b], inclusive.

Sample Input

5 3
0 2
2 4

Sample Output



There are no comments at the moment.