你在高中生国际比赛中与金牌失之交臂,回家后发现自己是一名正在参加考试的学生。但是,您需要 N 我没有做过任何类型的研究。
如果您以集中注意力的能力而闻名,那么连续进行每项研究将帮助您更加集中注意力。 我决定熬过 W 入学考试学习日。
在此期间您 我计划参加 N 模拟考试。
每次模拟考试都有它的日期和影响 d 已决定,将于开幕日期前后举行。 d 你知道不到1天的模拟考试吗?您当天知道的模拟考试数量将决定您的积极性水平。
i 研究不同类型 i 除非我有上述动机,否则我做不到。一天可以完成的学习次数没有限制,所以我想找出所有类型的学习可以连续学习的最大天数。
課題
W 白天 N 将进行模拟考试。用于模拟考试 0 从 N-1 它们使用不同的整数进行编号,最多为 。
每次模拟考试 i 是事件日期。 X[i] 和影响 D[i] 已确定。日期 t 加上 X[i]-D[i] < t < X[i]+D[i] 当且仅当 成立时,您才能得到一个日期 模拟考试时 t 我意识到 i 。
每天,你的学习动机就是你当天知道的模拟考试数量。
你应该学习的是 N 有不同的类型。为了学习 它们用不同的整数编号,最大为 1 从 N 。学习 k 只能靠你的动力来完成。 k 仅在这些天。
具有以下参数的过程 时间表(W、N、X、D) 实施 :
- W -- 入学考试学习天数。备考期间的每个日期都是 用小于0以上W的整数表示。
- N -- 模拟考试和学习的数量。用于模拟考试 0 从 N-1 它们使用不同的整数进行编号,最多为,用于学习 1 从 N 用不同的整数编号。
- X -- 表示模拟考试日期的整数数组。0 ≤ i < N 对于 反对 0 ≤ X[i] < W 可以假设为 。
- D -- 表示模拟考试影响力的整数数组。0 ≤ i < N 对于 反对 1 ≤ D[i] ≤ W 。X[i]-D[i] < 0 呀 如果显示 X[i]+D[i] ≧ W 可能会发生。
每项研究 您研究 k 计算 k 可以连续执行的最长时间。 答案(k, L, R) 致电 。L, R 研究每个 k 是可能发生的最长连续周期的第一天和最后一天。学习 如果您没有时间去做 k 如果没有可以做的日子 答案(k, 0, 0) 您必须致电 。如果有多个最大期限 必须选择 L 最小的一个。 答案(k, L, R) 致电 是什么? k 可以按该顺序调用,但每次研究都必须调用一次。
您一天内可以学习任意多种类型,因此您可以独立思考每个学习。即不同的 关于 k 的值,答案(k, L, R) 致电 的来电 由 L, R 表示的周期可以具有公共部分。
例
W = 10, N = 3,
| X = | 4 |
| 8 | |
| 3 |
| D = 考虑 | 2 |
| 4 | |
| 1 |
的情况。时间表 具有以下参数: 答案 必须调用 。 (不需要按此顺序调用它们。)
| 参数 |
| 答案(1,3,9) |
| 答案(2,3,3) |
| 答案(3, 0, 0) |
小課題
小課題 1 (10 点)
- 1 ≤ W ≤ 50
- 1 ≤ N ≤ 50
小課題 2 (19 点)
- 1 ≤ W ≤ 1 000
- 1 ≤ N ≤ 1 000
小課題 3 (71 点)
- 1 ≤ W ≤ 1 000 000 000
- 1 ≤ N ≤ 100 000
实施细节
制限
- CPU时间限制:1秒
- 内存限制:64 MB
注意: 堆栈的大小没有固定限制。作为堆栈使用的内存包含在总内存使用量中。
接口 (API)
- 实现文件夹:silver/(原型: 银.zip)
- 竞争对手实现的文件:或 silver.cpp
- 提交文件接口:silver.h
- 评分程序示例:grader.cpp
- 评分程序的示例输入:grader.in.1、grader.in.2、...
注意:示例评分程序按以下格式读取输入。- 1 行目: W, N 以空格分隔。
- 从第 2 行开始 N+1 对于 行目: 0 ≤ i < N 对于 ,i+2 在线 X[i] 和 D[i] 以空格分隔。
- 评分器输入样本的预期输出:grader.expect.1、grader.expect.2、...
注意:示例评分程序按以下格式写入输出。- 从第 1 行开始 N 行目: 1 ≤ k ≤ N ,k 学习中行 一个整数,表示可以执行 k 的最长时间。 L, R 是用空格分隔的输出。