题目背景
从中国古代开始,就有捕鱼的活动。捕鱼是一种古老的生产活动,是人类获取食物的重要手段之一。捕鱼的方法有很多种,有的人用渔网,有的人用鱼叉,有的人用捕鱼网,有的人用捕鱼笼。
渔民都是靠海为生,靠天吃饭。辛勤劳动的渔民也是中华儿女的一支重要力量,也体现了中华民族的伟大精神。
题目描述
小明的家乡有一条美丽的河,周围的人们都以养鱼、捕鱼为生。河中有许许多多的鱼,有的从左往右游,有的从右往左游,小明有一张渔网,但是他只有一次撒网的机会来捕鱼,因为撒网之后鱼就会被吓走。小明想一次性地捕到更多的鱼。
通过观察小明发现,目前河中一共有 n 条鱼, 在时刻 0,每一条鱼都有一个初始的位置 xi,并且有一个移动方向(向左或者向右)和游动速度 vi,小明的渔网布置在位置 [l,r] 的区域。换句话说,当他撒网时,范围 (l≤鱼位置≤r)中的鱼会被小明捕获。
小明可以选择在任一时刻 t (t≥0 且是整数) 撒网,请问小明最多能捕获多少条鱼?
输入格式
第一行一个整数 n,表示河中鱼的条数。
第二行一个整数 l,表示渔网的左边界。
第三行一个整数 r,表示渔网的右边界。
接下来的 3×n 行,每三行包含一条鱼的信息,具体信息如下:
第一行一个整数 xi,表示鱼的初始位置,
第二行一个整数 vi,表示鱼的游动速度,
第三行一个整数 di,表示鱼的移动方向,di=1 表示向左游,di=2 表示向右游。
输出格式
一行一个整数,表示小明最多能捕获鱼的条数。
样例数据
2
1
5
-1
3
2
6
2
1
2
样例解释 #1
小明可以选择在时刻 1 撒网,这时候第一条鱼在位置 −1+3=2,第二条鱼在位置 6−2=4,都处于范围 [1,5] 中,所以最多能捕获 2 条鱼。
1
-1
1
2
2
2
1
1
2
0
样例解释 #2
小明可以选择在时刻 0 撒网,这时候第一条鱼在位置 2+0=2,此时已经不在捕捞范围[−1,1] 中,再加上这条鱼是向右游动的,所以不管如何都无法再处于捕捞范围 [−1,1] 中,第二条鱼在 0 时刻的位置是 1,正好处于捕捞范围,所以最多能捕获 1 条鱼。
数据范围
对于所有测试数据,保证 1≤n≤2×105,−106≤l≤r≤106,−106≤xi≤106,1≤vi≤105,di=1或di=2。
| 测试点编号 |
n |
l,r |
xi |
vi |
特殊性质 |
| 1∼2 |
=1 |
0≤l≤r≤100 |
0≤xi≤100 |
=1 |
|
| 3∼4 |
≤2×103 |
0≤l≤r≤103 |
0≤xi≤103 |
vi≤103 |
A |
| 5∼7 |
0≤l≤r≤104 |
0≤xi≤104 |
vi≤104 |
|
| 8∼10 |
≤2×105 |
−106≤l≤r≤106 |
−106≤xi≤106 |
vi≤105 |
特殊性质 A:所有鱼的游动速度相同、游动方向相同。