algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.ml (2313B)


      1 (*
      2 - n stones
      3 - 1 -> n
      4 - cost of ith is v_i
      5 - query types
      6     1. sum
      7         - l,r
      8             - l <= r
      9         - sum from l to r
     10     2. u_i cost of ith cheapest stone l and r where we sum over these
     11         - basically, sum on ordered list non-decreasing
     12 
     13 - n, n integers (costs), m (number of questions), questions (type, l, r)
     14 
     15 n = 6
     16 costs = 6 4 2 7 2 7
     17 question count = 3
     18 
     19 q1 = 2 3 6
     20 q2 = 1 3 4
     21 q3 = 1 1 6
     22 
     23 2 3 6 is ordered sum from index 2 to 5
     24 
     25 [2, 2, 4, 6, 7, 7]
     26 
     27 sum(4, 6, 7, 7) = 24
     28 
     29 ...
     30 
     31 *)
     32 
     33 type query = {tp : int64; l : int; r : int}
     34 
     35 let readShortInt () =
     36     Scanf.scanf " %d" (fun x -> x)
     37 
     38 let readInt () = 
     39     Scanf.scanf " %Ld" (fun x -> x)
     40 
     41 let readInts num  = 
     42     let arr = Array.make num (Int64.zero) in
     43         let rec acc itr = 
     44             if itr == num then ()
     45             else (arr.(itr) <- readInt (); acc (itr+1))
     46     in let () = acc 0 in arr
     47 
     48 
     49 let readQuery () = 
     50     let a = readInt () in let b = readShortInt () in let c = readShortInt () in
     51     {tp =  a; l = b; r = c}
     52 
     53 let readQueries qc = 
     54     let arr = Array.make qc {tp = 0L; l = 0; r = 0} in
     55         let rec acc idx = 
     56             if idx = qc then () else (arr.(idx) <- readQuery (); acc (idx+1))
     57         in acc 0; arr
     58 
     59 let prefixSums arr =
     60     let sums = Array.make ((Array.length arr) + 1) Int64.zero in
     61         let rec acc idx running = 
     62             if idx = Array.length arr then () 
     63             else (sums.(idx+1) <- (Int64.add running arr.(idx)); acc (idx+1) (Int64.add running arr.(idx)))
     64         in acc 0 0L; sums
     65 
     66 let handleQuery query orderedSums stdSums = 
     67     if query.tp = 2L then
     68         (print_endline (Int64.to_string (Int64.sub orderedSums.(query.r) orderedSums.(query.l-1))))
     69     else
     70         (print_endline (Int64.to_string (Int64.sub stdSums.(query.r) stdSums.(query.l-1))))
     71 
     72 let rec handleQueries queries orderedSums stdSums idx =
     73     if idx = Array.length queries then ()
     74     else 
     75         (handleQuery queries.(idx) orderedSums stdSums; handleQueries queries orderedSums stdSums (idx+1))
     76 
     77 let () = 
     78     let n = readShortInt () in
     79     let costs = readInts n in
     80     let stdSums = prefixSums costs in
     81     let () = Array.sort compare costs in
     82     let orderedSums = prefixSums costs in
     83     let qc = readShortInt () in
     84     let queries = readQueries qc in 
     85         handleQueries queries orderedSums stdSums 0