Đi Bộ Manhattan

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

$Q$ con bò của bác John đã trốn thoát ở Manhattan và đi bộ theo các quy tắc nhất định. Manhattan có $N$ con đường chạy theo phương ngang hoặc dọc, mô tả bằng $y = c_{i}$ hoặc $x = c_{i}$ .

Quy tắc di chuyển:

Bò di chuyển về phía bắc (+y) hoặc phía đông (+x) với tốc độ 1 đơn vị/giây.
Trên một con đường đơn lẻ: bò tiếp tục theo hướng của con đường đó (ngang = đông, dọc = bắc).
Tại ngã tư (giao của đường ngang và dọc): đi về phía bắc nếu số giây đã đi là chẵn, đi về phía đông nếu lẻ.
Không trên đường nào: dùng quy tắc chẵn/lẻ như tại ngã tư.

Cho vị trí ban đầu và thời gian đã đi của mỗi con bò, hãy tìm vị trí hiện tại của chúng.

Dòng đầu tiên: hai số nguyên $N$ và $Q$ ( $1 \leq N, Q \leq 2 \times 10^{5}$ ).
$N$ dòng tiếp theo: ký tự $d$ (H hoặc V) và số nguyên $c_{i}$ ( $0 \leq c_{i} \leq 10^{9}$ ) - mô tả đường.
$Q$ dòng tiếp theo: ba số nguyên $x_{i}$ , $y_{i}$ , $d_{i}$ ( $0 \leq x_{i}, y_{i}, d_{i} \leq 10^{9}$ ) - vị trí bắt đầu và số giây đã đi.

$Q$ dòng, mỗi dòng chứa hai số nguyên - vị trí hiện tại $(x, y)$ của mỗi con bò.

Input	Output	Giải thích
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	Bò 1: (6,3) -> di chuyển 10 giây -> (14,5). Bò 5: (100,4) trên đường H4, đi đông 10 bước -> (110,4).

Bình luận

Không có bình luận tại thời điểm này.