| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 148 | 51 | 45 | 63.380% |
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 | 15 | N ≦ 2 000,M ≦ 2 000,Q ≦ 2 000. |
| 2 | 20 | M = 1. |
| 3 | 12 | M ≦ 10. |
| 4 | 14 | Ai ≠ Aj (1 ≦ i < j ≦ N). |
| 5 | 22 | Pi = 2 (1 ≦ i ≦ N). |
| 6 | 17 | 追加の制約はない. |
5 1 3 10 1 40 1 30 1 20 1 50 1 1 2 4 1 3 5 1 1 5
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 の制約を満たす.
5 3 3 10 1 40 3 30 2 20 1 50 3 1 2 4 3 3 5 2 1 5
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 の制約を満たす.
5 5 3 50 2 70 4 20 5 30 1 10 3 4 2 4 5 1 5 2 3 4
85 170 50
この入力例は小課題 1,3,4,6 の制約を満たす.
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
11 13 17 8
この入力例は小課題 1,3,5,6 の制約を満たす.
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
1907757100 3182585150 458514202 1684028078 1064002576 3897234150 2030460064 441379880 2043536529 1009893320
この入力例は小課題 1,3,6 の制約を満たす.
Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics Qualification Round > JOI 2023/2024 예선 2 2번