問題一覧 > 通常問題

No.3314 Library Rearrangement

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 14
作問者 : 👑 ArcAki / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 11986 / 自分の提出
問題文最終更新日: 2025-10-24 11:02:45
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 486 オムニバス (順位表) の他の問題:

Note

The time limit is quite tight even for the intended solution, so we strongly recommend using a language with speed comparable to C++.

Story (you do not need to read this)

Aki, a librarian, wants to raise the overall value of the books in the library.
So she decided to increase the value of the bookshelves by storing several book series on consecutive bookshelves.
She then decided to investigate how quickly the improvement was achieved.

Problem Statement

You are given a sequence $A$ of length $N$. $K$ update queries are given, and the $i$-th update query performs the following operation.

  • Three positive integers $L_i, R_i, X_i$ are given. For each integer $j$ such that $L_i ≤ j ≤ R_i$, change $A_j$ to $\max(A_j, X_i)$.
In addition, $Q$ question queries are given. The $i$-th question query is as follows.
  • Three positive integers $L_i, R_i, X_i$ are given. Find the update query immediately after which $\sum_{j=L_i}^{R_i}{A_j} ≥ X_i$ holds for the first time.
    However, if the condition is already satisfied before the $1$-st update query, answer $0$, and if the condition is not satisfied even after the $K$-th update query, answer $-1$.
Find the answer to each question query.

Input

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

Here, $Update_i$ and $Query_i$ represent an update query and a question query, respectively, and both are given in the following format.

$L_i\ R_i\ X_i$

  • All inputs are integers.
  • $1 ≤ N, Q ≤ 5 × 10^4$
  • $1 ≤ K ≤ 10^4$
  • $1 ≤ A_i ≤ 10^9$
  • The update queries satisfy the following.
    • $1 ≤ L_i ≤ R_i ≤ N$
    • $1 ≤ X_i ≤ 10^9$
  • The question queries satisfy the following.
    • $1 ≤ L_i ≤ R_i ≤ N$
    • $1 ≤ X_i ≤ 5 × 10^{13}$

Output

Output $Q$ lines. On the $i$-th line, output the answer to question query $i$, followed by a newline.

Sample

Sample 1
Input
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
Output
1
6
-1
7
4
-1

The values of $A$ at the start and after each update query are as follows.

  • $[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]$
For example, in question query $1$, the sum is initially $10+7+6+2 = 25 < 26$, so the condition does not hold, but
after update query $1$, we have $10+7+6+3 ≥ 26$, so the answer is $1$.
Similarly, for question query $2$, the sum is $68$ after update query $5$ but $74$ after update query $6$, so the answer is $6$.
Note that the condition may never be satisfied, as in question queries $3$ and $6$, and it may also be satisfied from the beginning.

Sample 2
Input
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
Output
-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もしくは右上の雲マークをクリックしてアカウントを作成してください。