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