Vincent Massey SS - 2014 Senior Contest #1
Problem B: Lil' Jami
Lil' Jami is playing with a set of N cups numbered 0, 1, …, 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 ≤ Q ≤ 1,000,000) of the form "
a b" (0 ≤ a ≤ b < N). For each query, find the sum of the stones in cups numbered a, a+1, …, b−1, b.
The first line will contain the integers N and K (1 ≤ N, K ≤ 1,000,000) separated by a space.
The next K lines will each contain a single integer ki (0 ≤ ki < N) meaning to add a stone to the cup with index ki (for 0 ≤ i < N).
The next line will contain the single integer Q.
The next Q lines will contain two space-separated integers a and b.
For each query, print the sum of the number of stones in each of the cups in the range [a, b], inclusive.
5 3 1 1 2 2 0 2 2 4
Point Value: 7
Time Limit: 3.00s
Memory Limit: 16M
Added: Nov 04, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3