페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6219
서브태스크

맨해튼 수학여행 2s 1024MB

문제

권수쌤과 그의 학생 Q명 이 맨해튼으로 수학여행을 왔습니다. 하지만 학생들이 도망쳐 시내를 자유롭게 돌아다니고 있습니다! 맨해튼은 너무 커서 N개의 도로들이 x-y 평면에 무한히 뻗어 있지만, 다행히 모든 도로는 완벽하게 수평 또는 수직으로 되어 있습니다. 각 수평 및 수직 도로는 y = c_i 또는 x = c_i 형태의 방정식으로 모델링할 수 있다.

권수쌤은 각 학생이 어디서부터 걷기 시작했는지, 그리고 얼마나 오래 전에 도망쳤는지를 정확히 알고 있습니다. 학생들은 매우 예측 가능하여 다음과 같은 패턴에 따라 걷습니다:

  • 학생들은 북쪽(+y) 또는 동쪽(+x)으로 초당 1단위씩만 걷습니다.

  • 현재 한 도로에 있다면, 그 도로의 방향을 따라 계속 걷습니다.

  • 두 도로의 교차점에 있는 경우, 짝수 초 동안 걸은 후에는 북쪽으로 걷고, 홀수 초 동안 걸은 후에는 동쪽으로 걷습니다.

맨해튼의 도로 배치와 각 학생의 정보를 바탕으로 권수쌤이 현재 학생들이 어디에 있는지 알아낼 수 있도록 도와주세요!


입력

첫 번째 줄에는 N과 Q가 주어집니다.

다음 N개의 줄에는 도로가 설명됩니다. 각 도로는 방향(H 또는 V)과 좌표 c_i로 설명됩니다. 도로는 고유함이 보장됩니다.

다음 Q개의 줄에는 학생이 설명됩니다. 각 학생은 세 개의 정수 (x_i, y_i, d_i)로 설명되며, 이는 학생이 정확히 d_i 초 전에 (x_i, y_i)에서 걷기 시작했음을 의미합니다.

[제약 조건]

  • 1 ≤ Q ≤ 200,000

  • 1 ≤ N ≤ 200,000

  • c_i는 정수이며, 0 ≤ c_i ≤ 1,000,000,000

  • (x_i, y_i)는 반드시 어떤 도로 위에 위치하며, 0 ≤ x_i, y_i, d_i ≤ 1,000,000,000


출력

Q개의 줄에 i번째 학생의 현재 위치를 출력합니다.


부분문제

번호 점수 조건
#130점

N,Q,c_i,x_i,y_i,d_i≤100

#230점

N,Q≤3000

#340점

추가 제약 조건 없음


예제 

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)



출처

USACO 2024 January Gold

로그인해야 코드를 작성할 수 있어요.