kckyoung2   1년 전

문제

JOI 상점에는 N개의 상품이 있고, 상품에는 1 부터 N 까지의 번호가 매겨져 있다.

각각의 상품에는 가격과 종류가 정해져 있다. 상품 i (1 ≦ i ≦ N) 의 가격은 Pi 엔이다. 상품의 종류는 1 이상 M 이하의 정수로 나타내고, 상품 i (1 ≦ i ≦ N) 의 종류는 Ai 이다.

JOI 상점은 세일을 하기로 했다. 세일은  M 일간 연속해서 진행되고,j 일째 (1 ≦ j ≦ M) 에는 종류 j 의 상품을 50%의 가격으로 살 수 있다.

세일 기간 중에 Q 명의 손님이 JOI 상점가에 방문했다. 손님에게는  1 부터 Q 까지의 번호가 매겨져 있다. 손님 k (1 ≦ k ≦ Q) 는 세일 Tk 일째에 JOI 상점가를 방문하고, 상점 Lk, Lk+1, …, Rk 를 1 개씩 구매했다.

세일의 효과를 조사하기 위해서 각각의 손님이 상품을 구매할 때 지불한 비용을 알고 싶다.

상품의 정보와 손님의 정보가 주어졌을 때, 각각의 손님이 상품을 구매하는데 지불한 금액을 구하는 프로그램을 작성해보자

입력

입력은 아래와 같은 형식으로 주어진다.

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

출력

Q 행을 출력해라. k 번째 행 (1 ≦ k ≦ Q) 에는, 손님 k 가 상품을 구매했을 때 지불한 비용을 단위 (엔) 을 생략해서 출력해라.

제한

  • 1 ≦ N ≦ 200 000.
  • 1 ≦ M≦ 200 000.
  • 1 ≦ Q ≦ 200 000.
  • 2 ≦ Pi ≦ 109 (1 ≦ i ≦ N).
  • Pi 는 짝수 (1 ≦ i ≦ N).
  • 1 ≦ Ai ≦ M (1 ≦ i ≦ N).
  • 1 ≦ Tk ≦ M (1 ≦ k ≦ Q).
  • 1 ≦ Lk ≦ Rk ≦ N (1 ≦ k ≦ Q).
  • 입력으로 주어지는 값은 전부 정수.

댓글을 작성하려면 로그인해야 합니다.