B - 買い物 2 (Shopping 2) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

JOI 商店には N 個の商品があり，商品には 1 から N までの番号が付けられている．

それぞれの商品には，定価と種類が定められている．商品 i (1 \leqq i \leqq N) の定価は P_i 円である．商品の種類は 1 以上 M 以下の整数で表され，商品 i (1 \leqq i \leqq N) の種類は A_i である．

JOI 商店は，セールを行うことにした．セールは M 日間続き，j 日目 (1 \leqq j \leqq M) には種類 j の商品をすべて定価の半額で買うことができる．

セールの期間中に，Q 人の客が JOI 商店を訪れた．客には 1 から Q までの番号が付けられている．客 k (1 \leqq k \leqq Q) はセールの T_k 日目に JOI 商店を訪れ，商品 L_k, L_k+1, \dots, R_k を 1 つずつ買った．

セールの効果を調査するため，それぞれの客が商品を買うのにかかった金額を知りたい．

商品の情報と客の情報が与えられたとき，それぞれの客が商品を買うのにかかった金額を求めるプログラムを作成せよ．

制約

  • 1 \leqq N \leqq 200\,000．
  • 1 \leqq M\leqq 200\,000．
  • 1 \leqq Q \leqq 200\,000．
  • 2 \leqq P_i \leqq 10^9 (1 \leqq i \leqq N)．
  • P_i は偶数である (1 \leqq i \leqq N)．
  • 1 \leqq A_i \leqq M (1 \leqq i \leqq N)．
  • 1 \leqq T_k \leqq M (1 \leqq k \leqq Q)．
  • 1 \leqq L_k \leqq R_k \leqq N (1 \leqq k \leqq Q)．
  • 入力される値はすべて整数である．

小課題

  1. (15 点) N \leqq 2\,000，M \leqq 2\,000，Q \leqq 2\,000．
  2. (20 点) M = 1．
  3. (12 点) M \leqq 10．
  4. (14 点) A_i \neq A_j (1 \leqq i < j \leqq N)．
  5. (22 点) P_i = 2 (1 \leqq i \leqq N)．
  6. (17 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．

N M Q
P_1 A_1
P_2 A_2
\vdots
P_N A_N
T_1 L_1 R_1
T_2 L_2 R_2
\vdots
T_Q L_Q R_Q

出力

Q 行出力せよ．k 行目 (1 \leqq k \leqq Q) には，客 k が商品を買うのにかかった金額を，単位 (円) を省いて出力せよ．

入力例 1

5 1 3
10 1
40 1
30 1
20 1
50 1
1 2 4
1 3 5
1 1 5

出力例 1

45
50
75

客 1 が商品を買うのにかかった金額は 40 \div 2 + 30 \div 2 + 20 \div 2 = 45 円であるため，1 行目には 45 を出力する．

客 2 が商品を買うのにかかった金額は 30 \div 2 + 20 \div 2 + 50 \div 2 = 50 円であるため，2 行目には 50 を出力する．

客 3 が商品を買うのにかかった金額は 10 \div 2 + 40 \div 2 + 30 \div 2 + 20 \div 2 + 50 \div 2 = 75 円であるため，3 行目には 75 を出力する．

この入力例は小課題 1,2,3,6 の制約を満たす．

入力例 2

5 3 3
10 1
40 3
30 2
20 1
50 3
1 2 4
3 3 5
2 1 5

出力例 2

80
75
135

客 1 が商品を買うのにかかった金額は 40 + 30 + 20 \div 2 = 80 円であるため，1 行目には 80 を出力する．

客 2 が商品を買うのにかかった金額は 30 + 20 + 50 \div 2 = 75 円であるため，2 行目には 75 を出力する．

客 3 が商品を買うのにかかった金額は 10 + 40 + 30 \div 2 + 20 + 50 = 135 円であるため，3 行目には 135 を出力する．

この入力例は小課題 1,3,6 の制約を満たす．

入力例 3

5 5 3
50 2
70 4
20 5
30 1
10 3
4 2 4
5 1 5
2 3 4

出力例 3

85
170
50

この入力例は小課題 1,3,4,6 の制約を満たす．

入力例 4

10 5 4
2 1
2 5
2 4
2 3
2 4
2 2
2 2
2 4
2 2
2 1
3 2 7
1 1 7
2 1 10
5 5 8

出力例 4

11
13
17
8

この入力例は小課題 1,3,5,6 の制約を満たす．

入力例 5

10 10 10
741703628 7
231838922 5
920286164 3
763741914 5
246151406 7
54109256 1
966457488 5
441379880 10
458514202 2
224373612 1
5 5 10
2 2 7
1 9 9
1 3 4
9 4 6
1 1 7
9 4 7
4 8 8
7 5 9
1 4 5

出力例 5

1907757100
3182585150
458514202
1684028078
1064002576
3897234150
2030460064
441379880
2043536529
1009893320

この入力例は小課題 1,3,6 の制約を満たす．