#PU1377. USACO 2024 January Contest, Gold — Problem 1. Walking in Manhattan

    ID: 1548 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan24来源:usaco.orgscoring:equal_test_cases哈希

USACO 2024 January Contest, Gold — Problem 1. Walking in Manhattan

USACO 2024 January Contest, Gold — Problem 1. Walking in Manhattan

题目描述

Farmer John and his QQ (1≤Q≤2⋅1051 \leq Q \leq 2 \cdot 10^5) cows are in Manhattan on vacation, but the cows have escaped and are now walking around freely in the city! Manhattan is huge – so huge that its NN (1≤N≤2⋅1051 \le N \le 2 \cdot 10^5) roads stretch infinitely in the xx-yy plane, but conveniently, those roads all run perfectly horizontally or vertically. Each horizontal and vertical road can be modeled by an equation of the form y=ciy = c_i or x=cix = c_i, where cic_i is an integer in the range 00 to 10910^9 inclusive. Farmer John knows exactly where each cow started walking and how long ago they escaped. Cows are very predictable, so each of them walks according to the following pattern: They only walk north (+y+y) or east (+x+x) at one unit per second. If they are currently on a single road, they continue walking along the road's direction. If they are at the intersection of two roads, they walk north if they have been walking for an even number of seconds and east otherwise. Given the layout of Manhattan and the information for each cow, help Farmer John determine where his cows are now!

输入格式

The first line contains NN and QQ. The next NN lines describe the roads. Each road is described by a direction (H or V) and a coordinate cic_i. It is guaranteed that the roads are unique. The next QQ lines describe the cows. Each cow is described by three integers (xi,yi,di)(x_i, y_i, d_i), meaning that they started walking from (xi,yi)(x_i, y_i) exactly did_i seconds ago. It is guaranteed that (xi,yi)(x_i, y_i) lies on some road, and 0≤xi,yi,di≤1090 \le x_i, y_i, d_i \le 10^9.

输出格式

(见题面原文)

数据范围

Inputs 2-4 satisfy N,Q,ci,xi,yi,di≤100N, Q, c_i, x_i, y_i, d_i \leq 100. Inputs 5-9 satisfy N,Q≤3000N, Q\le 3000. Inputs 10-20 satisfy no additional constraints. Problem credits: Benjamin Qi

样例

样例 1

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
The first two cows took the following paths:
(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)
(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)