Submission #297227

---

Source Code Expand

import Control.Applicative
import Control.Monad
import Control.Monad.Trans.Class
import Control.Monad.Trans.Maybe
import Data.List
import qualified Data.Map as M
import Text.Printf


type HHMM = Int
type Minute = Int
type Count = Int


data Period = Period Minute Minute

instance Read Period where
    readsPrec p s = [(Period (toMinute st) (toMinute en), v) | (st,  t) <- readsPrec p s, ("-", u) <- lex t, (en,  v) <- readsPrec p u]

instance Show Period where
    showsPrec _ (Period st en) = (showString $ printf "%04d" (toHHMM st)) . ('-' :) . (showString $ printf "%04d" (toHHMM en))

toMinute :: HHMM -> Minute
toMinute x = (h * 60) + m
  where
    h = x `div` 100
    m = x - (h * 100)

toHHMM :: Minute -> HHMM
toHHMM x = (h * 100) + m
  where
    h = x `div` 60
    m = x - (h * 60)


main :: IO ()
main = do
    num <- getNumber
    ps <- getPeriods num
    let ps' = merge $ roundPeriod <$> ps
    mapM_ putStrLn (Prelude.map show ps')


getNumber :: IO Int
getNumber = read <$> getLine


getPeriods :: Int -> IO [Period]
getPeriods num = do
    replicateM num (read <$> getLine)


roundPeriod :: Period -> Period
roundPeriod (Period st en) = Period ((st `div` 5) * 5) (((en + 4) `div` 5) * 5)


merge :: [Period] -> [Period]
merge ps = ps'
  where
    cm = foldl' addPeriodToCountMap M.empty ps
    (ps', _, _) = M.foldrWithKey cumsum ([], 0, 0) cm


addPeriodToCountMap :: M.Map Minute Count -> Period -> M.Map Minute Count
addPeriodToCountMap m (Period st en) = addToCountMap en (-1) (addToCountMap st 1 m)


addToCountMap :: Minute -> Count -> M.Map Minute Count -> M.Map Minute Count
addToCountMap mi c m = case M.lookup mi m of
    Nothing -> M.insert mi c m
    Just c' -> M.insert mi (c' + c) m


cumsum :: Minute -> Count -> ([Period], Count, Minute) -> ([Period], Count, Minute)
cumsum mi c (ps, ac, en) = case ac + c of
    0         -> ((Period mi en) : ps, 0, 0)
    otherwise -> case en of
        0         -> (ps, ac + c, mi)
        otherwise -> (ps, ac + c, en)

Submission Info

Judge Result