「CROI · R1」浣熊的语言

题目背景

$2023/08/17\ \ 21:44$ 本题时限改为 $500\ ms$。 > 他复瞑着,沙地上的文字。\ > 词句,日忆夜诵,挥翰成风;夜幕下,星罗棋布。\ > 新意,呼之欲出,似即却离;叹气里,功败垂成。\ > 她释然一笑,潇然起身,轻叩他的后背。\ > 却见流光间,熊爪翻飞;夜风中,新词真切。\ > “你做到了……”\ > 平凡的仲夏夜,深刻的文字。\ > 忆诵的努力,闪烁着星光……

题目描述

小浣熊 CleverRaccoon 遵循浣熊的单词遗忘曲线,从第 $1$ 天开始背单词。 一共有 $n$ 个单词,正常情况下,第 $i$ 个单词将在第 $d_i$ 天首次学习。 同时,每个单词都会安排 $k$ 次复习,对于第 $j$ 次复习有复习点 $t_j$,表示正常情况下,每个单词在**首次学习后** $t_j$ 天都会安排这个单词的复习。换言之,第 $i$ 个单词的第 $j$ 次复习时间为第 $d_i+t_j$ 天。 另外,还有 $m$ 天为特殊情况,第 $i$ 次特殊情况发生在 $s_i$ 天。小浣熊 CleverRaccoon 在当日忘记背单词了,与当日冲突的首次学习或复习时间将顺延至第二天学习或复习。 - 若某单词的首次学习时间顺延至第二天,则该单词按**顺延后**的首次学习时间安排复习。 - 若某单词的当次复习时间顺延至第二天,则**不影响**该单词的后续复习时间。 - 若多个学习或复习时间重合于一天,则当天需要进行**多次**学习或复习。 小浣熊 CleverRaccoon 想知道:学习和复习完所有单词需要的天数、每天新学单词数、每天复习单词数。

输入输出格式

输入格式


第一行,三个整数 $n,m,k$,表示需背单词的总数、特殊情况的天数、每个单词均需复习的次数。 第二行,$n$ 个整数 $d_i$,表示每个单词的首次学习时间。保证 $d$ 单调不减。 第三行,$m$ 个整数 $s_i$,表示特殊情况日期。保证 $s$ 单调递增。特别地,若 $m=0$,则没有该行数据。 第四行,$k$ 个整数 $t_i$,表示所有单词的每个复习点。保证 $t$ 单调递增。

输出格式


第一行,一个整数,表示小浣熊 CleverRaccoon 学习和复习完所有单词需要的天数 $x$。 接下来有 $x$ 行,每行两个整数,表示每天的学习单词数量和复习单词数量。

输入输出样例

输入样例 #1

5 0 2
1 1 1 2 3
1 2

输出样例 #1

5
3 0
1 3
1 4
0 2
0 1

输入样例 #2

5 1 2
1 1 1 2 3
1
1 2

输出样例 #2

5
0 0
4 0
1 4
0 5
0 1

输入样例 #3

5 1 3
1 2 3 4 5
3
1 2 3

输出样例 #3

8
1 0
1 1
0 0
2 4
1 3
0 3
0 3
0 1

说明

设依次输入的单词编号分别为 $1 \sim n$。 #### 样例解释 #1 | 天数 | 新学单词编号 | 新学单词数量 | 复习单词编号 | 复习单词数量 | | :-: | :-: | :-: | :-: | :-: | | $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$ | #### 样例解释 #2 | 天数 | 新学单词编号 | 新学单词数量 | 复习单词编号 | 复习单词数量 | | :-: | :-: | :-: | :-: | :-: | | $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$ | #### 样例解释 #3 | 天数 | 新学单词编号 | 新学单词数量 | 复习单词编号 | 复习单词数量 | | :-: | :-: | :-: | :-: | :-: | | $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$ | #### 数据范围 **本题采用 Subtask 捆绑测试。** 对于 $100\%$ 的数据,保证 $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$。保证 $d$ 单调不减,$t,s$ 单调递增。 |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$|