P9553 「CROI · R1」Raccoon’s Language.

$\texttt{[2023.08.17 21:44]：}$ To prevent some magical brute-force solutions from passing, the time limit of this problem has been changed to $500\ ms$. > He half-closes his eyes, reading the words on the sand.\ > Lines and phrases, recited day and night, his pen dancing like the wind; under the night, stars are scattered everywhere.\ > New ideas, about to emerge, so close yet slipping away; with a sigh, success falls short at the last moment.\ > She smiles in relief, stands up calmly, and lightly taps his back.\ > Then, in streaks of light, bear claws flutter; in the night wind, new words become clear.\ > “You did it……”\ > An ordinary midsummer night, profound words.\ > The effort of reciting, shimmering with starlight……

The little raccoon CleverRaccoon follows the raccoon word-forgetting curve and starts memorizing words from day $1$. There are $n$ words in total. Normally, the $i$-th word will be learned for the first time on day $d_i$. Meanwhile, each word is scheduled for $k$ reviews. For the $j$-th review, there is a review point $t_j$, meaning that normally, each word will be reviewed $t_j$ days **after its first learning**. In other words, the time of the $j$-th review for the $i$-th word is day $d_i + t_j$. In addition, there are $m$ days with special situations. The $i$-th special situation happens on day $s_i$. On that day, CleverRaccoon forgets to memorize words, and any first-learning or review schedule that conflicts with that day will be postponed to the next day. - If a word’s first-learning time is postponed to the next day, then the reviews of that word are arranged based on the **postponed** first-learning time. - If a word’s current review time is postponed to the next day, it **does not affect** the subsequent review times of that word. - If multiple learning or review events fall on the same day, then **multiple** learning or review actions must be done on that day. CleverRaccoon wants to know: the number of days needed to finish learning and reviewing all words, the number of new words learned each day, and the number of words reviewed each day.

The first line contains three integers $n, m, k$, representing the total number of words to memorize, the number of special-situation days, and the number of reviews required for each word. The second line contains $n$ integers $d_i$, representing the first-learning time of each word. It is guaranteed that $d$ is non-decreasing. The third line contains $m$ integers $s_i$, representing the dates of special situations. It is guaranteed that $s$ is strictly increasing. In particular, if $m = 0$, then this line does not exist. The fourth line contains $k$ integers $t_i$, representing each review point for all words. It is guaranteed that $t$ is strictly increasing.

The first line contains one integer, the number of days $x$ needed for CleverRaccoon to finish learning and reviewing all words. Then there are $x$ lines. Each line contains two integers, representing the number of words newly learned and the number of words reviewed on that day.

Assume that the word indices in the input order are $1 \sim n$. #### Sample Explanation #1 | Day | New word indices | Number of new words | Reviewed word indices | Number of reviewed words | | :-: | :-: | :-: | :-: | :-: | | $1$ | $1,2,3$ | $3$ | $-$ | $0$ | | $2$ | $4$ | $1$ | $1,2,3$ | $3$ | | $3$ | $5$ | $1$ | $1,2,3,4$ | $4$ | | $4$ | $-$ | $0$ | $4,5$ | $2$ | | $5$ | $-$ | $0$ | $5$ | $1$ | #### Sample Explanation #2 | Day | New word indices | Number of new words | Reviewed word indices | Number of reviewed words | | :-: | :-: | :-: | :-: | :-: | | $1$ (special) | $-$ | $0$ | $-$ | $0$ | | $2$ | $1,2,3,4$ | $4$ | $-$ | $0$ | | $3$ | $5$ | $1$ | $1,2,3,4$ | $4$ | | $4$ | $-$ | $0$ | $1,2,3,4,5$ | $5$ | | $5$ | $-$ | $0$ | $5$ | $1$ | #### Sample Explanation #3 | Day | New word indices | Number of new words | Reviewed word indices | Number of reviewed words | | :-: | :-: | :-: | :-: | :-: | | $1$ | $1$ | $1$ | $-$ | $0$ | | $2$ | $2$ | $1$ | $1$ | $1$ | | $3$ (special) | $-$ | $0$ | $-$ | $0$ | | $4$ | $3,4$ | $2$ | $1,1,2,2$ | $4$ | | $5$ | $5$ | $1$ | $2,3,4$ | $3$ | | $6$ | $-$ | $0$ | $3,4,5$ | $3$ | | $7$ | $-$ | $0$ | $3,4,5$ | $3$ | | $8$ | $-$ | $0$ | $5$ | $1$ | #### Constraints **This problem uses bundled Subtask testdata.** For $100\%$ of the data, it is guaranteed that $1 \leq n \leq 10^6$, $0 \leq m \leq 200$, $1 \leq k, d_i, t_i \leq 10^3$, $s_m < d_n$. It is guaranteed that $d$ is non-decreasing, and $t, s$ are strictly increasing. |Subtask|$n$|$m$|$k$|$d_i$|$t_i$|Score| |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$0$|$\leq 100$|$=0$|$\leq 10$|$\leq 100$|$\leq 100$|$5$| |$1$|$\leq 10^3$|$=0$|$\leq 100$|$\leq 10^3$|$\leq 100$|$20$| |$2$|$\leq 100$|$\leq 10$|$\leq 10$|$\leq 100$|$\leq 100$|$15$| |$3$|$\leq 10^3$|$\leq 100$|$\leq 100$|$\leq 10^3$|$\leq 100$|$25$| |$4$|$\leq 10^6$|$\leq 200$|$\leq 10^3$|$\leq 10^3$|$\leq 10^3$|$35$| Translated by ChatGPT 5