All Tracks>Problem
Bhairava, the warrior
★★★★★

0

0 votes
Problem

In the kingdom of Udaigarh, there lives a great warrior named Kala Bhairava. His swordsmanship skills are unparalleled. He is so strong that if he is defeated Udaigarh would surrender. Sher Khan, an enemy king wants to invade Udaigarh  and asks his minister to send "N" spies and find out how many troops are needed to defeat Bhairava.

Each spy gives a range Li   Ri  , The minimum and maximum size of army needed to defeat bhairava.

An army size (say P) is said to be strong if atleast K spies are in favour of it, i.e., there are atleast K values of i such that  Li  ≤  P  ≤  Ri 

Sher khan has Q questions for the minister. The ith question consists of 2 numbers Ai and Bi. The minister has to find out how many strong army sizes are present in the range [Ai , Bi].

INPUT FORMAT:

First line of input consists of 3 space-separated integers N,  K and Q 

The next  N lines contain 2 space-separated numbers, Li  and Ri 

The next  Q lines contain 2 space-separated numbers, Ai  and Bi 

OUTPUT FORMAT:

Output must contain Q lines. The ith line must contain the number of strong army sizes between Ai  and Bi  (inclusive).

CONSTRAINTS:

1 ≤ K ≤ N ≤ 200000 

1 ≤ Q ≤ 200000

1 ≤ Li  ≤  Ri ≤ 200000

1 ≤ Ai  ≤  Bi ≤ 200000

Sample Input
6 3 4
100 102
101 105
104 109
103 115
107 108
120 121
102 103
105 107
103 106
108 111
Sample Output
0
2
2
1
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

For the first query , 102-103, both are not strong army sizes as 102 is favored by only one report (101 105) and 103 by only 2 reports(101-105, 103-115).

In the second query, 105-107, 105 is a strong army size(104-109, 101-105, 103-115) and 107 is a strong army size (104-109, 107-108, 103-115).

In third query, 103-106 , 104 and 105 are strong army sizes (104-109, 101-105, 103-115).

In fourth query, 108-111, only 108 is strong(104-109, 107-108, 103-115). 

Editor Image

?