結果

問題 No.877 Range ReLU Query
コンテスト
ユーザー 👑 tttmmmyyyy
提出日時 2026-10-30 21:01:05
言語 Fix
(1.6.0 + cp-library + minilib)
コンパイル:
fix_c _filename_
実行:
./a.out
結果
AC  
実行時間 59 ms / 2,000 ms
+ 249µs
コード長 1,659 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 16,561 ms
コンパイル使用メモリ 677,092 KB
実行使用メモリ 11,196 KB
最終ジャッジ日時 2026-10-30 21:02:15
合計ジャッジ時間 21,265 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
make: 'lib.o' は更新済みです.

ソースコード

diff #
raw source code 

module Main;

import CPLib.DSegtree::fold;
import CPLib.IO;
import CPLib.Monoid;
import CPLib.Segtree;

main : IO () = (
    let n = *read_i;
    let q = *read_i;
    let as = *read_is(n);
    let as_sorted = as.to_iter.enumerate.to_array.sort_by(|(a, b)| a.@1 > b.@1);
    let tree : Segtree (Sum I64) = Segtree::create(n);
    let cnt : Segtree (Sum I64) = Segtree::create(n);
    let qs = *range(0, q).fold_m([], |i, qs|
        let _t = *read_i;
        let l = *read_i - 1;
        let r = *read_i;
        let x = *read_i;
        qs.push_back((i, l, r, x)).pure
    );
    let qs = qs.sort_by(|((_, _, _, x), (_, _, _, y))| x > y);
    let ans = fill(q, 0);
    let (ans, _, _, _) = range(0, q).fold((ans, 0, tree, cnt), |q, (ans, as_sorted_i, tree, cnt)|
        let (i, l, r, x) = qs.@(q);
        let as_sorted_ib = as_sorted_i;
        let as_sorted_i = loop(as_sorted_i, |as_sorted_i|
            if as_sorted_i >= n { n.break };
            let (_, a) = as_sorted.@(as_sorted_i);
            if a < x { as_sorted_i.break };
            continue $ as_sorted_i + 1
        );
        let (tree, cnt) = range(as_sorted_ib, as_sorted_i).fold((tree, cnt), |as_sorted_i, (tree, cnt)|
            let (i, a) = as_sorted.@(as_sorted_i);
            let tree = tree.set(i, Sum { v: a });
            let cnt = cnt.set(i, Sum { v: 1 });
            (tree, cnt)
        );
        let sum = tree.fold(l, r).@v // x 以上のものの和
            - x * cnt.fold(l, r).@v; // x * (x以上のものの個数)
        let ans = ans[i].iset(sum);
        (ans, as_sorted_i, tree, cnt)
    );
    "{}".printfln((ans.to_iter.joined_with("\n"),));;
    pure()
);
0