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 \le i \le 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.

Implementation Details

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.

Example

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$.

Constraints

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

Sample Grader

The sample grader reads the input in the following format:

• line $1$: $N \; S \; Q$
• line $2 + i$ ($0 \le i \le N - 1$): $T[i] \; A[i][0] \; B[i][0] \; \ldots \; A[i][T[i] - 1] \; B[i][T[i] - 1]$
• line $2 + N + k$ ($0 \le k \le Q - 1$): $P$ for scenario $k$

The sample grader prints your answers in the following format:

• line $1 + k$ ($0 \le k \le Q - 1$): the return value of count_users for scenario $k$

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (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 \le i \le 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.

Implementation Details

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.

Example

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$.

Constraints

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

Sample Grader

The sample grader reads the input in the following format:

• line $1$: $N \; S \; Q$
• line $2 + i$ ($0 \le i \le N - 1$): $T[i] \; A[i][0] \; B[i][0] \; \ldots \; A[i][T[i] - 1] \; B[i][T[i] - 1]$
• line $2 + N + k$ ($0 \le k \le Q - 1$): $P$ for scenario $k$

The sample grader prints your answers in the following format:

• line $1 + k$ ($0 \le k \le Q - 1$): the return value of count_users for scenario $k$

Execution limits

Your solution will have 2.0 second(s) execution time and 2048 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "hoax.h"

#include <vector>

void init(int N, int S, std::vector<int> T,
          std::vector<std::vector<int>> A, std::vector<std::vector<int>> B) {

}

int count_users(int P) {
  return 0;
}

参考代码

#include "hoax.h"

#include <vector>

void init(int N, int S, std::vector<int> T,
          std::vector<std::vector<int>> A, std::vector<std::vector<int>> B) {

}

int count_users(int P) {
  return 0;
}

请将你的实现写入 submission.cpp（可沿用上面的框架与题目头文件）。判题时你的代码会与题目自带的 manager / grader 一起编译链接，并按题目规定的协议通信。

本题为交互题：你的程序需与题目自带的 manager 进程通信（按题目约定经标准输入输出或命名管道），无需自行读取测试数据。

由 manager 进程打印判定结果，无需自行写出答案。

include "hoax.h"

include <vector>

void init(int N, int S, std::vector<int> T,
std::vector<std::vector\<int>> A, std::vector<std::vector\<int>> B) {

}

int count_users(int P) {
return 0;
}