Solution to https://open.kattis.com/problems/pleasegofirst

pleasegofirst.hs

{-# LANGUAGE BangPatterns #-}
import           Control.Monad
import           Data.List
import qualified Data.Map.Strict as M

main :: IO ()
main = do
  cases <- readLn
  replicateM_ cases $ do
    getLine
    queue <- getLine
    let (_, res, _) = foldl' timeSaved (mempty, 0, 0) queue
    print res

timeSaved :: (M.Map Char (Pair Int), Int, Int)
          -> Char
          -> (M.Map Char (Pair Int), Int, Int)
timeSaved (!m, !acc, !i) c =
  case m M.!? c of
    Nothing ->
      ( M.insert c (Pair i 1) m
      , acc
      , i + 1
      )
    Just (Pair prevI n) ->
      ( M.insert c (Pair i (n + 1)) m
      , acc + (i - prevI - 1) * n * 5
      , i + 1
      )

data Pair a = Pair !a !a deriving Show