Skip to content
Sign in

宣伝 2 (Advertisement 2)

Unrated
日本語

Language

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

Statement

JOI 国には \(N\) 人の住人がおり，\(1\) から \(N\) までの番号が付けられている． 住人 \(i\) (\(1 \leqq i \leqq N\)) は数直線上の座標 \(X_i\) に住んでおり，その影響力は \(E_i\) である．同じ座標に複数の住人が住んでいることもある． 影響力が高い住人ほど宣伝効果が大きい一方で，本を買うのに慎重になる．

理恵さんは情報科学の本を出版した．本を多くの人に買ってもらうため，何人かの住人に献本をすることができる． 住民 \(i\) (\(1 \leqq i \leqq N\)) に献本した場合，住人 \(i\) は理恵さんの本を手に入れる． さらに，まだ理恵さんの本を持っていない住人のうち，次の条件を満たすようなすべての住人 \(j\) (\(1 \leqq j \leqq N\)) は理恵さんの本を買って手に入れる．

  • 住人 \(i\) と住人 \(j\) との数直線上での距離が \(E_i - E_j\) 以下である．すなわち \(|X_i - X_j| \leqq E_i - E_j\) である．

もし理恵さんの本が JOI 国のすべての住人に読まれれば，情報オリンピックの知名度は大きく向上するだろう． JOI 国の住人全員が理恵さんの本を手に入れるために，最小で何人に献本する必要があるかを求めるプログラムを作成せよ．

Input

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

\(N\)
\(X_1\) \(E_1\)
\(X_2\) \(E_2\)
\(\vdots\)
\(X_N\) \(E_N\)

Output

標準出力に，理恵さんが献本すべき住人の人数の最小値を \(1\) 行で出力せよ．

Constraints

  • \(1 \leqq N \leqq 500\,000\)．
  • \(1 \leqq X_i \leqq 10^9\) (\(1 \leqq i \leqq N\))．
  • \(1 \leqq E_i \leqq 10^9\) (\(1 \leqq i \leqq N\))．
  • 入力される値はすべて整数である．

Subtasks

  1. (\(10\) 点) \(E_1 = E_2 = \cdots = E_N\)．
  2. (\(23\) 点) \(N \leqq 16\)．
  3. (\(36\) 点) \(N \leqq 1\,000\)．
  4. (\(31\) 点) 追加の制約はない．

Examples

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

たとえば次のように献本すると，JOI 国の住人全員が理恵さんの本を手に入れることができる．

  • 住人 \(3\) に献本する．

    • \(|X_3 - X_1| = 1, E_3 - E_1 = 2\) より，住人 \(1\) は理恵さんの本を買って手に入れる．
    • \(|X_3 - X_2| = 1, E_3 - E_2 = 1\) より，住人 \(2\) は理恵さんの本を買って手に入れる．
    • \(|X_3 - X_4| = 3, E_3 - E_4 = -1\) より，住人 \(4\) は理恵さんの本を買わない．

    よって，住人 \(1, 2, 3\) が理恵さんの本を手に入れることになる．

  • 住人 \(4\) に献本する．住人 \(4\) 以外の住人はいずれも既に理恵さんの本を手に入れているので，これで JOI 国の住人全員が理恵さんの本を手に入れたことになる．

\(2\) 人未満への献本で JOI 国の住人全員が理恵さんの本を手に入れるようにすることはできないので，\(2\) を出力する．
この入力例は小課題 \(2, 3, 4\) の制約を満たす．

Sample input 2
3
7 10
10 10
7 10
Sample output 2
2

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

Sample input 3
10
31447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019
Sample output 3
5

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

Notes

JOI 2023 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source