This problem

Kalcor (188)
She knows n coffee recipes. The i-th recipe suggests that coffee should be brewed between li and ri degrees, inclusive, to achieve the optimal taste.

Karen thinks that a temperature is admissible if at least k recipes recommend it.

Karen has a rather fickle mind, and so she asks q questions. In each question, given that she only wants to prepare coffee with a temperature between a and b, inclusive, can you tell her how many admissible integer temperatures fall within the range?

Input
The first line of input contains three integers, n, k (1 ≤ k ≤ n ≤ 200000), and q (1 ≤ q ≤ 200000), the number of recipes, the minimum number of recipes a certain temperature must be recommended by to be admissible, and the number of questions Karen has, respectively.

The next n lines describe the recipes. Specifically, the i-th line among these contains two integers li and ri (1 ≤ li ≤ ri ≤ 200000), describing that the i-th recipe suggests that the coffee be brewed between li and ri degrees, inclusive.

The next q lines describe the questions. Each of these lines contains a and b, (1 ≤ a ≤ b ≤ 200000), describing that she wants to know the number of admissible integer temperatures between a and b degrees, inclusive.

Output
For each question, output a single integer on a line by itself, the number of admissible integer temperatures between a and b degrees, inclusive.

Examples
input
3 2 4
91 94
92 97
97 99
92 94
93 97
95 96
90 100
output
3
3
0
4
input
2 1 1
1 1
200000 200000
90 100
output
0
Note
In the first test case, Karen knows 3 recipes.

The first one recommends brewing the coffee between 91 and 94 degrees, inclusive.
The second one recommends brewing the coffee between 92 and 97 degrees, inclusive.
The third one recommends brewing the coffee between 97 and 99 degrees, inclusive.
A temperature is admissible if at least 2 recipes recommend it.

She asks 4 questions.

In her first question, she wants to know the number of admissible integer temperatures between 92 and 94 degrees, inclusive. There are 3: 92, 93 and 94 degrees are all admissible.

In her second question, she wants to know the number of admissible integer temperatures between 93 and 97 degrees, inclusive. There are 3: 93, 94 and 97 degrees are all admissible.

In her third question, she wants to know the number of admissible integer temperatures between 95 and 96 degrees, inclusive. There are none.

In her final question, she wants to know the number of admissible integer temperatures between 90 and 100 degrees, inclusive. There are 4: 92, 93, 94 and 97 degrees are all admissible.

In the second test case, Karen knows 2 recipes.

The first one, "wikiHow to make Cold Brew Coffee", recommends brewing the coffee at exactly 1 degree.
The second one, "What good is coffee that isn't brewed at at least 36.3306 times the temperature of the surface of the sun?", recommends brewing the coffee at exactly 200000 degrees.
A temperature is admissible if at least 1 recipe recommends it.

In her first and only question, she wants to know the number of admissible integer temperatures that are actually reasonable. There are none.



I solved it using a solution that exceeded time limit but when I went to search for a better way of solving it within the time limit, I found that "partial sums" solves it, I understand partial sums as a normal topic for finding partial sum in an array of integers for example but in this problem partial sum is used to calculate something else which I can't figure out, I was told there was a reference to such "thing" using this link : http://www.geeksforgeeks.org/maximum-occurred-integer-n-ranges/ but I didn't know what is the use of that link compared to the question and just overall got confused when I saw an actual submission to the problem but anyways..I'll post the solution hoping someone can explain what goes on in there, I traced it but it didn't help me spot what goes on , I mean I could figure it out only if I understand the use of having the weird use of "for i [ 1, n ] arr[a]++; arr[b+1]--" assuming a and b are integers to be read in and represent the temperatures. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
int a[2000009];
int main()
{
	file();
	fast();
	int n, k, q;
	cin >> n >> k >> q;
	for (int i = 0; i < n; i++){
		int l, r;
		cin >> l >> r;
		a[l]++;
		a[r + 1]+=-1;
	}
	for (int i = 1; i <= 200000; i++){
		a[i] += a[i - 1];
	}
	for (int i = 1; i <= 200000; i++){
		if (a[i] >= k){
			a[i] = 1;
		}
		else a[i] = 0;
	}
	for (int i = 1; i <= 200000; i++){
		a[i] += a[i - 1];
	}
	while (q--){
		int a1, b1;
		cin >> a1 >> b1;
		cout << a[b1] - a[a1 - 1] << endl;
	}
}


It looks simple but the idea behind it is just vague for me.
Kalcor (188)
Question link incase the quote up there is not clear: http://codeforces.com/problemset/problem/816/B
lastchance (6980)
Method: keep track of the steps in recipe-range temperatures and the cumulative sum of accepted temperatures. This eliminates the nesting of loops (and keeps it as an O(N) not O(N2) algorithm).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    const int SIZE = 200000;
    vector<int> step(2+SIZE,0);                  // step change in number of recipes at a given temperature (0 to SIZE+1 inclusive)
    vector<int> sumOk(1+SIZE);                   // number of acceptable temperatures up to this point

    int n, k, q;                                 // numbers of: recipes, minimum for admissability, questions
    int l, r;                                    // left and right bounds for recipes
    int a, b;                                    // bounds for questions

    // Read numbers
    cin >> n >> k >> q;

    // Set recipe limits by marking the step changes
    for ( int i = 0; i < n; i++ )
    {
       cin >> l >> r;
       step[l  ] += 1;                           // step change UP on passing left bound
       step[r+1] -= 1;                           // step change DOWN AFTER leaving right bound
    }

    // Cumulate the number of admissable temperatures up to a given point
    sumOk[0] = 0;
    int numIn = 0;
    for ( int i = 1; i <= SIZE; i++ ) 
    {
       numIn += step[i];                         // the number of recipes this temperature is in; found by accumulating steps
       sumOk[i] = sumOk[i-1] + ( numIn >= k );   // cumulative count of admissible temperatures up to here
    }

    // Now deal with individual questions
    for ( int i = 0; i < q; i++ ) 
    {
        cin >> a >> b;
        cout << sumOk[b] - sumOk[a-1] << '\n';       // the number of new admissible temperatures added in this interval
    }
}

Kalcor (188)
@lastchance I am still confused on why we increment and decrement when we are taking input I don't get the logic behind the increment and decrement moreover what does cumulative sum do here exactly? I still find these things vague for me :c sorryy
lastchance (6980)
@kalcor

To use an analogy - suppose you are walking along a level path punctuated by steps each 1 foot high. If on your walk you counted that at one position you had gone up 5 steps and down 2 steps then you would know that you were 5-2=3 feet higher than at the start. Thus if you keep track of steps up and steps down (or, in the problem, left and right boundaries of a recipe) then you will know your height (or how many recipes you are in).

When you need to get this number of recipes you can just count signed steps up to that point: line 31 in my code
numIn += step[i];

The number of admissible temperatures in a particular question range is just the number of admissible temperatures up to and including the end of the range minus the number at the temperature prior to the range; line 39 in my code:
cout << sumOk[b] - sumOk[a-1] << '\n';

Cumulative sum just means the number up to this point.

In the model answer they used a single array to do everything. I preferred to use two arrays because it was easier to see what was going on.

Keeping track of the step changes is faster because you only have to mark 2N things. Originally I tallied all temperatures in between, so requiring N (recipes) x order N (updates) - this would be much slower.

And, yes, I'm sad enough to have submitted my code to codeforces.com to check it was OK before I posted it here!

Kalcor (188)
@lastchance haha that last line xD

but why don't we just do a sumOk[b] - sumOk[a] ? why is it a-1 ? also i still don't know why we decrement the right side of it, i.e line 23. what if the right side is a legitimate number later on in the sequence didnt we just ruin its step[L] ? like for example

91 96
97 98
97 99

taking something like this we would say step[97]-- when we take in the first input then the total amount of times 97 appeared is 2 but in our step array it'll be just 1. or am I missing something?

Just pretty much confusing for me to get this part :
1
2
 
step[l  ] += 1;                           // step change UP on passing left bound
step[r+1] -= 1;                           // step change DOWN AFTER leaving right bound


Also sorry for the 5 days later reply
Last edited on
lastchance (6980)
but why don't we just do a sumOk[b] - sumOk[a] ?

No, you should do sumOk[b] - sumOk[a-1].
If you wanted the number of integers between 10 and 15 inclusive you would do 15-9, not 15-10.



i still don't know why we decrement the right side
step[r+1] -= 1
Step down ... so decrement.



what if the right side is a legitimate number later on in the sequence

I don't really understand what you are asking. step is counting the number of ... steps .. not the number of occurrences - that is done by sumOk.



Just pretty much confusing for me to get this part :
1
2
 
step[l  ] += 1;                           // step change UP on passing left bound
step[r+1] -= 1;                           // step change DOWN AFTER leaving right bound

Consider my previous analogy about walking along a path. You will be in an elevated position until you step down.

Try putting some numbers down on paper and following the contents of the arrays.



Last edited on
Kalcor (188)
@lastchance you're not quite getting what I mean, I was asking why we decrement r+1 in the step array, like taking this example

91 96

we do step[91]+= 1 and step[97] -= 1; why don't we do step[96]-=1 ? 96 should be our maximum range not 97.

for the 2nd question

Consider this case:

91 96
97 99
97 100

we do
step[91]+=1
step[97]-=1
step[97]+=1
step[97]+=1

now the total value for 97 in the step array will be 1 because it got incremented twice from being -1 after the first decrement, but the true value should be 2 though because it appeared twice in the input , right?
lastchance (6980)
Your first example:
T      90  91  92  93  94  95  96  97  98  99  100
After recipe 91 96 ...
Step    0   1   0   0   0   0   0  -1   0   0   0
numIn   0   1   1   1   1   1   1   0   0   0   0          <=== everything between 91 and 96 inclusive marked as 1



Your second example:
T      90  91  92  93  94  95  96  97  98  99  100  101
After recipe 91 96 ...
Step    0   1   0   0   0   0   0  -1   0   0   0    0
After recipe 97 99 ...
Step    0   1   0   0   0   0   0   0   0   0  -1    0
After recipe 97 100 ...
Step    0   1   0   0   0   0   0   1   0   0  -1   -1
numIn   0   1   1   1   1   1   1   2   2   2   1    0     <==== Number of recipes each temperature is in



(My last reply on the topic)
Kalcor (188)
Thanks that clarified it more to me!
Topic archived. No new replies allowed.