#P6425. 「JOI 2023 Final」宣传 2

    ID: 5914 传统题 2000ms 1024MiB 尝试: 9 已通过: 6 难度: 5 上传者: 标签>CF1700普及+/提高-坐标变换支配关系消除被支配候选自定义排序规则前后缀最值

「JOI 2023 Final」宣传 2

题目描述

译自 JOI 2023 Final T2「宣伝 2 / Advertisement 2」

JOI 国有 NN 位居民,从 11 到 NN 编号。居民 i (1≤i≤N)i\ (1\le i\le N) 住在数轴的 XiX_i 位置,并且他的影响力是 EiE_i。

存在超过一位居民住在同一位置的情况。影响力大的居民有很高的宣传价值。但是这样的居民在买书方面十分小心。

理惠女士出版了一本信息学方面的书。为了鼓励人们买书,她可以把书送给一些居民。如果她送给居民 i (1≤i≤N)i\ (1\le i\le N) 一本书,那么居民 ii 就会收到这本书。此外,在目前没有这本书的居民中,所有满足如下条件的居民 j (1≤j≤N)j\ (1\le j\le N) 都会买这本书并得到它。

  • 居民 ii 和 jj 居住位置之间的距离小于等于 Ei−EjE_i-E_j。换句话说,需要满足 ∣Xi−Xj∣≤Ei−Ej|X_i-X_j|\le E_i-E_j。

如果所有的居民都读了理惠女士的书,那么信息学竞赛的知名度就会大幅上升。写一个程序计算最少要给多少居民送出书,才能使得 JOI 国的所有人都有一本理惠女士的书。

输入格式

第一行一个整数 NN。

接下来 NN 行,每行两个整数 Xi,EiX_i,E_i。

输出格式

输出一行一个整数,表示至少要给多少居民送书。

4
4 2
2 3
3 4
6 5
2
3
7 10
10 10
7 10
2
10
31447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019
5

数据范围与提示

对于全部数据,满足:

  • 1≤N≤5×1051\le N\le 5\times 10^5
  • 1≤Xi,Ei≤109 (1≤i≤N)1\le X_i,E_i\le 10^9\ (1\le i\le N)

详细附加限制及分值如下表所示。

子任务编号 附加限制 分值
11 E1=E2=…=ENE_1=E_2=\ldots=E_N 1010
22 N≤16N\le 16 2323
33 N≤1 000N\le 1\ 000 3636
44 无附加限制 3131