Submission #3236649

---

Source Code Expand

let rec upper_bound l r p =
  if r <= 1 + l
  then l
  else let m = (l + r) / 2 in
       if p m 
       then upper_bound m r p
       else upper_bound l m p

let () = Scanf.scanf "%d\n" @@ fun n ->
  let lrs = Array.init n @@ fun _ -> Scanf.scanf "%d %d\n" @@ fun l r -> l, r in
  let f x = Array.fold_right (fun (l, r) -> ( + ) @@
    if x < l then l - x
    else if r < x then x - r
    else 0) lrs 0 in
  Printf.printf "%d\n" @@ f @@ upper_bound
    (Array.fold_right (fun (l, _) -> min l) lrs max_int)
    (Array.fold_right (fun (_, r) -> max r) lrs 0 + 1) @@ fun x -> f (x - 1) >= f x

Submission Info

Judge Result