Official Analysis

Explanation

In order to find how many "good" coffee brewing temperatures are in a range $[a, b]$, we start by finding which temperatures are recommended by at least $k$ recipes. Instead of checking each temperature one by one, we use a difference array to quickly mark all temperatures covered by each recipe's range. Once we've processed all the ranges, we use a prefix sum to count how many recipes recommend each temperature. If a temperature is recommended by at least $k$ recipes, we call it "good". Finally, we convert these "good" temperatures into a running total, allowing us to instantly answer Karen's queries by subtracting two values for any range $[a, b]$.

Implementation

Time Complexity: $\mathcal{O}(N + Q)$

Copy
#include <iostream>
#include <vector>

using std::cin;
using std::cout;

constexpr int MAX_TEMP = 200000;

int main() {
	int n, k, q;

Copy
import java.io.*;
import java.util.*;

public class KarenAndCoffee {
	static int MAX_TEMP = 200000;
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int k = io.nextInt();
		int q = io.nextInt();

Copy
MAX_TEMP = 200000

n, k, q = map(int, input().split())

"""
+2 is required since we are decrementing r + 1 and max r will be 2e5
thus prevents out-of-bounds errors, and the additional +1 ensures safe
prefix sum computation.
"""
diff_arr = [0] * (MAX_TEMP + 2)