Skip to Content
CTRL K

Karen and Coffee

Editorial oficial 

Explicación

Para hallar cuántas temperaturas “buenas” para preparar café hay en un rango [a,b][a, b], empezamos por hallar qué temperaturas son recomendadas por al menos kk recetas. En lugar de chequear cada temperatura una por una, usamos un arreglo de diferencias para marcar rápidamente todas las temperaturas cubiertas por el rango de cada receta. Una vez procesados todos los rangos, usamos una suma de prefijos para contar cuántas recetas recomiendan cada temperatura. Si una temperatura es recomendada por al menos kk recetas, la llamamos “buena”. Finalmente, convertimos estas temperaturas “buenas” en un total acumulado, lo que nos permite responder al instante las consultas de Karen restando dos valores para cualquier rango [a,b][a, b].

Implementación

Complejidad temporal: O(N+Q)\mathcal{O}(N + Q)

#include <iostream>
#include <vector>
 
using std::cin;
using std::cout;
 
constexpr int MAX_TEMP = 200000;
 
int main() {
	int n, k, q;
	cin >> n >> k >> q;
 
	/*
	 * Hace falta +2 porque decrementamos r + 1 y el máximo r será 2e5,
	 * así se evitan errores de fuera de rango, y el +1 adicional asegura un
	 * cálculo seguro de la suma de prefijos.
	 */
	std::vector<int> diff_arr(MAX_TEMP + 2);
 
	for (int i = 0; i < n; i++) {
		int l, r;
		cin >> l >> r;
		diff_arr[l]++;
		diff_arr[r + 1]--;
	}
 
	for (int i = 1; i <= MAX_TEMP; i++) { diff_arr[i] += diff_arr[i - 1]; }
 
	for (int i = 1; i <= MAX_TEMP; i++) {
		diff_arr[i] = (diff_arr[i] >= k) + diff_arr[i - 1];
	}
 
	for (int i = 0; i < q; i++) {
		int a, b;
		cin >> a >> b;
		cout << diff_arr[b] - diff_arr[a - 1] << '\n';
	}
}
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();
 
		/*
		 * Hace falta +2 porque decrementamos r + 1 y el máximo r será 2e5,
		 * así se evitan errores de fuera de rango, y el +1 adicional asegura un
		 * cálculo seguro de la suma de prefijos.
		 */
		int[] diff_arr = new int[N + 2];
		for (int i = 0; i < n; i++) {
			int l, r;
			l = io.nextInt();
			r = io.nextInt();
			diff_arr[l]++;
			diff_arr[r + 1]--;
		}
 
		for (int i = 1; i <= MAX_TEMP; i++) { diff_arr[i] += diff_arr[i - 1]; }
 
		for (int i = 1; i <= MAX_TEMP; i++) {
			diff_arr[i] = (diff_arr[i] >= k ? 1 : 0) + diff_arr[i - 1];
		}
 
		for (int i = 0; i < q; i++) {
			int a, b;
			a = io.nextInt();
			b = io.nextInt();
			io.println(diff_arr[b] - diff_arr[a - 1]);
		}
		io.close();
	}
 
	// CodeSnip{Kattio}
}
MAX_TEMP = 200000
 
n, k, q = map(int, input().split())
 
"""
Hace falta +2 porque decrementamos r + 1 y el máximo r será 2e5,
así se evitan errores de fuera de rango, y el +1 adicional asegura un
cálculo seguro de la suma de prefijos.
"""
diff_arr = [0] * (MAX_TEMP + 2)
 
for _ in range(n):
	l, r = map(int, input().split())
	diff_arr[l] += 1
	diff_arr[r + 1] -= 1
 
for i in range(1, MAX_TEMP + 1):
	diff_arr[i] += diff_arr[i - 1]
 
for i in range(1, MAX_TEMP + 1):
	diff_arr[i] = (diff_arr[i] >= k) + diff_arr[i - 1]
 
for _ in range(q):
	a, b = map(int, input().split())
	print(diff_arr[b] - diff_arr[a - 1])
Fundamentos