#P3088. [USACO13NOV] Crowded Cows S

    ID: 2127 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2013USACO单调队列概率论,统计队列

[USACO13NOV] Crowded Cows S

Description

FJ 有 N(1N50000)N(1\le N\le50000) 头奶牛沿着一维的栅栏吃草,第 ii 头奶牛在目标点 xix_i ,它的身高是 hi(1xi,hi109)h_i (1 \le x_i,h_i\le10^9)

当一头奶牛左边 D(1D109)D(1\le D\le10^9) 距离内且右边 DD 距离内有身高至少是它的两倍的奶牛,它就会觉得拥挤。

请计算觉得拥挤的奶牛的数量。

Input Format

第一行两个整数 N,DN,D

接下来 NN 行,每行两个整数 xi,hix_i,h_i。保证 xix_i 互不相同。

Output Format

一行一个整数,表示觉得拥挤的奶牛的数量。

6 4 
10 3 
6 2 
5 3 
9 7 
3 6 
11 2 

2 

Hint

共有 66 头奶牛,拥挤感知距离为 4411 号奶牛位于位置 1010,身高为 33,依此类推。

位于位置 55 和位置 66 的两头奶牛处于拥挤状态。