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

#6325
서브태스크

쇼핑 2 2초 1024MB

문제

상점에는 N 개의 상품이 있으며 상품에는 1 에서 N 까지의 번호가 매겨져 있다.

각 상품에는 정가와 종류가 정해져 있다.

상품 i\ ( 1≤i≤N )의 정가는 P_i 원 이다.

상품의 종류는 1 이상 M 이하의 정수로 나타내고, 상품 i\ ( 1≤i≤N )의 종류는 A_i 이다.

상점은 세일을 하기로 했다. 세일은 M 일간 계속되고, j 일째( 1≤j≤M )에는 종류 j 의 상품을 모두 정가의 반값으로 살 수 있다.

판매 기간 동안 Q 명의 고객이 상점을 방문했다. 고객은 1 에서 Q 까지 번호가 매겨져 있다.

손님 k\ ( 1 ≤ k ≤ Q )는 판매의 T_k 일째에 상점을 방문하여 상품 L_k , L_k+ 1 ,\ ...,\ R_k 를 하나씩 샀다.

판매의 효과를 조사하기 위해 각 고객이 상품을 사는 데 사용한 금액을 알고 싶다.

상품 정보와 고객 정보가 주어지면 각 고객이 상품을 구입하는 데 사용한 금액을 구하는 프로그램을 작성하시오.


입력

입력은 다음과 같은 형식으로 주어진다.

N\ M\ Q

P_1\ A_1

P_2\ A_2

︙

P_N A_N

T_1 \ L_1 \ R_1

T_2 \ L_2 \ R_2

︙

T_Q \ L_Q \ R_Q

  • 1 \le N,M,Q \le 200\ 000

  • 2 \le P_i \le 10^9 (1 \le i \le N), P_i는 짝수.

  • 1 \le A_i, T_k \le M (1 \le i \le N), (1 \le k \le Q)

  • 1 \le L_k \le R_k \le N (1 \le k \le Q)

  • 모든 입력은 정수다.


출력

Q 행에 걸쳐 k 번째 행 ( 1 ≤ k ≤ Q )에 고객 k 가 상품을 사는 데 사용한 금액을 출력한다.


부분문제

번호 점수 조건
#115점

N, M, Q \le 2\ 000

#220점

M=1

#312점

M \le 10

#414점

A_i \neq A_j (1 \le i < j \le N)

#522점

P_i = 2 (1 \le i \le N)

#617점

추가 제한 없음


예제1

입력
513
101
401
301
201
501
124
135
115
출력
45
50
75

예제2

입력
533
101
403
302
201
503
124
335
215
출력
80
75
135

예제3

입력
553
502
704
205
301
103
424
515
234
출력
85
170
50

예제4

입력
1054
21
25
24
23
24
22
22
24
22
21
327
117
2110
558
출력
11
13
17
8

예제5

입력
101010
7417036287
2318389225
9202861643
7637419145
2461514067
541092561
9664574885
44137988010
4585142022
2243736121
5510
227
199
134
946
117
947
488
759
145
출력
1907757100
3182585150
458514202
1684028078
1064002576
3897234150
2030460064
441379880
2043536529
1009893320

출처

JOI 2024 예선2

역링크