제사 비용 (Cost for Rituals)

문제

인덱스국 문화사 : Day 4

당신은 동아시아에 존재했던 전설 속의 국가 '인덱스국'에 대해 얼마나 알고 있나요? 최근 인덱스국의 유적이 발굴되어 많은 역사가들의 관심을 사고 있습니다. 인덱스국 연구에 일생을 바 친 박 교수에 따르면, 인덱스국은 다신교 국가로 그 흔적이 발견된 것만 N개의 사당을 보유하고 있었다고 전해집니다.

박 교수는 인덱스국에 굉장히 흥미로운 제사 풍습이 있었다고 말합니다. 사당의 위치를 2차원 평면상의 한 점 (x, y)로 나타내었을 때, 매년 상수 A, B를 정하여 A ≤ x ≤ B를 만족하는 사당들에 대해서 제사를 올린다는 것입니다.

그런데 박 교수는 오랜 연구를 통해 혁신적인 사실을 밝혀냈습니다. 인덱스국의 (0, 0)좌표에는 거대한 호수가 있는데, 이 호수는 매년 우기마다 범람하여 $x^2 + y^2 ≤ R^2$을 만족하는 영역을 침수시켰다는 것입니다. 제사 구역에 있는 사당이라도 침수된 해에는 제사를 올릴 수 없습니 다. 다행히도 인덱스국은 신앙심을 중요시하는 나라였기 때문에, 우기가 끝나자마자 사당 복구 작업을 진행해 다음해의 제사 작업에 차질이 없도록 합니다.

사당마다 바치는 제물은 엄격하게 정해져 있기 때문에, 한 사당에 제사를 올리는 비용은 항상 일정합니다. 하지만 최근 인덱스국의 유적지에서 A, B, R에 관한 기록물이 계속해서 발견되고 있습니다. 이는 인덱스국의 경제 규모 추론에 매우 중요한 자료가 됩니다. 박 교수는 A, B, R 의 값이 주어질 때, 그 해 인덱스국의 제사 비용을 빠르게 계산하는 프로그램을 만들어달라고 여러분에게 부탁했습니다. 뛰어난 프로그래머인 여러분이 박 교수의 연구를 도와주도록 합시다!

구현 세부 사항

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

void init(int X[], int Y[], int C[])

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
• 정수 N은 인덱스국의 사당 개수를 나타냅니다.
• 크기 N의 배열 X, Y, C는 각각의 사당에 대한 정보를 저장하고 있습니다. i = 0, 1, ··· N − 1에 대해 X[i]는 i번 사당의 x좌표를, Y[i]는 i번 사당의 y좌표를 나타냅니다. C[i]는 i번째 사당에서 제사를 올리는데 드는 비용입니다. 같은 위치에 2개 이상의 사당이 존재할 수 있음에 주의하세요.

int64 getCost(int A, int B, int R)

• 이 함수는 총 Q번 호출됩니다.
• 이 함수는 특정 연도에 대한 A, B, R이 주어질 때, 그해 인덱스국의 제사 비용을 반환해야 합니다.

제한 조건

• 1 ≤ N ≤ 500,000
• $−10^9$ ≤ X[i], Y[i] ≤ $10^9$
• 1 ≤ C[i] ≤ $10^9$
• 1 ≤ Q ≤ 500,000
• $-10^9$ ≤ A ≤ B ≤ $10^9$
• 0 ≤ R ≤ $10^9$

서브태스크

서브태스크	점수	제한 조건
1	4	N ≤ 4,000, Q ≤ 4,000
2	2	−1,000 ≤ X[i], Y[i] ≤ 1,000
3	2	N ≤ 100,000, Q ≤ 100,000
4	9	모든 getCost 호출에서 R ≤ 100
5	3	추가 제한 조건 없음

예제 입출력

N = 4, Q = 2, X = [3, 2, 1, 3], Y = [1, 2, 3, 0], C = [1, 2, 4, 8]

그레이더는 다음의 함수를 호출합니다.

init([3, 2, 1, 3], [1, 2, 3, 0], [1, 2, 4, 8])

getCost([2, 3, 2]) = 11

getCost([2, 3, 3]) = 1

샘플 그레이더

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

A[j], B[j], R[j]는 각각 j번째로 getCost함수가 호출될 때의 A, B, R 값을 의미합니다.

• line 1 : N Q
• line 2 : X[0] X[1] ··· X[N − 1]
• line 3 : Y[0] Y[1] ··· Y[N − 1]
• line 4 : C[0] C[1] ··· C[N − 1]
• line 5 + i (0 ≤ i ≤ Q − 1) : A[i] B[i] R[i]