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

#8332
서브태스크

Mi Teleferico 2s 1024MB

문제

La Paz, 볼리비아의 수도는 관광지로 유명하며 Mi Teleferico라는 공중 케이블카로도 잘 알려져 있습니다.

관광을 위해 La Paz를 방문한 여러분은 가능한 한 많은 관광지를 방문하고자 합니다. 이 문제에서는 다음과 같이 단순화한 상황을 고려합니다.

La Paz에는 고도가 증가하는 순서대로 번호가 1부터 N까지인 공중 케이블카 정거장이 있습니다.

1부터 M까지 번호가 매겨진 단방향 노선들이 있으며, 각 노선은 한 개의 케이블카 회사에 의해 운영됩니다. 회사들은 1부터 P까지 번호가 매겨져 있습니다.

노선 i (1 ≤ i ≤ M)는 정거장 Aᵢ에서 Bᵢ로 운행되며, 회사 Cᵢ가 관리합니다. (항상 Aᵢ < Bᵢ)

La Paz 교통국은 편리하게 이용할 수 있도록 무제한 이용권을 발행합니다. 각 이용권은 두 정수 l, r (1 ≤ l ≤ r ≤ P)로 구성되며, 이 이용권을 가진 사람은 회사 번호가 l, l+1, …, r 중 하나인 노선을 탈 수 있습니다. (한 이용권으로 여러 노선을 이용할 수 있음)

Q명의 관광객이 La Paz를 방문합니다. 관광객 j (1 ≤ j ≤ Q)는 초기 이용권 (L_j, R_j)과 X_j원의 현금을 가지고 있습니다.

각 관광객의 목표는 자신이 가진(또는 교환을 통해 얻은) 이용권을 사용하여, 정거장 1에서 출발해 해당 이용권으로 탈 수 있는 노선만 이용함으로써 모든 정거장에 도달할 수 있게 되는 것입니다.

관광객 j는 단 한 번, 아래 절차를 통해 자신의 이용권을 교환할 수 있습니다.

  • 두 정수 l^′, r^′ (1 ≤ l^′ ≤ r^′ ≤ P)를 선택한다.

  • 현재 이용권 (L_j, R_j)를 (l^′, r^′)로 교환하는데, 교환 비용은 |L_j − l^′| + |R_j − r^′|원이다.

각 관광객이 자신이 가진 현금 X_j 내에서 목표를 달성할 수 있는지 판별하는 프로그램을 작성하시오.


입력

첫 번째 줄에 세 정수 N, M, P가 주어집니다.

다음 M개의 줄에는 각 노선에 대해 세 정수 Aᵢ, Bᵢ, Cᵢ가 공백으로 구분되어 주어집니다 (1 ≤ i ≤ M). Aᵢ와 Bᵢ는 노선의 시작과 끝 정거장을, Cᵢ는 노선을 관리하는 회사 번호를 나타냅니다.

그 다음 줄에 정수 Q가 주어집니다.

이후 Q개의 줄 각각에는 세 정수 L_j, R_j, X_J가 주어집니다 (1 ≤ j ≤ Q). 여기서 (L_j, R_j)는 관광객 j의 초기 이용권, X_j는 그가 가진 현금을 나타냅니다.

[제약사항]

  • 2 ≤ N ≤ 300\ 000

  • 1 ≤ M ≤ 300\ 000

  • 1 \le P \le 10^9

  • 0 ≤ A_i ≤ B_i \le N ( 1 ≤ i ≤ N )

  • 0 ≤ C_i ≤ P ( 1 ≤ i ≤ N )

  • 1 ≤ Q ≤ 400\ 000

  • 1 ≤ L_j ≤ R_j \le P ( 1 ≤ j ≤ Q )

  • 0 ≤ X_i ≤ 10^9 ( 1 ≤ j ≤ Q )

  • 주어진 값은 모두 정수입니다.


출력

출력은 표준 출력으로 Q개의 줄을 출력합니다.

각 줄에는 관광객 j (1 ≤ j ≤ Q)가 가진 현금 X_j 내에서 목표(정거장 1에서 모든 정거장 도달)를 달성할 수 있으면 "Yes", 달성할 수 없으면 "No"를 출력합니다.


부분문제

번호 점수 조건
#17점

N ≤ 50, M ≤ 50, Q ≤ 50, 모든 관광객의 X_j = 0

#28점

P ≤ 10

#311점

P ≤ 100

#423점

P ≤ 300,000, 모든 관광객의 X_j = 0

#59점

P ≤ 300,000

#622점

N ≤ 8,000, M ≤ 8,000

#720점

추가 제약 조건 없음


예제 #1

4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
4
3 7 0
5 6 0
3 4 0
1 9 0
Yes
No
No
Yes

관광객 1: 초기 이용권 (3, 7), 현금 0. 이 이용권으로는 노선 1, 2, 3, 4를 이용해 정거장 1에서 모든 정거장에 도달할 수 있으므로 목표 달성이 가능 → Yes.

관광객 2: 초기 이용권 (5, 6), 현금 0. 이 경우 이용 가능한 노선은 3, 4뿐이어서 정거장 4에 도달할 수 없으므로 → No.

관광객 3: 초기 이용권 (3, 4), 현금 0. 목표 달성이 불가능하므로 → No.

관광객 4: 초기 이용권 (1, 9), 현금 0. 모든 노선을 이용할 수 있으므로 → Yes.


예제 #2

4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
3
5 6 10
3 4 1
7 8 3
Yes
No
Yes

관광객 1: 초기 이용권 (5, 6), 현금 10. 교환을 통해 (5, 6)에서 (1, 5)로 변경하면 비용 |5−1|+|6−5| = 5가 소요되며, 새 이용권으로 정거장 1에서 모든 정거장에 도달 가능 → Yes.

관광객 2: 초기 이용권 (3, 4), 현금 1. 어떤 교환으로도 목표 달성이 불가능 → No.

관광객 3: 목표 달성이 가능 → Yes.


예제 #3

3 1 1000000000
1 2 6
1
1 1000000000 1000000000
No

주어진 노선으로는 정거장 1에서 정거장 3까지 이동할 수 없으므로, 관광객은 목표를 달성할 수 없습니다.


예제 #4

5 9 2000
2 3 1814
2 3 457
1 2 1226
3 4 1354
1 5 1050
1 2 1725
2 3 1383
1 5 1626
1 4 1795
5
850 1872 128
82 428 1217
487 924 573
1639 1926 202
202 420 25
Yes
Yes
Yes
Yes
No

각 관광객은 자신의 초기 이용권과 현금을 바탕으로 (필요한 경우 교환을 고려하여) 정거장 1에서 모든 정거장으로 이동 가능한 이용권을 확보할 수 있는지 여부가 결정됩니다.


출처

JOI 2025

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