28a Olimpíada Brasileira de Informática
Submeta sua solução

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.
Para organizar o estacionamento, cada escola que chega de ônibus deve informar o horário de chegada e o horário de partida de seu ônibus, e os horários devem ser obedecidos rigorosamente. Dessa forma, o espaço de um ônibus que já partiu pode ser reutilizado por um outro ônibus que chega. Dados os horários em que cada ônibus chega e parte, escreva um programa para calcular o menor espaço possível, em metros, que deve ser reservado para que todos os ônibus estacionem.

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.
Seu programa pode resolver corretamente todas ou algumas das subtarefas acima (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por qualquer uma das suas submissões.

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
Tarefas Programação Nível Júnior
Promoção
logo sbc
Patrocínio
Apoio
Coordenação