RMQ 도로 (RMQ Road)

문제

인덱스국 도로교통 : Day 1

인덱스국에는 N개의 도시과 M개의 양방향 도로가 있습니다. 어떤 사람이 당신에게 도시 X에서 도시 Y로 이동할 수 있는지 물어보고 있습니다. 그러나 S[i]와 E[i]를 연결하는 도로에는 세그먼트 트리로는 TLE가 나고 인덱스 트리로만 풀 수 있는 난이도 D[i]의 무시무시한 RMQ 문제들이 있어서, 모든 사람들은 IDTforces 레이팅보다 어려운 난이도의 문제가 있는 도로는 건너갈 수 없다고 합니다. 당신은 사람들이 헛고생을 하지 않도록 도시 X에서 도시 Y 로 이동하기 위해서 필요한 최소 레이팅을 알려주는 프로그램을 작성하려고 합니다. 단, IDTforces 레이팅은 음수가 될 수 없다고 합니다.

구현 세부 사항

다음 함수들을 구현하세요.

void init(int N, int S[], int E[], int64 D[])

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
• S, E, D는 크기 M 의 배열입니다. 모든 0 ≤ i ≤ M − 1에 대해 S[i]와 E[i]를 연결하는 양방향 도로가 존재하며, 그 도로에는 난이도 D[i]의 RMQ 문제가 있습니다.

int64 getRequiredRating(int X, int Y)

• 이 함수는 그레이더에 의해 Q번 호출됩니다.
• 이 함수는 도시 X에서 도시 Y로 이동하기 위한 최소 실력을 알고 싶을 때 호출됩니다.
• 이 함수는 이동할 수 있다면 이동하기 위한 최소 레이팅을, 이동할 수 없다면 −1을 반환해야 합니다.

제한 조건

• 1 ≤ N ≤ 1,000,000
• 1 ≤ M ≤ 1,000,000
• 0 ≤ Q ≤ 1,000,000
• 1 ≤ S[i], E[i], X, Y ≤ N (0 ≤ i ≤ M − 1)
• 1 ≤ D[i] ≤ $10^{18}$ (0 ≤ i ≤ M − 1)

서브태스크

서브태스크	점수	N	Q
1	4	N ≤ 5,000	Q ≤ 5,000
2	8	N ≤ 50,000	Q ≤ 500,000
3	8	N ≤ 1,000,000	Q ≤ 1,000,000

예제 입출력

N = 3, Q = 3, S = [1, 2, 3, 1], E = [3, 2, 1, 1], D = [2, 3, 5, 2]

그레이더는 다음 함수들을 호출합니다.

init(3, [1, 2, 3, 1], [3, 2, 1, 1], [2, 3, 5, 2])

getRequiredRating(1, 3) = 2

getRequiredRating(1, 2) = -1

getRequiredRating(2, 2) = 0

샘플 그레이더

Sample grader는 다음의 형식으로 입력을 받습니다.

• line 1 : N M Q
• line 2 + i (0 ≤ i ≤ M − 1) : S[i] E[i] D[i]
• line M + 2 + i (0 ≤ i ≤ Q − 1) : X Y