Los regalos de Santa P23858
En Villabajo de Arriba hay una única calle, con viviendas numeradas del 1 al N. Cuando llega la Navidad, Santa hace k pasadas con su trineo por encima de la calle. En cada pasada, Santa cubre un intervalo de viviendas [a, b], tirando un regalo por la chimenea de cada vivienda del intervalo. Se te pide que digas el número máximo y mínimo de regalos que recibirán las viviendas, y el número de las viviendas que reciben más y menos regalos (en caso de haber más de una, escribe el número de la primera de ellas).
Entrada
La entrada contiene una cantidad arbitraria de casos. La primera línea de cada caso contiene los números N y k. La segunda línea contiene k intervalos [a, b], con números 1≤ a ≤ b≤ N. Los extremos a y b de los intervalos se separan con un espacio, mientras que dos intervalos consecutivos se separan con dos espacios.
Salida
Escribe tantas líneas como casos. Para cada caso, escribe cuatro números separados por espacios: la cantidad máxima y mínima de regalos que reciben las viviendas, y el (primer) número de la vivienda que recibe la máxima y la mínima cantidad de regalos.
Puntuación
- TestA: Entradas con un único caso donde N, k≤ 1000. 25 Puntos
- TestB: Entradas con no más de 100 casos donde N, k≤ 1000. 25 Puntos
- TestC: Entradas con no más de 3 casos donde N, k≤ 100000. 30 Puntos
- TestD: Entradas con no más de 3 casos donde N ≤ 109 y k≤ 100000. 20 Puntos
Input
10 3 1 4 3 6 8 10
Output
2 0 3 7
Input
500 0 500 1 10 20 500 2 10 20 1 500
Output
0 0 1 1 1 0 10 1 2 1 10 1
Input
100000 2 99999 99999 1 99998 100000 2 99999 99999 1 99999 100000 2 99999 99999 1 100000
Output
1 0 1 100000 2 0 99999 100000 2 1 99999 1
- Author
- Omer Giménez
- Language
- Spanish
- Official solutions
- C++
- User solutions
- C++