Ganesh: Problem Description: Krish loves chocolates very much. He has N containers

Question

Ganesh: Problem Description: Krish loves chocolates very much. He has N containers

numbered from 1 to N.Everyday, he used to select two indices [l,r] and adds 1 chocolate to each box starting from l to r (both inclusive).He repeats the same activity for M days.

After M days, he asked his friend Nakshatra Q queries. Each query can be described as: How many containers have atleast K chocolates.
Help Nakshatra to answer these queries.

Input Format:
First line contains an integer N that denotes the number of containers.
Second line contains an integer M denoting the number of days.
Each of the next M lines consists of two space separated integers l and r.
Followed by an integer Q denoting the number of queries.
Each of next Q lines contain a single integer K.

Output Format:
For each query, print the result in new line.

Constraints:
1 <= N <= 100000
1 <= M <= 1000
1 <= l <= r <= N
1 <= Q <= 100000
1 <= K <= N
Example:
Input:
7
4
1 3
2 5
1 2
5 6
4
1
7
4
2
Output:
6
0
0
4
Explanation:
Initially, as shown in the sample test case, we have 7 containers, so let's have an array of 7 integers initialized to 0 (consider 1-based indexing).

arr = [0,0,0,0,0,0,0]
After Day 1, arr becomes:
arr = [1,1,1,0,0,0,0]
After Day 2, arr becomes:
arr = [1,2,2,1,1,0,0]
After Day 3, arr becomes:
arr = [2,3,2,1,1,0,0]
After Day 4, arr becomes:
arr = [2,3,2,1,2,1,0]

Now, Krish asked 4 queries from his friend:
Query 1: How many containers have atleast 1 chocolate?
Ans 1: Containers 1,2,3,4,5 and 6 have atleast 1 chocolates in them. Hence, the output is 6.

Query 2: How many containers have atleast 7 chocolates?
Ans 2: We can see that there is no container which contains atleast 7 chocolates. Hence, the output is 0.

Query 3: Similar to Query 2.
Query 4: How many containers have atleast 2 chocolates?
Ans 4: Containers 1,2,3 and 5 have atleast 2 chocolates in them. Hence, the output is 4.

0

26.07.2018

1 ответов

5 просмотров

DarkLord · Answer 1

DarkLord Автор вопроса

How to solve this in order (n)?

0

26.07.2018

Похожие чаты

Ganesh: Problem Description: Krish loves chocolates very much. He has N containers

1 ответов

Похожие вопросы