import Control.Applicative import Control.Monad import Data.Vector (Vector, (!), (//)) import qualified Data.Vector as V import Data.Vector.Mutable (IOVector, STVector) import qualified Data.Vector.Mutable as VM import Data.IntSet (IntSet) import qualified Data.IntSet as IS import Control.Monad.ST main :: IO () main = do [n, xlb, xrb] <- f solve [n, xlb, xrb] <$> replicateM n f >>= mapM_ print where f = map read <$> words <$> getLine solve :: [Int] -> [[Int]] -> [Int] solve [n, xlb, xrb] es = map f [1..n] where f i = if IS.member i st then 1 else 0 st = runST $ do v <- VM.replicate 1281 0 :: ST s (STVector s Int) ev <- V.thaw $ V.fromList es :: ST s (STVector s [Int]) forM_ [1 .. n] $ \i -> do [xl, _, xr, yd] <- VM.read ev (i-1) forM_ [max xlb xl .. min xrb xr] $ \x -> do j <- VM.read v x if j == 0 then VM.write v x i else do [_,_,_,yd'] <- VM.read ev (j-1) when (yd > yd') $ VM.write v x i foldM (\st x -> do i <- VM.read v x return $ IS.insert i st ) IS.empty [xlb .. xrb]