Los regalos de Santa P23858


Statement
 

pdf   zip

thehtml

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≤ abN. 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 ‍
Public test cases
  • 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
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++