{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BlockArguments #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE LambdaCase #-}
{-# HLINT ignore "Used otherwise as a pattern" #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications #-}
{-# OPTIONS_GHC -Wno-unrecognised-pragmas #-}
module Main where
import Control.Monad (filterM, foldM, foldM_, forM, forM_, replicateM, unless, when)
import Data.Array (Array)
import Data.Array.Base (MArray, UArray (UArray), freezeIOArray, getElems)
import Data.Array.IArray (IArray (bounds), accumArray, array, assocs, listArray, (!))
import qualified Data.Array.IArray as IA
import Data.Array.IO.Internals (IOArray (IOArray), IOUArray (IOUArray))
import Data.Array.MArray (freeze, newArray, readArray, writeArray)
import Data.Bifunctor (Bifunctor (bimap))
import Data.Bits (Bits (bit, testBit))
import Data.Bool
import Data.ByteString.Char8 (readInt)
import qualified Data.ByteString.Char8 as BC
import Data.Char (ord)
import qualified Data.Char as C
import Data.Foldable (for_)
import Data.Function (on)
import Data.Graph (buildG, dfs)
import qualified Data.Heap as H
import Data.IORef (IORef, modifyIORef', newIORef)
import qualified Data.IntMap as IM
import qualified Data.IntSet as IS
import Data.Ix
import qualified Data.List as L
import Data.List.Extra
import qualified Data.Map.Strict as M
import Data.Maybe (fromJust, fromMaybe, isNothing)
import Data.Ord (Down (Down), comparing)
import Data.Sequence (Seq ((:<|)), (|>))
import qualified Data.Sequence as Seq
import qualified Data.Set as S
import Data.Tree (Tree (subForest), flatten)
import qualified Data.Vector.Algorithms.Intro as VAI
import qualified Data.Vector.Unboxed as VU
import Debug.Trace
import GHC.IO
import System.Environment
import System.Exit
main :: IO ()
main = do
[n, q] <- getInts
hts <- replicateM q do
[h, t] <- readWords
return (h, read @Int t)
let ans =
foldl'
( \((l, r), cnt) (h, t) ->
case h of
"L" -> let d = dist r l l t n in ((t, r), cnt + d)
"R" -> let d = dist l r r t n in ((l, t), cnt + d)
)
((1, 2), 0)
hts
print $ snd ans
{-- lib --}
getInts :: IO [Int]
getInts = unfoldr (BC.readInt . BC.dropWhile C.isSpace) <$> BC.getLine
readWords :: IO [String]
readWords = words <$> getLine
dist :: (Num a, Ord a, Bounded a) => a -> a -> a -> a -> a -> a
dist r l c t n =
let rlr = if (r - l) > 0 then r - l else r + (n - l)
rll = if (l - r) > 0 then l - r else l + (n - r)
tcr = if (t - c) >= 0 then t - c else t + (n - c)
tcl = if (c - t) >= 0 then c - t else c + (n - t)
tcr' = if tcr > rlr then maxBound else tcr
tcl' = if tcl > rll then maxBound else tcl
in min tcr' tcl'
{-- debug --}
dbg :: (Show a) => a -> ()
dbg = case getDebugEnv of
Just _ -> (`traceShow` ())
Nothing -> const ()
getDebugEnv :: Maybe String
getDebugEnv = unsafePerformIO (lookupEnv "DEBUG")
{-# NOINLINE getDebugEnv #-}
app/Main.hs:13:1: warning: [-Wunused-imports]
The import of ‘filterM, foldM, foldM_, forM, forM_, unless, when’
from module ‘Control.Monad’ is redundant
|
13 | import Control.Monad (filterM, foldM, foldM_, forM, forM_, replicateM, unless, when)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:14:1: warning: [-Wunused-imports]
The import of ‘Data.Array’ is redundant
except perhaps to import instances from ‘Data.Array’
To import instances alone, use: import Data.Array()
|
14 | import Data.Array (Array)
| ^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:15:1: warning: [-Wunused-imports]
The import of ‘Data.Array.Base’ is redundant
except perhaps to import instances from ‘Data.Array.Base’
To import instances alone, use: import Data.Array.Base()
|
15 | import Data.Array.Base (MArray, UArray (UArray), freezeIOArray, getElems)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:16:1: warning: [-Wunused-imports]
The import of ‘Data.Array.IArray’ is redundant
except perhaps to import instances from ‘Data.Array.IArray’
To import instances alone, use: import Data.Array.IArray()
|
16 | import Data.Array.IArray (IArray (bounds), accumArray, array, assocs, listArray, (!))
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:17:1: warning: [-Wunused-imports]
The qualified import of ‘Data.Array.IArray’ is redundant
except perhaps to import instances from ‘Data.Array.IArray’
To import instances alone, use: import Data.Array.IArray()
|
17 | import qualified Data.Array.IArray as IA
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:18:1: warning: [-Wunused-imports]
The import of ‘Data.Array.IO.Internals’ is redundant
except perhaps to import instances from ‘Data.Array.IO.Internals’
To import instances alone, use: import Data.Array.IO.Internals()
|
18 | import Data.Array.IO.Internals (IOArray (IOArray), IOUArray (IOUArray))
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:19:1: warning: [-Wunused-imports]
The import of ‘Data.Array.MArray’ is redundant
except perhaps to import instances from ‘Data.Array.MArray’
To import instances alone, use: import Data.Array.MArray()
|
19 | import Data.Array.MArray (freeze, newArray, readArray, writeArray)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:20:1: warning: [-Wunused-imports]
The import of ‘Data.Bifunctor’ is redundant
except perhaps to import instances from ‘Data.Bifunctor’
To import instances alone, use: import Data.Bifunctor()
|
20 | import Data.Bifunctor (Bifunctor (bimap))
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:21:1: warning: [-Wunused-imports]
The import of ‘Data.Bits’ is redundant
except perhaps to import instances from ‘Data.Bits’
To import instances alone, use: import Data.Bits()
|
21 | import Data.Bits (Bits (bit, testBit))
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:22:1: warning: [-Wunused-imports]
The import of ‘Data.Bool’ is redundant
except perhaps to import instances from ‘Data.Bool’
To import instances alone, use: import Data.Bool()
|
22 | import Data.Bool
| ^^^^^^^^^^^^^^^^
app/Main.hs:23:1: warning: [-Wunused-imports]
The import of ‘Data.ByteString.Char8’ is redundant
except perhaps to import instances from ‘Data.ByteString.Char8’
To import instances alone, use: import Data.ByteString.Char8()
|
23 | import Data.ByteString.Char8 (readInt)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:25:1: warning: [-Wunused-imports]
The import of ‘Data.Char’ is redundant
except perhaps to import instances from ‘Data.Char’
To import instances alone, use: import Data.Char()
|
25 | import Data.Char (ord)
| ^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:27:1: warning: [-Wunused-imports]
The import of ‘Data.Foldable’ is redundant
except perhaps to import instances from ‘Data.Foldable’
To import instances alone, use: import Data.Foldable()
|
27 | import Data.Foldable (for_)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:28:1: warning: [-Wunused-imports]
The import of ‘Data.Function’ is redundant
except perhaps to import instances from ‘Data.Function’
To import instances alone, use: import Data.Function()
|
28 | import Data.Function (on)
| ^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:29:1: warning: [-Wunused-imports]
The import of ‘Data.Graph’ is redundant
except perhaps to import instances from ‘Data.Graph’
To import instances alone, use: import Data.Graph()
|
29 | import Data.Graph (buildG, dfs)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:30:1: warning: [-Wunused-imports]
The qualified import of ‘Data.Heap’ is redundant
except perhaps to import instances from ‘Data.Heap’
To import instances alone, use: import Data.Heap()
|
30 | import qualified Data.Heap as H
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:31:1: warning: [-Wunused-imports]
The import of ‘Data.IORef’ is redundant
except perhaps to import instances from ‘Data.IORef’
To import instances alone, use: import Data.IORef()
|
31 | import Data.IORef (IORef, modifyIORef', newIORef)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:32:1: warning: [-Wunused-imports]
The qualified import of ‘Data.IntMap’ is redundant
except perhaps to import instances from ‘Data.IntMap’
To import instances alone, use: import Data.IntMap()
|
32 | import qualified Data.IntMap as IM
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:33:1: warning: [-Wunused-imports]
The qualified import of ‘Data.IntSet’ is redundant
except perhaps to import instances from ‘Data.IntSet’
To import instances alone, use: import Data.IntSet()
|
33 | import qualified Data.IntSet as IS
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:34:1: warning: [-Wunused-imports]
The import of ‘Data.Ix’ is redundant
except perhaps to import instances from ‘Data.Ix’
To import instances alone, use: import Data.Ix()
|
34 | import Data.Ix
| ^^^^^^^^^^^^^^
app/Main.hs:35:1: warning: [-Wunused-imports]
The qualified import of ‘Data.List’ is redundant
except perhaps to import instances from ‘Data.List’
To import instances alone, use: import Data.List()
|
35 | import qualified Data.List as L
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:37:1: warning: [-Wunused-imports]
The qualified import of ‘Data.Map.Strict’ is redundant
except perhaps to import instances from ‘Data.Map.Strict’
To import instances alone, use: import Data.Map.Strict()
|
37 | import qualified Data.Map.Strict as M
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:38:1: warning: [-Wunused-imports]
The import of ‘Data.Maybe’ is redundant
except perhaps to import instances from ‘Data.Maybe’
To import instances alone, use: import Data.Maybe()
|
38 | import Data.Maybe (fromJust, fromMaybe, isNothing)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:39:1: warning: [-Wunused-imports]
The import of ‘Data.Ord’ is redundant
except perhaps to import instances from ‘Data.Ord’
To import instances alone, use: import Data.Ord()
|
39 | import Data.Ord (Down (Down), comparing)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:40:1: warning: [-Wunused-imports]
The import of ‘Data.Sequence’ is redundant
except perhaps to import instances from ‘Data.Sequence’
To import instances alone, use: import Data.Sequence()
|
40 | import Data.Sequence (Seq ((:<|)), (|>))
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:41:1: warning: [-Wunused-imports]
The qualified import of ‘Data.Sequence’ is redundant
except perhaps to import instances from ‘Data.Sequence’
To import instances alone, use: import Data.Sequence()
|
41 | import qualified Data.Sequence as Seq
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:42:1: warning: [-Wunused-imports]
The qualified import of ‘Data.Set’ is redundant
except perhaps to import instances from ‘Data.Set’
To import instances alone, use: import Data.Set()
|
42 | import qualified Data.Set as S
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:43:1: warning: [-Wunused-imports]
The import of ‘Data.Tree’ is redundant
except perhaps to import instances from ‘Data.Tree’
To import instances alone, use: import Data.Tree()
|
43 | import Data.Tree (Tree (subForest), flatten)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:44:1: warning: [-Wunused-imports]
The qualified import of ‘Data.Vector.Algorithms.Intro’ is redundant
except perhaps to import instances from ‘Data.Vector.Algorithms.Intro’
To import instances alone, use: import Data.Vector.Algorithms.Intro()
|
44 | import qualified Data.Vector.Algorithms.Intro as VAI
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:45:1: warning: [-Wunused-imports]
The qualified import of ‘Data.Vector.Unboxed’ is redundant
except perhaps to import instances from ‘Data.Vector.Unboxed’
To import instances alone, use: import Data.Vector.Unboxed()
|
45 | import qualified Data.Vector.Unboxed as VU
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
app/Main.hs:49:1: warning: [-Wunused-imports]
The import of ‘System.Exit’ is redundant
except perhaps to import instances from ‘System.Exit’
To import instances alone, use: import System.Exit()
|
49 | import System.Exit
| ^^^^^^^^^^^^^^^^^^
app/Main.hs:61:15: warning: [-Wincomplete-patterns]
Pattern match(es) are non-exhaustive
In a case alternative:
Patterns of type ‘String’ not matched:
[]
(p:_) where p is not one of {'L', 'R'}
('L':_:_)
('R':_:_)
|
61 | case h of
| ^^^^^^^^^...