Este problema aborda a necessidade de processar informações de chegada de navios a um porto, focando na diversidade de nacionalidades dos passageiros dentro de uma janela de tempo específica. Para cada navio que chega, é preciso determinar quantas nacionalidades distintas de passageiros foram representadas nos navios que chegaram nas últimas 24 horas (86400 segundos).
Entrada
A entrada consiste em um inteiro n, indicando o número total de navios monitorados. Seguem-se n linhas, cada uma descrevendo um navio com seu tempo de chegada t (em segundos), o número de passageiros k e uma lista de k códigos de nacionalidade x<sub>i,j</sub>.
As informações dos navios são fornecidas em ordem crescente de tempo de chegada. As restrições de entrada são:
1 ≤ n ≤ 10<sup>5</sup>∑ k<sub>i</sub> ≤ 3 × 10<sup>5</sup>(soma do número de passageiros em todos os navios)1 ≤ x<sub>i,j</sub> ≤ 10<sup>5</sup>(código de nacionalidade)1 ≤ t<sub>i-1</sub> ≤ t<sub>i</sub> ≤ 10<sup>9</sup>(tempo de chegada, t0 é implícito como 0 ou 1)
Saída
Para cada navio registrado, a saída deve ser um único inteiro representando o número de nacionalidades únicas entre os passageiros de todos os navios que chegaram no intervalo de tempo (t - 86400, t], onde t é o tempo de chegada do navio atual.
Exemplo 1
Entrada
3
1 4 4 1 2 2
2 2 2 3
10 1 3
Saída
3
4
4
Explicação
- Navio 1 (t=1): Apenas este navio está no intervalo. Passageiros: {4, 1, 2, 2}. Nacionalidades únicas: {1, 2, 4}. Total: 3.
- Navio 2 (t=2): Navios no intervalo (t-86400, t] são o navio 1 (t=1) e o navio 2 (t=2). Passageiros: {4, 1, 2, 2} U {2, 3}. Nacionalidades únicas: {1, 2, 3, 4}. Total: 4.
- Navio 3 (t=10): Navios no intervalo (t-86400, t] são os navios 1, 2 e 3. Passageiros: {4, 1, 2, 2} U {2, 3} U {3}. Nacionalidades únicas: {1, 2, 3, 4}. Total: 4.
Exemplo 2
Entrada
4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5
Saída
3
3
3
4
Explicação
- Navio 1 (t=1): Apenas o navio 1 está no intervalo. Passageiros: {1, 2, 2, 3}. Nacionalidades únicas: {1, 2, 3}. Total: 3.
- Navio 2 (t=3): Navios 1 (t=1) e 2 (t=3) estão no intervalo. Passageiros: {1, 2, 2, 3} U {2, 3}. Nacionalidades únicas: {1, 2, 3}. Total: 3.
- Navio 3 (t=86401): Navios no intervalo (t-86400, t] são o navio 2 (t=3) e o navio 3 (t=86401). O navio 1 (t=1) está fora, pois 86401 - 1 = 86400, que não é estritamente menor que 86400. Passageiros: {2, 3} U {3, 4}. Nacionalidades únicas: {2, 3, 4}. Total: 3.
- Navio 4 (t=86402): Navios no intervalo (t-86400, t] são os navios 2 (t=3), 3 (t=86401) e 4 (t=86402). O navio 1 (t=1) ainda está fora. Passgaeiros: {2, 3} U {3, 4} U {5}. Nacionalidades únicas: {2, 3, 4, 5}. Total: 4.
Implementação Eficiente
Para resolver este problema eficientemente, podemos utilizar uma estrutura de dados que gerencie os passageiros dantro da janela de 24 horas. Uma fila (queue) é adequada para manter os navios e passageiros que ainda estão dentro do período de interesse, enquanto um array ou mapa pode rastrear a contagem de cada nacionalidade presente.
À medida que cada novo navio chega:
- Adicione todos os passageiros do novo navio à estrutura de acompanhamento. Atualize a contagem de nacionalidades únicas.
- Remova os navios mais antigos da estrutura que excedem o limite de 86400 segundos em relação ao tempo do navio atual. Ao remover passageiros, atualize a contagem de nacionalidades únicas, decrementando a contagem se uma nacionalidade deixar de ter representantes.
- Registre a contagem atual de nacionalidades únicas para o navio que acabou de chegar.
Considerando as restrições de entrada, onde o tempo de chegada t pode ser grande, mas o número total de passageiros (∑ k<sub>i</sub>) e o número de nacionalidades (x<sub>i,j</sub>) são limitados, uma abordagem usando um array para contar nacionalidades (cntry) é viável, desde que o tamanho do array seja suficiente (até 105 + 1).
O uso de uma fila para armazenar os navios e seus passageiros permite a remoção eficiente dos elementos mais antigos. Cada elemento na fila pode ser uma estrutura contendo o tempo de chegada e a nacionalidade do passageiro.
Código de Exemplo (abordagem com fila e array de contagem):
#include <iostream>
#include <queue>
#include <vector>
#include <map> // Alternativa se o range de x for muito grande ou esparso
// Estrutura para armazenar informações do passageiro/navio
struct PassageiroInfo {
int tempoChegada;
int nacionalidade;
};
const int MAX_NACIONALIDADES = 100001; // Limite para o array de contagem
int contagemNacionalidades[MAX_NACIONALIDADES]; // Array para contar ocorrências de cada nacionalidade
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
std::cin >> n;
std::queue<PassageiroInfo> janelaTempo; // Fila para gerenciar passageiros na janela de 24h
int contadorNacionalidadesUnicas = 0;
int indiceNavioAtual = 0; // Para referência do tempo
// Armazenar informações dos navios para acesso posterior se necessário
std::vector<int> temposNavios(n);
std::vector<std::vector<int>> passageirosNavios(n);
for (int i = 0; i < n; ++i) {
int t, k;
std::cin >> t >> k;
temposNavios[i] = t;
passageirosNavios[i].resize(k);
// Processar passageiros do navio atual
for (int j = 0; j < k; ++j) {
int nacionalidade;
std::cin >> nacionalidade;
passageirosNavios[i][j] = nacionalidade;
// Adicionar à janela de tempo
janelaTempo.push({t, nacionalidade});
if (contagemNacionalidades[nacionalidade] == 0) {
contadorNacionalidadesUnicas++;
}
contagemNacionalidades[nacionalidade]++;
}
// Remover navios/passageiros antigos da janela
// Usamos o tempo do navio atual 't' para verificar a janela
while (!janelaTempo.empty() && (t - janelaTempo.front().tempoChegada) >= 86400) {
PassageiroInfo antigo = janelaTempo.front();
janelaTempo.pop();
contagemNacionalidades[antigo.nacionalidade]--;
if (contagemNacionalidades[antigo.nacionalidade] == 0) {
contadorNacionalidadesUnicas--;
}
}
// Imprimir o resultado para o navio atual
std::cout << contadorNacionalidadesUnicas << "\n";
}
return 0;
}
A segunda solução apresentada no problema original substitui a fila de estruturas por dois arrays paralelos (x para nacionalidades e y para tempos), simulando o comportamento da fila. Isso pode ser ligeiramente mais performático em C++ devido a overheads menores em comparação com a classe std::queue.
Código Alternativo (simulando fila com arrays):
#include <iostream>
#include <vector>
const int MAX_PASSAGEIROS_TOTAL = 300001; // Limite para o total de passageiros em todas as entradas
const int MAX_NACIONALIDADES = 100001;
int contagemNacionalidades[MAX_NACIONALIDADES];
int temposPassageiros[MAX_PASSAGEIROS_TOTAL];
int nacionalidadesPassageiros[MAX_PASSAGEIROS_TOTAL];
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
std::cin >> n;
int ponteiroEsquerda = 0; // Ponteiro para o início da janela de tempo (simula o front da queue)
int contadorNacionalidadesUnicas = 0;
int indiceAtualPassageiro = 0; // Índice para adicionar novos passageiros (simula o back da queue)
for (int i = 0; i < n; ++i) {
int t, k;
std::cin >> t >> k;
// Adicionar passageiros do navio atual
for (int j = 0; j < k; ++j) {
int nacionalidade;
std::cin >> nacionalidade;
indiceAtualPassageiro++; // Avança o índice para o próximo espaço
temposPassageiros[indiceAtualPassageiro] = t;
nacionalidadesPassageiros[indiceAtualPassageiro] = nacionalidade;
if (contagemNacionalidades[nacionalidade] == 0) {
contadorNacionalidadesUnicas++;
}
contagemNacionalidades[nacionalidade]++;
}
// Remover passageiros antigos da janela
// A condição é t - tempo_do_passageiro >= 86400
while (ponteiroEsquerda < indiceAtualPassageiro && (t - temposPassageiros[ponteiroEsquerda]) >= 86400) {
ponteiroEsquerda++; // Avança o ponteiro da esquerda, removendo o passageiro
if (--contagemNacionalidades[nacionalidadesPassageiros[ponteiroEsquerda]] == 0) {
contadorNacionalidadesUnicas--;
}
}
// Imprimir o resultado para o navio atual
std::cout << contadorNacionalidadesUnicas << "\n";
}
return 0;
}