← 返回题目列表

AtCoder · ijpc_silver

B. 银牌

中文机器翻译题面 查看原题

你在高中生国际比赛中与金牌失之交臂,回家后发现自己是一名正在参加考试的学生。但是,您需要 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 是用空格分隔的输出。