結果

問題 No.801 エレベーター
コンテスト
ユーザー 👑 tttmmmyyyy
提出日時 2026-11-03 16:02:44
言語 Fix
(1.6.0 + cp-library + minilib)
コンパイル:
fix_c _filename_
実行:
./a.out
結果
AC  
実行時間 850 ms / 2,000 ms
+ 881µs
コード長 1,859 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,258 ms
コンパイル使用メモリ 669,204 KB
実行使用メモリ 9,904 KB
最終ジャッジ日時 2026-11-03 16:03:22
合計ジャッジ時間 25,412 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
make: 'lib.o' は更新済みです.

ソースコード

diff #
raw source code 

module Main;

import BinaryHeap;
import BoolArray;
import CPLib.Arithmetic;
import CPLib.DSegtree;
import CPLib.Graph;
import CPLib.IO;
import CPLib.LSegtree;
import CPLib.Monoid;
import CPLib.UnionFind;
import CPLib.ZP;
import HashMap;
import HashSet;

type Z = ZP P1000000007;

// type Event = union {
//     enter : (I64, Z),
//     leave : (I64, Z)
// };
// 
// pos : Event -> I64 = |e| match e {
//     enter(i) => i,
//     leave(i) => i
// };

main : IO () = (
    let cN = *read_i; // 回数
    let cM = *read_i; // エレベータの数
    let cK = *read_i; // 移動回数
    let cLRs = *range(0, cM).fold_m([], |_, cLRs|
        let l = *read_i;
        let r = *read_i;
        let l = l - 1;
        cLRs.push_back((l, r)).pure
    );
    let t = Array::fill(cN, zp(0) : Z);
    let t = t[0].iset(zp(1));
    let t = range(0, cK).fold(t, |k, t|
        let acm = range(0, cN).fold([zp(0)], |n, acm|
            let v = acm.@(acm.@size - 1);
            acm.push_back(v + t.@(n))
        );
        let evts = cLRs.to_iter.fold([], |(l, r), evts|
            let sum = acm.@(r) - acm.@(l);
            evts.push_back((l, sum)).push_back((r, -sum))
        );
        let evts = evts.sort_by(|(a, b)| a.@0 < b.@0);
        let s = Array::fill(cN, zp(0));
        let (s, _, _) = range(0, cN).fold((s, 0, zp(0)), |n, (s, ei, v)|
            // ei の position <= n なものをすべて処理
            let (ei, v) = loop((ei, v), |(ei, v)|
                if ei >= evts.@size { (ei, v).break };
                let e = evts.@(ei);
                if !(e.@0 <= n) { (ei, v).break };
                let v = v + e.@1;
                let ei = ei + 1;
                (ei, v).continue
            );
            let s = s[n].iset(v);
            (s, ei, v)
        );
        s
    );
    let ans = t.@(cN-1);
    ans.@value.to_string.println
);
0