28a Olimpíada Brasileira de Informática
UPA
A Unicamp organiza anualmente, sempre em agosto, a UPA -- Unicamp Portas Abertas --, um evento em que alunos de escolas da região podem visitar e conhecer as atividades da Universidade. O evento recebe em um dia dezenas de milhares alunos, que chegam em ônibus. Um dos grandes problemas da organização da UPA é o estacionamento dos ônibus que trazem os alunos. A Unicamp reserva uma longa avenida para que os ônibus estacionem, um em seguida ao outro, todos paralelos à avenida; para cada ônibus são reservados 20 metros de avenida, com os espaços marcados no chão.
Entrada
A primeira linha contém um inteiro N, o número de ônibus que chegarão para a UPA. Os horários de chegada e partida são dados como números inteiros. Cada uma das N linhas seguintes descreve um ônibus e contém dois inteiros Ci e Pi, respectivamente o instante de chegada e o instante de partida do ônibus i. Dois ônibus A e B tais que CB ≥ PA ou CA ≥ PB podem utilizar o mesmo espaço de estacionamento. Assim, por exemplo, se o horário de chegada do ônibus B e a partida do ônibus A forem iguais, então o ônibus B pode ocupar o espaço que o ônibus A ocupou.Saída
Seu programa deve produzir uma única linha, contendo um único inteiro, o menor comprimento da avenida, em metros, que deve ser reservado para o estacionamento de ônibus.Restrições
- 1 ≤ N ≤ 100 000
- 0 ≤ Ci ≤ 100 000 para 1 ≤ i ≤ N
- 0 ≤ Pi ≤ 100 000 para 1 ≤ i ≤ N
- Ci < Pi para 1 ≤ i ≤ N
Informações sobre a pontuação
A tarefa vale 100 pontos. Os pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:- Subtarefa 1 (12 pontos): Pi = 1 + Ci para 1 ≤ i ≤ N
- Subtarefa 2 (29 pontos): N ≤ 1 000, Ci ≤ 1 000 e Pi ≤ 1 000.
- Subtarefa 3 (27 pontos): É garantido que a resposta é menor do que 1 000 metros.
- Subtarefa 4 (32 pontos): Nenhuma restrição adicional.
Exemplos
Entrada
3 100 360 300 500 200 400 |
Saída
60 |
Entrada
4 500 560 200 340 80 200 400 540 |
Saída
40 |
| PJ | P1 | P2 | PS |