結果

問題 No.877 Range ReLU Query
コンテスト
ユーザー potoooooooo
提出日時 2019-09-06 22:27:58
言語 OCaml
(5.2.1)
結果
AC  
実行時間 459 ms / 2,000 ms
コード長 3,158 bytes
コンパイル時間 1,903 ms
コンパイル使用メモリ 21,632 KB
実行使用メモリ 35,532 KB
最終ジャッジ日時 2024-11-08 10:07:18
合計ジャッジ時間 7,343 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
File "Main.ml", line 63, characters 10-13:
63 |       let com = scan_int() and l = scan_int() and r = scan_int() and x = scan_int() in
               ^^^
Warning 26 [unused-var]: unused variable com.

ソースコード

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 () =
  let n = scan_int() and q = scan_int() in
  let merge (a, x) (b, y) = (a+b, x+y) in
  let st = SegmentTree.init n merge (0, 0) in
  let a = scan_array n scan_int in
  let _ = 
    for i = 0 to n-1 do
      SegmentTree.set st i (a.(i), 1)
    done in
  let a_array = Array.mapi (fun i x -> (x, i)) a in
  let compare_a (x, _) (y, _) = if x > y then 1 else -1 in
  let _ = Array.fast_sort compare_a a_array in
  let _ = SegmentTree.build st in
  let q_array = Array.make q (0, 0, 0, 0) in
  let ans = Array.make q (-1) in
  let _ =
    for i = 0 to q-1 do
      let com = scan_int() and l = scan_int() and r = scan_int() and x = scan_int() in
      q_array.(i) <- (x, l, r, i)
    done in
  let compare_query (x, _, _, _) (y, _, _, _) = if x > y then 1 else -1 in
  let _ = Array.fast_sort compare_query q_array in
  let _ =
    let rec calc a_index q_index =
      if q_index = q then ()
      else
        let x, l, r, i = q_array.(q_index) in
        if a_index = n then
          let sum, u = SegmentTree.query st (l-1) r in
          let _ = ans.(i) <- sum - x * u in
          calc a_index (q_index+1)
        else
          let ax, ai = a_array.(a_index) in
          if ax <= x then
            let _ = SegmentTree.update st ai (0, 0) in
              calc (a_index+1) q_index
          else
            let sum, u = SegmentTree.query st (l-1) r in
            let _ = ans.(i) <- sum - x * u in
            calc a_index (q_index+1) in
    calc 0 0 in
  for i = 0 to q-1 do
    print_int ans.(i)
  done
0