Submission #523829


Source Code Expand

Copy
{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
{-# LANGUAGE BangPatterns, TupleSections, OverloadedStrings #-}
import Control.Applicative
import Control.Exception (assert)
import Control.Monad hiding (foldM)
import Control.Monad.ST
import Data.Array.Base hiding (readArray, writeArray)
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 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 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 = go [1..] sts
   where
     go (i:is) ((s,t):sts)
       | queryRMQ rmq (s-1) (t-1) > 1 = i : go is sts
       | otherwise = go is sts
     go _ _ = []
     !rmq = mkRMQ n freqs
     !freqs = listArray(0,n-1).scanl1 (+) $ map (fromIntegral.unsafeAt arr) [0..n-1]
     arr :: UArray Int Int
     !arr = unsafeAccumArray (+) 0 (0,n) $ go0 sts
     go0 ((s,t):sts) = (s-1,1):(t,-1):go0 sts
     go0 _ = []
   


------------------------------------------------------------------------------
bool :: a -> a -> Bool -> a
bool t f b=if b then t else f
readInt :: B.ByteString -> Int
readInt bs=case B.readInt bs of{Just(n,_)->n;_->error$"readInt error : bs = "++show bs;}
readInteger :: B.ByteString -> Integer
readInteger bs=case B.readInteger bs of{Just(n,_)->n;_->error$"readInteger error : bs = "++show bs;}
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
readArray a i=do lr<-getBounds a;assert(inRange lr i)$unsafeRead a$unsafeIndex lr i
{-# INLINE readArray #-}
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 #-}


type RMQ = UArray (Int,Int) Int

mkRMQ :: Int -> UArray Int Int -> RMQ
mkRMQ n arr = runSTUArray $ do
  rmq <- newArray_ ((0,0),(log2 n,n-1)) :: ST s (STUArray s (Int,Int) Int)

  rep n $ \i -> do
    unsafeWrite rmq i $ unsafeAt arr i

  for 1 (log2 n)$ \logk -> do
    for ((logk-1)*n) ((logk-1)*n+n-1) $ \ki -> do
      unsafeRead rmq ki >>= unsafeWrite rmq (ki+n)
    let !k = 1 `unsafeShiftL` (logk-1)
    rep (n-k) $ \i -> do
      xi  <- unsafeRead rmq $ logk*n+i
      xik <- unsafeRead rmq $ logk*n+i+k
      when (xik < xi) $ do
        unsafeWrite rmq (logk*n+i) xik

  return rmq      

queryRMQ :: RMQ -> Int -> Int -> Int
queryRMQ rmq l r = (unsafeAt rmq $ log2d * n + l) `min` (unsafeAt rmq $ log2d * n + r - (1 `unsafeShiftL` log2d) + 1)
   where
     !log2d = log2 $ r - l
     !n = numElements rmq
{-# INLINE queryRMQ #-}

infixl 8 .<<. , .>>.
(.<<.), (.>>.) :: (Bits a, Num a) => a -> Int -> a
(.<<.) = unsafeShiftL
(.>>.) = unsafeShiftR
{-# INLINE (.<<.) #-}
{-# INLINE (.>>.) #-}

log2 :: Int -> Int
log2 x = unsafeAt magic32 . fromIntegral $ (e * 0x07c4acdd) .>>. 27
   where
     w :: Word
     w = fromIntegral x
     !a = w .|. (w .>>. 1)
     !b = a .|. (a .>>. 2)
     !c = b .|. (b .>>. 4)
     !d = c .|. (c .>>. 8)
     !e = d .|. (d .>>. 16)

magic32 :: UArray Int Int
magic32 = listArray (0,31) [  0,  9,  1, 10, 13, 21,  2, 29
                           , 11, 14, 16, 18, 22, 25,  3, 30
                           ,  8, 12, 20, 28, 15, 17, 24,  7
                           , 19, 27, 23,  6, 26,  5,  4, 31
                           ]

Submission Info

Submission Time
Task B - ドキドキデート大作戦高橋君
User cojna
Language Haskell (Haskell Platform 2014.2.0.0)
Score 0
Code Size 4930 Byte
Status
Exec Time 341 ms
Memory 25240 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
Subtask1 0 / 30 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All 0 / 70 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt 30 ms 1432 KB
subtask0_sample_02.txt 28 ms 1432 KB
subtask0_sample_03.txt 30 ms 1424 KB
subtask1_01.txt 164 ms 23836 KB
subtask1_02.txt 163 ms 23832 KB
subtask1_03.txt 341 ms 25100 KB
subtask1_04.txt 273 ms 18964 KB
subtask1_05.txt 323 ms 25240 KB
subtask1_06.txt 30 ms 1804 KB
subtask1_07.txt 28 ms 1424 KB
subtask1_08.txt 29 ms 1300 KB
subtask1_09.txt 29 ms 1428 KB
subtask2_01.txt 151 ms 22028 KB
subtask2_02.txt 161 ms 23832 KB
subtask2_03.txt 163 ms 1628 KB
subtask2_04.txt 160 ms 1424 KB
subtask2_05.txt 166 ms 1552 KB
subtask2_06.txt 167 ms 1432 KB
subtask2_07.txt 164 ms 1436 KB
subtask2_08.txt 325 ms 25108 KB