Meetings

题目描述

两座谷仓位于一维数轴上的位置 $0$ 和 $L$（$1\le L\le 10^9$）。数轴上还有 $N$ 头奶牛（$1\le N\le 5\cdot 10^4$）位于互不相同的位置（可以将谷仓与奶牛都视为点）。每头奶牛 $i$ 初始位于位置 $x_i$，并以每秒 1 个单位的速度向正方向或负方向移动，用整数 $d_i$ 表示，其取值为 $1$ 或 $-1$。每头奶牛还有一个重量 $w_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

提示

评分说明： 测试点 2-4 满足 $N\le 10^2$ 且对所有 $i$ 都有 $w_i=1$。 测试点 5-7 满足 $N\le 10^2$。 样例解释： 本样例中奶牛的移动过程如下： 第一头与第二头奶牛在时刻 0.5 于位置 1.5 相遇。此后第一头奶牛速度变为 $-1$，第二头奶牛速度变为 $1$。 第二头与第三头奶牛在时刻 1 于位置 2 相遇。此后第二头奶牛速度变为 $-1$，第三头奶牛速度变为 $1$。 第一头奶牛在时刻 2 到达左侧谷仓。 第二头奶牛在时刻 3 到达左侧谷仓。 由于到达谷仓的奶牛重量之和已至少为所有奶牛重量之和的一半，过程在此终止。第三头奶牛本会在时刻 4 到达右侧谷仓。 恰好发生了两次相遇。 题目来源：Benjamin Qi

标签: USACO|2019|Silver

来源

USACO|2019|Silver