| 第23回日本情報オリンピック 二次予選 |
|
|
2023年12月15日
情報オリンピック日本委員会
|
JOI 商店には N 個の商品があり，商品には 1 から N までの番号が付けられている．
それぞれの商品には，定価と種類が定められている．商品 i (1 ≦ i ≦ N) の定価は Pi 円である．商品の種類は 1 以上 M 以下の整数で表され，商品 i (1 ≦ i ≦ N) の種類は Ai である．
JOI 商店は，セールを行うことにした．セールは M 日間続き，j 日目 (1 ≦ j ≦ M) には種類 j の商品をすべて定価の半額で買うことができる．
セールの期間中に，Q 人の客が JOI 商店を訪れた．客には 1 から Q までの番号が付けられている．客 k (1 ≦ k ≦ Q) はセールの Tk 日目に JOI 商店を訪れ，商品 Lk, Lk+1, …, Rk を 1 つずつ買った．
セールの効果を調査するため，それぞれの客が商品を買うのにかかった金額を知りたい．
商品の情報と客の情報が与えられたとき，それぞれの客が商品を買うのにかかった金額を求めるプログラムを作成せよ．
入力は以下の形式で与えられる．
N M Q
P1 A1
P2 A2
︙
PN AN
T1 L1 R1
T2 L2 R2
︙
TQ LQ RQ
Q 行出力せよ．k 行目 (1 ≦ k ≦ 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 ÷ 2 + 30 ÷ 2 + 20 ÷ 2 = 45 円であるため，1 行目には 45 を出力する．
客 2 が商品を買うのにかかった金額は 30 ÷ 2 + 20 ÷ 2 + 50 ÷ 2 = 50 円であるため，2 行目には 50 を出力する．
客 3 が商品を買うのにかかった金額は 10 ÷ 2 + 40 ÷ 2 + 30 ÷ 2 + 20 ÷ 2 + 50 ÷ 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 ÷ 2 = 80 円であるため，1 行目には 80 を出力する．
客 2 が商品を買うのにかかった金額は 30 + 20 + 50 ÷ 2 = 75 円であるため，2 行目には 75 を出力する．
客 3 が商品を買うのにかかった金額は 10 + 40 + 30 ÷ 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 の制約を満たす．