We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Arrays
  4. Array Manipulation
  5. Discussions

Array Manipulation

  • Roaneno
     + 0 comments

    Someone's probably mentioned, but to avoid using O(n) space, you can use a sparse data structure like a map.

    import qualified Data.Map.Strict as M
import Data.List (foldl')

main = do
    getLine -- skip the first line, we won't use N or M
    input <- map readWords . lines <$> getContents -- lazily read operations
    let ops = foldl' insertOperation M.empty input
    print $ findMax ops

readWords = map read . words

insertOperation m [a, b, k] = (M.insertWith (+) a k) . (M.insertWith (+) (b+1) (-k)) $ m

findMax :: M.Map Int Int -> Int -- Result is >= 0
findMax m = snd $ M.foldl' update (0, 0) m
    where update = \(cur, peak) x -> let next = cur + x in (next, max peak next)