Skip to content
Sign in

買い物 2 (Shopping 2)

Unrated
日本語

Language

Contribute a translation
Time limit
2000 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

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\) つずつ買った．

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

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

Constraints

  • \(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\))．
  • 入力される値はすべて整数である．

Subtasks

  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\) 点) 追加の制約はない．

Input

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

\(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\)

Output

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

Examples

Sample input 1
5 1 3
10 1
40 1
30 1
20 1
50 1
1 2 4
1 3 5
1 1 5
Sample output 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\) の制約を満たす．

Sample input 2
5 3 3
10 1
40 3
30 2
20 1
50 3
1 2 4
3 3 5
2 1 5
Sample output 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\) の制約を満たす．

Sample input 3
5 5 3
50 2
70 4
20 5
30 1
10 3
4 2 4
5 1 5
2 3 4
Sample output 3
85
170
50

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

Sample input 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
Sample output 4
11
13
17
8

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

Sample input 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
Sample output 5
1907757100
3182585150
458514202
1684028078
1064002576
3897234150
2030460064
441379880
2043536529
1009893320

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

Notes

JOI 2024 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source