Contest Duration: ~ (local time) (90 minutes) Back to Home

Submission #524236

Source Code Expand

Copy
```{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
{-# LANGUAGE BangPatterns, TupleSections, OverloadedStrings #-}
import Control.Applicative
import Control.Exception (assert)
import Data.Array.ST (runSTUArray, runSTArray)
import Data.Bits
import qualified Data.ByteString.Char8 as B
import Data.Char
import Data.Function
import Data.Int
import Data.List
import qualified Data.Map as M
import qualified Data.IntMap as IM
import Data.Monoid
import qualified Data.Set as S
import qualified Data.IntSet as IS
import Data.STRef
import Data.Word
import GHC.Arr (Array, STArray, Ix(..))
import Debug.Trace

main :: IO ()
main = do
[n,m] <- map read.words <\$> getLine
sts <- parse.map (pred.readInt).B.words <\$> B.getContents
let res = solve n m sts
print \$ length res
putStr.unlines.map show \$ res

parse :: [Int] -> [(Int, Int)]
parse (s:t:sts) = (s,t) : parse sts
parse _ = []

solve :: Int -> Int -> [(Int, Int)] -> [Int]
solve n m sts = runST \$ do
segtree <- mkSegTree 0 (n-1) freqs
let go res (i:is) ((s,t):sts) = do
freq <- query s t segtree
if freq > 1 then do
go (i:res) is sts
else do
go res is sts
go res _  _ = return \$! reverse res
go [] [1..] sts

where
freqs :: UArray Int Int
!freqs = listArray(0,n-1).scanl1 (+) \$ map (unsafeAt arr) [0..n-1]
arr :: UArray Int Int
!arr = unsafeAccumArray (+) 0 (0,n) \$ go0 sts
go0 ((s,t):sts) = (s,1):(t+1,-1):go0 sts
go0 _ = []

------------------------------------------------------------------------------
bool :: a -> a -> Bool -> a
bool t f b=if b then t else f
rep, rev :: Monad m => Int -> (Int -> m ()) -> m ()
rep n f=foldr((>>).f)(return())[0..n-1]
rev n f=foldr((>>).f.negate)(return())[1-n..0]
for :: Monad m => Int -> Int -> (Int -> m ()) -> m ()
for a b f=foldr((>>).f)(return())[a..b]
{-# INLINE rep #-}
{-# INLINE rev #-}
{-# INLINE for #-}
whenM, unlessM :: Monad m => m Bool -> m () -> m ()
whenM p f=p>>=flip when f
unlessM p f=p>>=flip unless f
{-# INLINE whenM #-}
{-# INLINE unlessM #-}
foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM f a xs=foldr((>=>).flip f)return xs\$a
{-# INLINE foldM #-}
unsafeModify :: (MArray a e m, Ix i) => a i e -> Int -> (e -> e) -> m ()
unsafeModify a i f=unsafeRead a i>>=unsafeWrite a i.f
{-# INLINE unsafeModify #-}
(!) :: (IArray a e, Ix i) => a i e -> i -> e
(!) a i=assert(inRange(bounds a)i).unsafeAt a\$unsafeIndex(bounds a)i
{-# INLINE (!) #-}
readArray :: (MArray a e m, Ix i) => a i e -> i -> m e
writeArray :: (MArray a e m, Ix i) => a i e -> i -> e -> m ()
writeArray a i e=do lr<-getBounds a;assert(inRange lr i)\$unsafeWrite a(unsafeIndex lr i)e
{-# INLINE writeArray #-}
modifyArray :: (MArray a e m, Ix i) => a i e -> i -> (e -> e) -> m ()
modifyArray a i f=do lr<-getBounds a;assert(inRange lr i)\$unsafeModify a(unsafeIndex lr i)f
{-# INLINE modifyArray #-}

instance Monoid Int where
mempty = maxBound
mappend = min

data SegTree s m = Node {-# UNPACK #-} !Int {-# UNPACK #-} !Int !(STRef s m) !(SegTree s m) !(SegTree s m)
| Leaf {-# UNPACK #-} !Int !(STRef s m)

getVal :: SegTree s m -> ST s m
getVal (Node _ _ ref _ _) = readSTRef ref
getVal (Leaf _ ref)       = readSTRef ref

mkSegTree :: (Monoid m, IArray a m) => Int -> Int -> a Int m -> ST s (SegTree s m)
mkSegTree l r arr = go l r
where
go !l !r
| l < r = do
let !m = (l+r) `quot` 2
lt <- go l m
rt <- go (m+1) r
res <- mappend <\$> getVal lt <*> getVal rt
ref <- newSTRef \$! res
return \$! Node l r ref lt rt
| otherwise = do
ref <- newSTRef \$! unsafeAt arr l
return \$! Leaf l ref

update :: (Monoid m) => Int -> (m -> m) -> SegTree s m -> ST s ()
update key f segtree = go segtree
where
go (Node l r ref lt rt) = do
when (l<=key && key<=r) \$ do
if 2*key <= l+r then go lt else go rt
res <- mappend <\$> getVal lt <*> getVal rt
writeSTRef ref \$! res
go (Leaf k ref) = do
when (k==key) \$ do
modifySTRef' ref f

query :: (Monoid m) => Int -> Int -> SegTree s m -> ST s m
query kl kr segtree = go segtree
where
go (Node l r ref lt rt)
| r<kl  || kr<l  = return mempty
| kl<=l && r<=kr = readSTRef ref
| otherwise = do
res <- mappend <\$> go lt <*> go rt
return \$! res
go (Leaf k ref)
| kl<=k && k<=kr = readSTRef ref
| otherwise      = return mempty
```

#### Submission Info

Submission Time 2015-10-10 22:05:04+0900 B - ドキドキデート大作戦高橋君 cojna Haskell (Haskell Platform 2014.2.0.0) 100 5118 Byte AC 713 ms 84136 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Case Name Status Exec Time Memory