#! /usr/bin/env python3 # OBI 2023 - Fase 2 # UPA - Solução O(N + max(P_i)) usando vetor de marcação # Mateus Bezrutchka # Perceba que o problema é equivalente a, dados N intervalos na reta (o período # que cada ônibus ficará estacionado), calcular o número máximo de intervalos # que se intersectam -- podemos provar, via um argumento guloso, que se K é o # máximo de intervalos que se intersectam, então conseguimos estacionar todos os # ônibus usando K vagas, sempre alocando o ônibus que chega antes (intervalo mais # à esquerda) para qualquer vaga disponível. # Esse novo problema, dos intervalos que se intersectam, pode ser resolvido # processando os intervalos da esquerda para a direita e mantendo um contador # de intervalos ativos. Observe que, como o limite de C_i e P_i é somente 10^5, # podemos marcar esses intervalos em um vetor de marcação (ordenação ou sets não # são necessários) e iterar de 1 a 10^5 para obter uma solução O(N + max(P_i)). MAXP = int(1e5 + 1) def read_int_list(): return [int(x) for x in input().split()] n = int(input()) num_chegada = [0 for i in range(MAXP)] num_partida = [0 for i in range(MAXP)] for i in range(n): [chegada, partida] = read_int_list() num_chegada[chegada] += 1 num_partida[partida] += 1 intervalos_ativos = 0 max_intervalos_ativos = 0 for x in range(MAXP): intervalos_ativos += num_chegada[x] - num_partida[x] max_intervalos_ativos = max(max_intervalos_ativos, intervalos_ativos) resp = 20 * max_intervalos_ativos print(resp)