結果

問題 No.878 Range High-Element Query
ユーザー potoooooooopotoooooooo
提出日時 2019-09-06 22:46:03
言語 OCaml
(5.1.0)
結果
AC  
実行時間 506 ms / 2,000 ms
コード長 2,196 bytes
コンパイル時間 392 ms
コンパイル使用メモリ 21,648 KB
実行使用メモリ 17,024 KB
最終ジャッジ日時 2024-04-17 08:50:23
合計ジャッジ時間 4,912 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 4 ms
5,376 KB
testcase_02 AC 4 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 4 ms
5,376 KB
testcase_09 AC 5 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 481 ms
15,872 KB
testcase_12 AC 309 ms
16,256 KB
testcase_13 AC 341 ms
12,416 KB
testcase_14 AC 233 ms
11,520 KB
testcase_15 AC 293 ms
16,000 KB
testcase_16 AC 449 ms
16,768 KB
testcase_17 AC 506 ms
17,024 KB
testcase_18 AC 499 ms
17,024 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
File "Main.ml", line 60, characters 8-10:
60 |     let op = scan_int() and l = scan_int() and r = scan_int() in
             ^^
Warning 26 [unused-var]: unused variable op.

ソースコード

diff # 

let scan_int () = Scanf.scanf " %d" (fun x -> x)
let print_int n = Printf.printf "%d\n" n
let scan_array len read_func = Array.init len (fun _ -> read_func())

(* zero-based numbering *)
module SegmentTree :
  sig
    type 'a st
    val init   : int -> ('a -> 'a -> 'a) -> 'a -> 'a st
    val set    : 'a st -> int -> 'a -> unit
    val build  : 'a st -> unit
    val update : 'a st -> int -> 'a -> unit
    val query  : 'a st -> int -> int -> 'a
    val get    : 'a st -> int -> 'a
  end =
  struct
    type 'a st = {n: int; func: ('a -> 'a -> 'a); seg: 'a array; id: 'a}
    let get_n _n =
      let rec loop n ret = if ret < n then loop n (ret*2) else ret in loop _n 1
    let init _n _func _id =
      let _n = get_n _n in {n = _n; func = _func; seg = Array.make (_n*2) _id; id = _id}
    let set st i x = st.seg.(st.n+i) <- x
    let merge st par = st.seg.(par) <- st.func st.seg.(par*2) st.seg.(par*2+1)
    let build st =
      let rec loop i = 
        if i = 0 then () else let _ = merge st i in loop (i-1) in
      loop (st.n-1)
    let update st i x =
      let _ = set st i x in
      let k = i + st.n in
      let rec loop i =
        if i = 0 then () else let _ = merge st i in loop (i/2) in
      loop (k/2)
    (* query: [a, b) *)
    let query st a b =
      let rec loop a b l r =
        if a >= b then st.func l r
        else
          let l = if a land 1 = 0 then l else st.func l st.seg.(a) in
          let r = if b land 1 = 0 then r else st.func st.seg.(b-1) r in
          loop ((a + a land 1) / 2) ((b - b land 1) / 2) l r in
      loop (a+st.n) (b+st.n) st.id st.id
    let get st i = st.seg.(st.n+i)
  end

let f x (a, list) = if (List.hd list < x) then (a+1, x :: list) else (a, list)

let merge (a, a_list) (b, b_list) = List.fold_right f b_list (a, a_list)

let () =
  let n = scan_int() and q = scan_int() in
  let st = SegmentTree.init n merge (0, [0]) in
  let _ =
    for i = 0 to n-1 do
      let a = scan_int() in
      SegmentTree.set st i (1, [a])
    done in
  let _ = SegmentTree.build st in
  for i = 1 to q do
    let op = scan_int() and l = scan_int() and r = scan_int() in
    let ans, _ = SegmentTree.query st (l-1) r in
    print_int ans
  done
0