#P1309. 撒网捕鱼(fish)

撒网捕鱼(fish)

题目背景

从中国古代开始,就有捕鱼的活动。捕鱼是一种古老的生产活动,是人类获取食物的重要手段之一。捕鱼的方法有很多种,有的人用渔网,有的人用鱼叉,有的人用捕鱼网,有的人用捕鱼笼。

渔民都是靠海为生,靠天吃饭。辛勤劳动的渔民也是中华儿女的一支重要力量,也体现了中华民族的伟大精神。

题目描述

小明的家乡有一条美丽的河,周围的人们都以养鱼、捕鱼为生。河中有许许多多的鱼,有的从左往右游,有的从右往左游,小明有一张渔网,但是他只有一次撒网的机会来捕鱼,因为撒网之后鱼就会被吓走。小明想一次性地捕到更多的鱼。

通过观察小明发现,目前河中一共有 nn 条鱼, 在时刻 00,每一条鱼都有一个初始的位置 xix_i,并且有一个移动方向(向左或者向右)和游动速度 viv_i,小明的渔网布置在位置 [l,r][l, r] 的区域。换句话说,当他撒网时,范围 (l鱼位置rl \le 鱼位置 \le r)中的鱼会被小明捕获。

小明可以选择在任一时刻 ttt0t \geq 0 且是整数) 撒网,请问小明最多能捕获多少条鱼?

输入格式

第一行一个整数 nn,表示河中鱼的条数。

第二行一个整数 ll,表示渔网的左边界。

第三行一个整数 rr,表示渔网的右边界。

接下来的 3×n3 \times n 行,每三行包含一条鱼的信息,具体信息如下:

第一行一个整数 xix_i,表示鱼的初始位置,

第二行一个整数 viv_i,表示鱼的游动速度,

第三行一个整数 did_i,表示鱼的移动方向,di=1d_i = 1 表示向左游,di=2d_i = 2 表示向右游。

输出格式

一行一个整数,表示小明最多能捕获鱼的条数。

样例数据

2
1
5
-1
3
2
6
2
1
2

样例解释 #1

小明可以选择在时刻 11 撒网,这时候第一条鱼在位置 1+3=2-1 + 3 = 2,第二条鱼在位置 62=46 - 2 = 4,都处于范围 [1,5][1, 5] 中,所以最多能捕获 22 条鱼。

1
-1
1
2
2
2
1
1
2
0

样例解释 #2

小明可以选择在时刻 00 撒网,这时候第一条鱼在位置 2+0=22 + 0 = 2,此时已经不在捕捞范围[1,1][-1, 1] 中,再加上这条鱼是向右游动的,所以不管如何都无法再处于捕捞范围 [1,1][-1, 1] 中,第二条鱼在 00 时刻的位置是 11,正好处于捕捞范围,所以最多能捕获 11 条鱼。

数据范围

对于所有测试数据,保证 1n2×1051 \le n \le 2 \times 10 ^ 5106lr106-10^6 \le l \le r \le 10^6106xi106-10^6 \le x_i \le 10^61vi105 1 \le v_i \le 10^5di=1di=2d_i = 1 或 d_i = 2

测试点编号 nn l,rl,r xix_i viv_i 特殊性质
121 \sim 2 =1 = 1 0lr1000 \le l \le r \le 100 0xi1000 \le x_i \le 100 =1 = 1
343 \sim 4 2×103 \le 2 \times 10 ^ 3 0lr1030 \le l \le r\le 10^3 0xi1030 \le x_i \le 10^3 vi103 v_i \le 10^3 AA
575 \sim 7 0lr1040 \le l \le r\le 10^4 0xi1040 \le x_i \le 10^4 vi104 v_i \le 10^4
8108 \sim 10 2×105 \le 2 \times 10 ^ 5 106lr106-10^6 \le l \le r\le 10^6 106xi106-10^6 \le x_i \le 10^6 vi105 v_i \le 10^5

特殊性质 A:所有鱼的游动速度相同、游动方向相同。