/ Vijos / 题库 /

拥挤的奶牛

拥挤的奶牛

时间限制:1秒  内存限制:256M


【题目描述】

  FJ的 \(n\) 头奶牛在被放养在一维的牧场。第 \(i\) 头奶牛站在位置 \(x(i)\),并且 \(x(i)\) 处有一个高度值 \(h(i)\)。

  一头奶牛感觉到拥挤当且仅当它的左右两端都有一头奶牛所在的高度至少是它的 2 倍,且和它的距离最多为 \(D\)。尽管感到拥挤的奶牛会产生更少的牛奶,FJ还是想知道一共有多少头感到拥挤的奶牛。请你帮助他。

【输入格式】

  第一行:两个整数 \(n\) 和 \(D\)。
  第二行到第 \(n+1\) 行:每一行有两个数表示 \(x(i)\) 和 \(h(i)\)。

【输出格式】

  一个数 \(k\) 表示感到拥挤的奶牛的数量。

【输入输出样例】

 Input

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

 Output

2

【数据限制】

  \(100\%\) 的数据满足,\(1≤n≤50000\),\(1<=x(i),h(i)<=10^9\)。

【来源】

  Mr.he

信息

ID
1709
难度
(无)
分类
图结构 | 最短路差分约束数据结构 | 队列 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
1
上传者