問題一覧 > 通常問題

No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 54
作問者 : 👑 KazunKazun / テスター : keisuke6keisuke6 butsurizukibutsurizuki
1 ProblemId : 7616 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-14 11:10:21

問題文

チェリーちゃんはゼルコバ君からプレゼントとして長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ を貰った.

実は, チェリーちゃんが貰った数列は $1$ 日目の昼から次のように日に日に変化していく.

  • $d$ 日目の昼に, $i=1,2, \dots, N$ のうち, $d \geq T_i$ かつ 第 $i$ 項目が正であるような全ての $i$ に対して, 第 $i$ 項目の値が $1$ 減る.

チェリーちゃんが数列 $A$ を貰ったのが $0$ 日目の夜だとしたとき, 次の $Q$ 個の質問 $1$, $\dots$, 質問 $Q$ に答えよ.

  • 質問 $q$: $D_q$ 日目の夜時点におけるチェリーちゃんが貰った数列にある第 $L_q$ 項から第 $R_q$ 項まで (両端共に含む) の連続部分列における $(R_q-L_q+1)$ 個の項の総和は何か?

ただし, チェリーちゃんが住んでいる世界は次のように昼夜が変化していく.

  • $0$ 日目夜 $\to$ $1$ 日目昼 $\to$ $1$ 日目夜 $\to$ $2$ 日目昼 $\to$ $\cdots$ $\to$ $(d-1)$ 日目夜 $\to$ $d$ 日目昼 $\to$ $d$ 日目夜 $\to$ $(d+1)$ 日目昼 $\to$ $\cdots$

制約

  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq A_i \leq 10^9$
  • $1 \leq T_i \leq 10^9$
  • $1 \leq Q \leq 2 \times 10^5$
  • $0 \leq D_q \leq 2 \times 10^9$
  • $1 \leq L_q \leq R_q \leq N$
  • 入力はすべて整数

入力

$N$
$A_1$ $T_1$
$\vdots$
$A_N$ $T_N$
$Q$
$D_1$ $L_1$ $R_1$
$\vdots$
$D_Q$ $L_Q$ $R_Q$

出力

出力は $Q$ 行からなる. $q~(1 \leq q \leq Q)$ 行目には質問 $q$ に対する解答を整数で出力せよ.

最後に改行も忘れないこと.

サンプル

サンプル1
入力
5
4 3
6 1
5 5
0 8
2 2
4
0 1 5
2 3 4
5 2 5
100 1 5
出力
17
5
5
0

チェリーちゃんが貰った数列は次のように変化していく.

  • $0$ 日目夜: $(4,6,5,0,2)$
  • $1$ 日目夜: $(4,5,5,0,2)$
  • $2$ 日目夜: $(4,4,5,0,1)$
  • $3$ 日目夜: $(3,3,5,0,0)$
  • $4$ 日目夜: $(2,2,5,0,0)$
  • $5$ 日目夜: $(1,1,4,0,0)$
  • $6$ 日目夜: $(0,0,3,0,0)$
  • $7$ 日目夜: $(0,0,2,0,0)$
  • $8$ 日目夜: $(0,0,1,0,0)$
  • $9$ 日目夜: $(0,0,0,0,0)$
  • $\vdots$
  • $100$ 日目夜: $(0,0,0,0,0)$

サンプル2
入力
4
0 4
0 46
0 464
0 4646
3
0 1 4
1 1 4
10 1 4
出力
0
0
0

チェリーちゃんが貰った数列は変化しない.

サンプル3
入力
10
314159265 358979323 
846264338 327950288
419716939 937510582
97494459 230781640
628620899 862803482
534211706 798214808
651328230 664709384
460955058 223172535
940812848 111745028
410270193 852110555
5
271828182 3 5
845904523 2 8
536028747 4 10
1352662497 1 7
757247093 6 9
出力
1104785754
2333303020
2889059001
143326906
1388313008

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