Walking in Manhattan

题目描述

农夫约翰和他的 $Q$ 头奶牛（$1 \leq Q \leq 2 \cdot 10^5$）正在曼哈顿度假，但奶牛们逃走了，现在正在城市里自由走动！曼哈顿非常大——大到它的 $N$ 条道路（$1 \le N \le 2 \cdot 10^5$）在 $x$-$y$ 平面中无限延伸；并且很方便的是，这些道路都完全水平或完全竖直。每条水平路或竖直路都可以用形如 $y = c_i$ 或 $x = c_i$ 的方程建模，其中 $c_i$ 是 $0$ 到 $10^9$（含端点）范围内的整数。 农夫约翰准确知道每头奶牛开始走动的位置，以及它们逃走到现在过了多久。奶牛的行为非常可预测，因此每头奶牛都按以下模式行走： 它们只会以每秒 1 个单位的速度向北（$+y$）或向东（$+x$）行走。 如果它们当前只在一条道路上，它们会沿着该道路的方向继续行走。 如果它们位于两条道路的交点处，那么当它们已经行走的秒数为偶数时向北走，否则向东走。 给定曼哈顿道路的布局以及每头奶牛的信息，帮助农夫约翰确定他的奶牛们现在在哪里！

输入格式

第一行包含 $N$ 和 $Q$。 接下来的 $N$ 行描述道路。每条道路由一个方向（H 或 V）以及一个坐标 $c_i$ 描述。保证所有道路互不相同。 接下来的 $Q$ 行描述奶牛。每头奶牛由三个整数 $(x_i, y_i, d_i)$ 描述，表示它们恰好在 $d_i$ 秒前从 $(x_i, y_i)$ 开始行走。保证 $(x_i, y_i)$ 位于某条道路上，且 $0 \le x_i, y_i, d_i \le 10^9$。

输出格式

输出 $Q$ 行，其中第 $i$ 行包含第 $i$ 头奶牛的当前位置。

4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10

14 5
7 13
6 15
6 16
110 4

提示

前两头奶牛走过如下路径： (6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5) (6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13) 计分： 输入 2-4 满足 $N, Q, c_i, x_i, y_i, d_i \leq 100$。 输入 5-9 满足 $N, Q\le 3000$。 输入 10-20 没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2024|Gold

来源

USACO|2024|Gold