← 返回题目列表

AtCoder · tessoku_book_fm

C15. 许多会议

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

配点: 1000 点

問題文

今天在 KYOPRO-MARKET Co., Ltd. N 会议已安排。i 第次会议时间 L_i 从 [秒] 开始,时间 结束于 R_i [秒]。 请输出以下有关

i=1, 2, 3, \cdots, N 问题的答案。

问题: 如果您一定要参加第
i 次会议,您最多可以参加多少次会议?
但是,会议可能会延长,因此两次出席的会议之间可能会有间隔。 您需要等待至少 K 秒。 对于

制約

  • 1 \leq N \leq 100000
  • 0 \leq K \leq 86400
  • 0 \leq L_i < R_i \leq 86400

入力

输入是按以下格式从标准输入给出的。

N
K
L_1 R_1
L_2 R_2
 :
L_N R_N

出力

请以整数形式输出答案。


入力例 1

5
0
0 4
1 2
3 7
5 9
7 8

出力例 1

2
3
3
2
3

每个 对于 i ,最佳会议出席方法的示例如下。

  • i=1 :会议 参加 1, 4 。
  • i=2 :会议 参加 2, 3, 5 。
  • i=3 :会议 参加 2, 3, 5 。
  • i=4 :会议 参加 1, 4 。
  • i=5 :会议 参加 2, 3, 5 。

入力例 2

9
1000
0 1000
1000 2000
2000 3000
3000 4000
4000 5000
5000 6000
6000 7000
7000 8000
8000 9000

出力例 2

5
4
5
4
5
4
5
4
5

会议之间 请注意,您必须等待至少 K=1000 秒。