// 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)). // #include #include using namespace std; const int MAXN = 100100; const int MAXP = 100100; int n; int num_chegada[MAXP]; // quantos onibus chegam nesse momento int num_partida[MAXP]; // quantos saem int min_num_vagas() { int intervalos_ativos = 0; int max_intervalos_ativos = 0; for (int x = 0; x < MAXP; x++) { intervalos_ativos += num_chegada[x] - num_partida[x]; max_intervalos_ativos = max(max_intervalos_ativos, intervalos_ativos); } return max_intervalos_ativos; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { int chegada, partida; scanf("%d %d", &chegada, &partida); num_chegada[chegada]++; num_partida[partida]++; } int resp = 20 * min_num_vagas(); printf("%d\n", resp); return 0; }