Stuck in a Rut

题目描述

农夫约翰最近扩大了农场的规模，因此从奶牛们的视角来看，它现在实际上是无限大的！奶牛们把农场的放牧区域看作一个无限的二维方格网，每个方格“单元”都长满了美味的草（可以把每个单元想成无限棋盘上的一个格子）。农夫约翰有 $N$ 头奶牛（$1\le N\le 1000$），每头奶牛起初都在不同的单元格中；有些奶牛面朝北，有些面朝东。 每过一小时，每头奶牛会执行以下两种行为之一： 如果她当前所在的格子里的草已经被另一头奶牛吃过，则她停止（并从此一直保持停止状态）。 吃光她当前格子里的所有草，并按照她面朝的方向向前移动一格。 随着时间推移，每头奶牛都会在身后留下由空格子组成的贫瘠“车辙”。 如果两头奶牛在同一次移动中进入同一个仍有草的格子，那么她们共享该格子，并在下一小时继续分别沿各自的方向移动。 农夫约翰看到奶牛停止吃草会不高兴，他想知道该把停止的奶牛怪罪于谁。如果奶牛 $b$ 在一个最初由奶牛 $a$ 吃过的格子里停止，那么我们称奶牛 $a$ 使奶牛 $b$ 停止（cow $a$ stopped cow $b$）。此外，如果奶牛 $a$ 使奶牛 $b$ 停止，且奶牛 $b$ 使奶牛 $c$ 停止，那么我们也说奶牛 $a$ 也使奶牛 $c$ 停止（即“使停止”的关系具有传递性）。每头奶牛被归咎的程度等于她使多少头奶牛停止。请计算每头奶牛应承担的责怪数量——也就是她使多少头奶牛停止。

输入格式

第一行输入包含 $N$。接下来的 $N$ 行每行描述一头奶牛的起始位置：一个字符（N 表示面朝北，E 表示面朝东）以及两个非负整数 $x$ 和 $y$（$0\le x\le 10^9$, $0\le y\le 10^9$），表示该格子的坐标。所有的 $x$ 坐标两两不同，所有的 $y$ 坐标也两两不同。 为尽可能清楚地说明方向和坐标：若一头奶牛在格子 $(x,y)$ 并向北移动，则她最终到达格子 $(x,y+1)$。若她向东移动，则她最终到达格子 $(x+1, y)$。

输出格式

输出 $N$ 行。输出的第 $i$ 行应给出输入中第 $i$ 头奶牛所承担的责怪数量。

6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 1
E 9 2

0
0
1
2
1
0

提示

在该示例中，奶牛 3 使奶牛 2 停止，奶牛 4 使奶牛 5 停止，奶牛 5 使奶牛 6 停止。由于传递性，奶牛 4 也使奶牛 6 停止。 SCORING: 在测试点 2-5 中，所有坐标都不超过 $2000$。 在测试点 6-10 中，没有额外限制。 题目贡献者：Brian Dean

标签: USACO|2020|Silver

来源

USACO|2020|Silver