3315. [USACO19 DEC Silver]Meetings

【题目描述】

有两个牛棚位于一维数轴上的点 $0$ 和 $L$ 处。同时有 $N$ 头奶牛位于数轴上不同的位置（将牛棚和奶牛看作点）。每头奶牛 $i$ 初始时位于某个位置 $x_i$，并朝着正向或负向以一个单位每秒的速度移动，用一个等于 $1$ 或 $-1$ 的整数 $d_i$ 表示。每头奶牛还拥有一个在范围 $[1,10^3]$ 内的重量。所有奶牛始终以恒定的速度移动，直到以下事件之一发生：

- 如果奶牛 $i$ 移动到了一个牛棚，则奶牛 $i$ 停止移动。

- 当奶牛 $i$ 和 $j$ 占据了相同的点的时候，并且这一点不是一个牛棚，则发生了相遇。此时，奶牛 $i$ 被赋予奶牛 $j$ 先前的速度，反之亦然。注意奶牛可能在一个非整数点相遇。

令 $T$ 等于停止移动的奶牛（由于到达两个牛棚之一）的重量之和至少等于所有奶牛的重量之和的一半的最早时刻。请求出在时刻 $0 \ldots T$（包括时刻 $T$）之间发生的奶牛对相遇的总数。

【输入格式】

输入的第一行包含两个空格分隔的整数 $N$ 和 $L$。

以下$ N $行，每行包含三个空格分隔的整数 $w_i$，$x_i$ 以及 $d_i$。所有的位置 $x_i$ 各不相同，并且满足 $0<x_i<L$。

【输出格式】

输出一行，包含答案。

【样例输入】

3 5
1 1 1
2 2 -1
3 3 -1

【样例输出】

2

【提示】

对于 $100\%$ 的数据，保证有：$1≤N≤5×10^4,L≤1×10^9$。

【来源】

USACO 2019十二月月赛 Silver 组