問題一覧 > 通常問題

No.3314 Library Rearrangement

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 11
作問者 : 👑 ArcAki / テスター : 👑 p-adic
ProblemId : 11986 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-10-24 11:02:45
コンテストの他の問題:

注意

想定解でもかなり制限時間が厳しいためC++相当の速度の言語を使用することを強く推奨します。

ストーリー (読まなくて良い)

図書館の司書であるAkiさんは図書館の本の価値全体を高めたいと思っています。
そこでいくつかのシリーズものの本を連続する本棚に収納することで本棚の価値を増加させることにしました。
そしてどのくらいのスピード感で改善ができたかを調べることにしました。

問題文

長さ $N$ の数列 $A$ が与えられます。$K$ 個の更新クエリが与えられ、$i$ 番目の更新クエリでは以下の操作を行います。

  • 3つの正整数 $L_i, R_i, X_i$ が与えられます。$L_i ≤ j ≤ R_i$ なる各整数 $j$ に対し $A_j$ を $\max(A_j, X_i)$ に変更します。
また $Q$ 個の質問クエリが与えられます。$i$ 番目の質問クエリの内容は以下のとおりです。
  • 3つの正整数 $L_i, R_i, X_i$ が与えられます。初めて $\sum_{j=L_i}^{R_i}{A_j} ≥ X_i$ となるのは何番目の更新クエリの直後か答えてください。
    ただし $1$ 番目の更新クエリの前にすでに条件を満たすなら $0$ 、$K$ 番目の更新クエリの後でも条件を満たさないなら $-1$ と答えてください。
各質問クエリに対する答えを求めてください。

入力

$N\ K\ Q$
$A_1\ A_2\ …\ A_N$
$Update_1$
$\vdots$
$Update_K$
$Query_1$
$\vdots$
$Query_Q$

ただし $Update_i$ 及び $Query_i$ はそれぞれ更新クエリ、質問クエリを表し、ともに以下の形式で与えられます。

$L_i\ R_i\ X_i$

  • 入力は全て整数である。
  • $1 ≤ N, Q ≤ 5 × 10^4$
  • $1 ≤ K ≤ 10^4$
  • $1 ≤ A_i ≤ 10^9$
  • 更新クエリにおいて以下を満たす。
    • $1 ≤ L_i ≤ R_i ≤ N$
    • $1 ≤ X_i ≤ 10^9$
  • 質問クエリにおいて以下を満たす。
    • $1 ≤ L_i ≤ R_i ≤ N$
    • $1 ≤ X_i ≤ 5 × 10^{13}$

出力

$Q$ 行出力してください。$i$ 行目では質問クエリ $i$ の答えを出力し、改行してください。

サンプル

サンプル1
入力
10 7 6
1 10 7 6 2 3 1 1 11 2
1 6 3
7 7 3
8 10 5
4 6 7
1 2 6
2 5 9
1 7 8
2 5 26
1 10 70
8 10 30
1 3 26
5 8 21
10 10 10
出力
1
6
-1
7
4
-1

開始直後及び各更新クエリ後の $A$ の値は以下の通りです。

  • $[1, 10, 7, 6, 2, 3, 1, 1, 11, 2]$
  • $[3, 10, 7, 6, 3, 3, 1, 1, 11, 2]$
  • $[3, 10, 7, 6, 3, 3, 3, 1, 11, 2]$
  • $[3, 10, 7, 6, 3, 3, 3, 5, 11, 5]$
  • $[3, 10, 7, 7, 7, 7, 3, 5, 11, 5]$
  • $[6, 10, 7, 7, 7, 7, 3, 5, 11, 5]$
  • $[6, 10, 9, 9, 9, 7, 3, 5, 11, 5]$
  • $[8, 10, 9, 9, 9, 8, 8, 5, 11, 5]$
例えば質問クエリ $1$ では初めは和は $10+7+6+2 = 25 < 26$ で非成立ですが
更新クエリ $1$ のあとは $10+7+6+3 ≥ 26$ となるので答えは $1$ となります。
同様にして質問クエリ $2$ の答えは更新クエリ $5$ の後では $68$ ですが更新クエリ $6$ の後では $74$ となるので $6$ となります。
質問クエリ $3$ や $6$ のように最後まで条件を満たさない場合もあれば初めから条件を満たしている場合もあることに注意してください。

サンプル2
入力
18 27 37
14 3 20 9 4 6 8 14 10 10 9 20 19 3 16 2 4 16
10 12 19
5 18 23
8 16 65
1 13 17
6 14 12
1 3 15
2 5 79
3 4 80
2 4 34
7 13 12
13 18 72
8 11 29
15 16 55
1 8 13
1 14 40
5 16 46
1 13 7
2 3 16
4 13 63
8 11 38
2 5 9
16 16 61
1 1 32
9 13 49
3 11 71
1 12 48
12 16 81
1 5 588
5 15 59
2 11 215
4 12 521
8 11 222
1 11 70
7 8 400
6 9 100
1 3 273
10 16 44
12 18 98
6 9 207
9 10 409
8 11 315
9 14 283
7 9 506
1 6 550
10 15 380
8 16 27
5 18 416
3 17 410
8 15 417
2 12 523
8 12 317
7 17 185
9 11 231
8 15 205
1 17 368
16 17 281
4 15 292
1 10 372
11 18 493
9 9 38
10 15 121
9 13 412
8 9 347
9 13 375
出力
-1
0
3
7
3
0
-1
3
-1
0
2
15
-1
-1
3
-1
-1
3
0
3
3
3
7
3
2
-1
3
3
-1
3
7
11
3
2
-1
-1
27

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。