Submission #42564516

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List
import qualified Data.IntMap as IM
import Data.Array.IO
-- mutable array版
main = do
  [n,k,q] <- bsGetLnInts
  if n == k then main1 n q else main2 n k q
-- Aとその合計を追跡する
main1 n q = do
  a <- newArray (1,n) 0 :: IO (IOArray Int Int)
  foldM_ (\s _ -> do
    x:y:_ <- bsGetLnInts
    z <- readArray a x
    writeArray a x y
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List

import qualified Data.IntMap as IM
import Data.Array.IO

-- mutable array版

main = do
  [n,k,q] <- bsGetLnInts
  if n == k then main1 n q else main2 n k q

-- Aとその合計を追跡する
main1 n q = do
  a <- newArray (1,n) 0 :: IO (IOArray Int Int)
  foldM_ (\s _ -> do
    x:y:_ <- bsGetLnInts
    z <- readArray a x
    writeArray a x y
    let s1 = s - z + y
    print s1
    return s1
    ) 0 [1..q]

main2 n k q = do
  a <- newArray (1,n) 0 :: IO (IOArray Int Int)
  foldM_ (\(lm, um, s0) _ -> do
    x:y:_ <- bsGetLnInts
-- ステップ1 : A[Xi]=Zを除く
    z <- readArray a x -- 指名された、消える値
    writeArray a x y
    let (lmax,_) = IM.findMax lm -- 下N-K個の最大値
    let (lm1, um1, s1) = if z <= lmax then (decr z lm, um, s0) else (decr lmax lm, incr lmax $ decr z um, s0 - z + lmax)
-- ステップ2 : Yを追加する
    let (umin,_) = IM.findMin um1 -- 上N個の最小値
    let (lm2, um2, s2) = if y <= umin then (incr y lm1, um1, s1) else (incr umin lm1, incr y $ decr umin um1, s1 - umin + y)
    print s2
    return (lm2, um2, s2)
    ) (IM.singleton 0 (n - k), IM.singleton 0 k, 0) [1..q]

bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

-- 値を一つ追加
incr x im = IM.insertWith (+) x 1 im
-- 値を一つ抜く
decr x im = IM.update f x im
  where
    f 1 = Nothing
    f k = Just $ pred k

Submission Info

Compile Error

Loaded package environment from /home/contestant/.ghc/x86_64-linux-8.8.3/environments/default

Judge Result