Skip to content
Sign in

イベント巡り (Event Hopping)

Unrated
日本語

Language

Contribute a translation
Time limit
1500 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

IOI 国には \(2\) 個の町があり，それぞれ \(1, 2\) と番号がついている．

これらの町では合計 \(N\) 個のイベントが行われる．これらのイベントには \(1\) から \(N\) までの番号がついている．イベント \(i\) (\(1 \leqq i \leqq N\)) は町 \(P_i\) で開催され，開催時刻は時刻 \(S_i + 0.1\) から時刻 \(S_i + 0.9\) までである．ここで \(S_i\) は整数である．JOI 君がイベント \(i\) に参加するためには，時刻 \(S_i + 0.1\) から時刻 \(S_i + 0.9\) までの間，ずっと町 \(P_i\) にいる必要がある．

JOI 君はイベント巡りを行うことにした．イベント巡りではいくつかのイベントに参加し，必要ならば町と町の間を移動することもできる．JOI 君は時刻 \(0\) からイベント巡りを開始する．このとき，好きな町から始めることができる．

JOI 君は町 \(1\) と町 \(2\) の間を双方向に移動することができる．\(2\) つの町の間を移動するのにかかる時間は，JOI 君がその移動を開始する時刻までに参加したイベントの数を \(j\) として，\(D + K \times j\) となる．

イベントと町の間の移動に関する情報が与えられるので，JOI 君が参加できるイベントの数の最大値を求めるプログラムを作成せよ．

Constraints

  • \(1 \leqq N \leqq 200\,000\)．
  • \(1 \leqq D \leqq 10^{12}\)．
  • \(0 \leqq K \leqq 10^{12}\)．
  • \(1 \leqq P_i \leqq 2\) (\(1 \leqq i \leqq N\))．
  • \(1 \leqq S_i \leqq 10^{12}\) (\(1 \leqq i \leqq N\))．
  • \(S_i \neq S_j\) (\(1 \leqq i < j \leqq N\))．
  • 入力される値はすべて整数である．

Subtasks

  1. (\(8\) 点) \(K = 0\)，\(N \leqq 20\)．
  2. (\(11\) 点) \(K = 0\)，\(N \leqq 4\,000\)．
  3. (\(24\) 点) \(K = 0\)．
  4. (\(12\) 点) \(N \leqq 160\)．
  5. (\(23\) 点) \(N \leqq 4\,000\)．
  6. (\(22\) 点) 追加の制約はない．

Input

入力は以下の形式で標準入力から与えられる．

\(N\) \(D\) \(K\)
\(P_1\) \(S_1\)
\(P_2\) \(S_2\)
\(\vdots\)
\(P_N\) \(S_N\)

Output

標準出力に，JOI 君が参加することのできるイベントの数の最大値を \(1\) 行で出力せよ．

Examples

Sample input 1
5 3 0
1 1
1 2
1 10
2 5
2 6
Sample output 1
4

例えば，以下のように行動することで，JOI 君は \(4\) 個のイベントに参加することができる．

  1. 時刻 \(0\) において JOI 君は町 \(1\) にいる．
  2. 時刻 \(1.1\) から時刻 \(1.9\) まで町 \(1\) でイベント \(1\) に参加する．
  3. 時刻 \(2.1\) から時刻 \(2.9\) まで町 \(1\) でイベント \(2\) に参加する．
  4. 時刻 \(3\) から時刻 \(6\) まで時間 \(3\) (\(= D + K \times 2\)) をかけて町 \(1\) から町 \(2\) に移動する．
  5. 時刻 \(6.1\) から時刻 \(6.9\) まで町 \(2\) でイベント \(5\) に参加する．
  6. 時刻 \(7\) から時刻 \(10\) まで時間 \(3\) (\(= D + K \times 3\)) をかけて町 \(2\) から町 \(1\) に移動する．
  7. 時刻 \(10.1\) から時刻 \(10.9\) まで町 \(1\) でイベント \(3\) に参加する．

どのように行動しても \(5\) 個以上のイベントに参加することはできないため，\(4\) を出力する．

この入力例はすべての小課題の制約を満たす．

Sample input 2
7 2 3
2 2
1 8
1 10
1 11
2 23
2 24
2 25
Sample output 2
6

例えば，以下のように行動することで，JOI 君は \(6\) 個のイベントに参加することができる．

  1. 時刻 \(0\) において JOI 君は町 \(2\) にいる．
  2. 時刻 \(2.1\) から時刻 \(2.9\) まで町 \(2\) でイベント \(1\) に参加する．
  3. 時刻 \(3\) から時刻 \(8\) まで時間 \(5\) (\(= D + K \times 1\)) をかけて町 \(2\) から町 \(1\) に移動する．
  4. 時刻 \(8.1\) から時刻 \(8.9\) まで町 \(1\) でイベント \(2\) に参加する．
  5. 時刻 \(11.1\) から時刻 \(11.9\) まで町 \(1\) でイベント \(4\) に参加する．
  6. 時刻 \(12\) から時刻 \(23\) まで時間 \(11\) (\(= D + K \times 3\)) をかけて町 \(1\) から町 \(2\) に移動する．
  7. 時刻 \(23.1\) から時刻 \(23.9\) まで町 \(2\) でイベント \(5\) に参加する．
  8. 時刻 \(24.1\) から時刻 \(24.9\) まで町 \(2\) でイベント \(6\) に参加する．
  9. 時刻 \(25.1\) から時刻 \(25.9\) まで町 \(2\) でイベント \(7\) に参加する．

どのように行動しても \(7\) 個以上のイベントに参加することはできないため，\(6\) を出力する．

この入力例は小課題 \(4, 5, 6\) の制約を満たす．

Sample input 3
12 153 0
1 155
2 861
1 646
1 218
2 450
2 56
1 932
2 295
2 863
1 612
2 38
2 768
Sample output 3
8

この入力例はすべての小課題の制約を満たす．

Sample input 4
15 89 104
1 4379
1 738
1 4862
1 4236
2 1416
1 9905
1 4775
2 4574
2 439
1 3956
1 955
2 8862
2 801
2 2299
2 575
Sample output 4
11

この入力例は小課題 \(4, 5, 6\) の制約を満たす．

Notes

JOI 2021 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source