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.

Input Format

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 k_i (0 ≤ k_i < N) meaning to add a stone to the cup with index k_i (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.

Output Format

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
1
1
2
2
0 2
2 4

Sample Output

3
1

All Submissions
Best Solutions

Point Value: 7
Time Limit: 3.00s
Memory Limit: 16M
Added: Nov 04, 2014
Author: thorthugnasty

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Nope, too complicated, much simpler data structures can be used

i dont know cs help me

There are many great resources to get you started on this. Look into things like Codecademy to start off with. As you get more comfortable, you may find the USACO training pages helpful.

Is this question impossible for Java?

Nvm... Over complicated the question

Your solution has the wrong time complexity. There exists a better solution. (Consider the fact that people have solved this in Python, and you are using fast i/o methods)

I don't think so. Your method is too slow and not required considering that this is a static state question.

Definitely doable in java. I just did it.

I love how my python solution is ranked second.

if the c++ people used scanf that wouldnt be the case, but nice