25435번 - Hoax Spreading 서브태스크다국어언어 제한함수 구현

문제

Pak Dengklek has just developed a social media site. There are $N$ users using the site, numbered 0ドル$ to $N - 1$. There are $S$ hours in one day. All of these users have a fixed usage schedule from day to day. For each $i$ such that 0ドル ≤ i ≤ N - 1,ドル user $i$ will be online $T[i]$ times every day:

• from the start of the $A[i][0]$^th hour to the end of the $B[i][0]$^th hour,
• from the start of the $A[i][1]$^th hour to the end of the $B[i][1]$^th hour
• ...
• and from the start of the $A[i][T[i] - 1]$^th hour to the end of the $B[i][T[i] - 1]$^th hour.

At any time, all users on the site like to share news to all other online users. Unfortunately, one of the $N$ users has a hoax at the start of the first day and will spread it. Hence, all users who meet the user with the hoax will also have the hoax at the end of the first day. Two users are stated to be met if there is at least an hour where the two users are both online.

This hoax will also be spread on the second day. Therefore, all users who meet the user with the hoax at the end of the first day will also have the hoax at the end of the second day. This continued the following days.

There are $Q$ scenarios, each can be represented as an integer $P$. For each scenario, the user who has the hoax at the start of the first day is user $P$. A different scenario might cause a different hoax spreading. Therefore, for each scenario, Pak Dengklek wonders on the number of users with the hoax at the end of the $N$^th day, where $N$ is the number of users.

구현

You should implement the following procedures:

void init(int N, int S, int[] T, int[][] A, int[][] B)

• $N$: the number of elements in the array $T,ドル $A,ドル and $B$.
• $S$: the number of hours in one day.
• $T$: an array of length $N$ describing the number of times each user will be online every day.
• $A,ドル $B$: arrays of length $N$. $A[i]$ and $B[i]$ are arrays of length $T[i]$ describing when user $i$ will be online every day.
• This procedure is called exactly once, before any calls to count_users.

int count_users(int P)

• $P$: the index of the user who has the hoax at the start of the first day.
• This procedure should return the number of users with the hoax at the end of the $N$^th day, where $N$ is the number of users.
• This procedure is called exactly $Q$ times.

예제

Consider the following sequence of calls:

init(5, 10, [2, 1, 1, 1, 1],
 [[2, 7], [1], [1], [9], [5]], [[4, 9], [3], [1], [10], [6]])

count_users(0)

This means user 0ドル$ has the hoax at the start of the first day. User 0ドル$ meets user 1ドル$ (at the second hour to the third hour) and user 3ドル$ (at the ninth hour). Therefore, at the end of the first day, the two users will have the hoax. User 1ドル$ also meets user 2ドル$ (at the first hour). Therefore, at the end of the second day, user 2ドル$ will also have the hoax. There will be no hoax spreading on the third, fourth, and fifth day, thus 4ドル$ users will have the hoax at the end of the fifth day. Therefore, the procedure should return 4ドル$.

count_users(4)

This means user 4ドル$ has the hoax at the start of the first day. User 4ドル$ does not meet other users, thus other users will not have the hoax. Therefore, the procedure should return 1ドル$.

입력

출력

제한

• 1ドル ≤ N ≤ 200,000円$
• $ 1 ≤ S ≤ 10^9$
• $ 1 ≤ Q ≤ 100,000円$
• $ 1 ≤ T[i] ≤ S$ (for each $i$ such that 0ドル ≤ i ≤ N - 1$)
• The sum of all elements of $T$ does not exceed 200ドル,000円$.
• 1ドル ≤ A[i][j] ≤ B[i][j] ≤ S$ (for each $i$ and $j$ such that 0ドル ≤ i ≤ N - 1$ and 0ドル ≤ j ≤ T[i] - 1$)
• $B[i][j - 1] < A[i][j]$ (for each $i$ and $j$ such that 0ドル ≤ i ≤ N - 1$ and 1ドル ≤ j ≤ T[i] - 1$)
• 0ドル ≤ P ≤ N - 1$
• The values of $P$ among all scenarios are pairwise distinct.

서브태스크

힌트

샘플 그레이더

The sample grader reads the input in the following format:

• line 1ドル$: $N$ $S$ $Q$
• line 2ドル + i$ (0ドル ≤ i ≤ N - 1$): $T[i]$ $A[i][0]$ $B[i][0]$ $\dots$ $A[i][T[i] - 1]$ $B[i][T[i] - 1]$
• line 2ドル + N + k$ (0ドル ≤ k ≤ Q - 1$): $P$ for scenario $k$

The sample grader prints your answers in the following format:

• line 1ドル + k$ (0ドル ≤ k ≤ Q - 1$): the return value of count_users for scenario $k$

첨부

• hoax.zip