P2058 [NOIP 2016 Junior] Harbor

NOIP 2016 Junior T3.

Xiao K is a customs officer at a harbor. Many ships arrive at the harbor every day, and there are usually many passengers on board from different countries. Xiao K is very interested in these ships that arrive at the harbor. He records every ship in chronological order. For the $i$-th arriving ship, he records its arrival time $t_i$ (in seconds), the number of passengers $k_i$, and the nationality of each passenger $x_{i,1}, x_{i,2}, \dots, x_{i,k_i}$. Xiao K has collected information about $n$ ships. Please help him compute, for each ship’s arrival time, how many distinct countries the passengers come from among all ships that arrived within the last $24$ hours ($24$ hours $= 86400$ seconds), up to and including that time. Formally, you need to compute $n$ values. For the $i$-th output, consider all ships $p$ satisfying $t_i - 86400 < t_p \le t_i$. Among all $x_{p,j}$ in these ships, count how many distinct values there are.

The first line contains a positive integer $n$, indicating that Xiao K recorded information about $n$ ships. Each of the next $n$ lines describes one ship: the first two integers $t_i$ and $k_i$ denote the ship’s arrival time and the number of passengers on board, followed by $k_i$ integers $x_{i,j}$, which are the nationalities of the passengers. It is guaranteed that the $t_i$ are nondecreasing, measured in seconds. Counting from when Xiao K first started working, the $i$-th ship arrives at second $t_i$. It is guaranteed that $1 \le n \le 10^5$, $\sum k_i \le 3 \times 10^5$, $1 \le x_{i,j} \le 10^5$, $1 \le t_{i-1} \le t_i \le 10^9$. Here, $\sum k_i$ denotes the sum of all $k_i$.

Output $n$ lines. On the $i$-th line, output one integer: the required statistic after the $i$-th ship arrives.

Sample Explanation 1: The first ship arrives at second $1$. The ships that arrived in the last $24$ hours are just the first ship, with $4$ passengers from countries $4, 1, 2, 2$, for a total of $3$ distinct countries. The second ship arrives at second $2$. The ships that arrived in the last $24$ hours are the first and second ships, with $4 + 2 = 6$ passengers from countries $4, 1, 2, 2, 2, 3$, for a total of $4$ distinct countries. The third ship arrives at second $10$. The ships that arrived in the last $24$ hours are the first, second, and third ships, with $4 + 2 + 1 = 7$ passengers from countries $4, 1, 2, 2, 2, 3, 3$, for a total of $4$ distinct countries. Sample Explanation 2: The first ship arrives at second $1$. The ships that arrived in the last $24$ hours are just the first ship, with $4$ passengers from countries $1, 2, 2, 3$, for a total of $3$ distinct countries. The second ship arrives at second $3$. The ships that arrived in the last $24$ hours are the first and second ships, with $4 + 2 = 6$ passengers from countries $1, 2, 2, 3, 2, 3$, for a total of $3$ distinct countries. The third ship arrives at second $86401$. The ships that arrived in the last $24$ hours are the second and third ships, with $2 + 2 = 4$ passengers from countries $2, 3, 3, 4$, for a total of $3$ distinct countries. The fourth ship arrives at second $86402$. The ships that arrived in the last $24$ hours are the second, third, and fourth ships, with $2 + 2 + 1 = 5$ passengers from countries $2, 3, 3, 4, 5$, for a total of $4$ distinct countries. Constraints - For $10\%$ of the test points, $n = 1, \sum k_i \leq 10, 1 \leq x_{i,j} \leq 10, 1 \leq t_i \leq 10$. - For $20\%$ of the test points, $1 \leq n \leq 10, \sum k_i \leq 100, 1 \leq x_{i,j} \leq 100, 1 \leq t_i \leq 32767$. - For $40\%$ of the test points, $1 \leq n \leq 100, \sum k_i \leq 100, 1 \leq x_{i,j} \leq 100, 1 \leq t_i \leq 86400$. - For $70\%$ of the test points, $1 \leq n \leq 1000, \sum k_i \leq 3000, 1 \leq x_{i,j} \leq 1000, 1 \leq t_i \leq 10^9$. - For $100\%$ of the test points, $1 \leq n \leq 10^5, \sum k_i \leq 3 \times 10^5, 1 \leq x_{i,j} \leq 10^5, 1 \leq t_i \leq 10^9$. Translated by ChatGPT 5