問題一覧 > 通常問題

No.2065 Sum of Min

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 115
作問者 : 👑 qand / テスター : 👑 p-adic ygussany とりゐ
お気に入りにしたユーザー ProblemId : 8066 / 自分の提出
問題文最終更新日: 2024-02-04 15:41:07
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 359 (順位表) の他の問題:

Problem Statement

For each $i=1,2,\ldots,Q$, find $\displaystyle\sum_{k=L_i}^{R_i}\min(X_i,A_k)$.

Input

$N\ Q$
$A_1\ A_2 \ldots A_N$
$L_1\ R_1\ X_1$
$L_2\ R_2\ X_2$
$\vdots$
$L_Q\ R_Q\ X_Q$

  • $1\le N\le 10^5$
  • $1\le Q\le 10^5$
  • $1\le A_k\le 10^9\ (1\le k\le N)$
  • $1\le L_i\le R_i\le N\ (1\le i\le Q)$
  • $1\le X_i\le 10^9\ (1\le i\le Q)$
  • All input values are integers.

    • Output

    Print $Q$ lines.
    On line $i$ $(1\le i\le Q)$, print the value of $\displaystyle\sum_{k=L_i}^{R_i}\min(X_i,A_k)$.

    Sample

    Sample 1
    Input
    3 3
1 2 4
1 3 5
2 3 3
1 3 1
    Output
    7
5
3

    $\displaystyle\sum_{k=1}^3\min(5,A_k)=1+2+4=7$. Therefore, print $7$ on line $1$.
    $\displaystyle\sum_{k=2}^3\min(3,A_k)=2+3=5$. Therefore, print $5$ on line $2$.
    $\displaystyle\sum_{k=1}^3\min(1,A_k)=1+1+1=3$. Therefore, print $3$ on line $3$.

    Sample 2
    Input
    5 1
1000000000 1000000000 1000000000 1000000000 1000000000
1 5 1000000000
    Output
    5000000000

    Note that the output may not fit in a 32-bit integer type.

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