Problem 2. Meetings

USACO 2019 December Contest, Silver

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

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

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

测试点性质： 测试点 2-4 满足 $N\le 10^2$，并且对所有 $i$，$w_i=1$。 测试点 5-7 满足 $N\le 10^2$。

输入格式（文件名：meetings.in）：

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

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

输出格式（文件名：meetings.out）：

输出一行，包含答案。

输入样例：

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

输出样例：

2

在这个例子中，奶牛们按如下方式移动：

第一和第二头奶牛于时刻 0.5 在位置 1.5 相遇。此时第一头奶牛拥有速度 $-1$，第二头奶牛拥有速度 $1$。第二和第三头奶牛于时刻 1 在位置 2 相遇。此时第二头奶牛拥有速度 $-1$，第三头奶牛拥有速度 $1$。第一头奶牛于时刻 2 到达左边的牛棚。第二头奶牛于时刻 3 到达左边的牛棚。由于到达牛棚的奶牛的总重量已经至少是所有奶牛的总重量的一半，这个过程此时终止。如果继续进行下去，第三头奶牛将会在时刻 4 到达右边的牛棚。 发生了恰好两次相遇。

供题：Benjamin Qi