結果

問題 No.3298 K-th Slime
コンテスト
ユーザー ID 21712
提出日時 2026-04-27 02:53:25
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 127 ms / 2,000 ms
コード長 1,387 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 15,340 ms
コンパイル使用メモリ 272,864 KB
実行使用メモリ 7,936 KB
最終ジャッジ日時 2026-04-27 02:53:51
合計ジャッジ時間 14,646 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "os"
import bf "bufio"
import . "sort"
import "container/heap"

func main() {
	rd:=bf.NewReader(Stdin)
	wr:=bf.NewWriter(Stdout)
	defer wr.Flush()
	
	var n,k,q int
	Fscan(rd,&n,&k,&q)
	a := make([]int, n)
	for i := range a {
		Fscan(rd,&a[i])
	}
	Ints(a)
	
	lb := &PQ{ make([]int,0, n+q), func(x, y int) bool { return x > y } }
	ub := &PQ{ make([]int,0, n+q), func(x, y int) bool { return x < y } }
	
	for i, v := range a {
		if i < k {
			heap.Push(lb, v)
		} else {
			heap.Push(ub, v)
		}
	}
	
	
	for i := 0; i < q; i++ {
		var qc, x, y int
		Fscan(rd, &qc)
		switch qc {
			case 1:
				Fscan(rd,&x)
				if x < lb.Peek() {
					t := heap.Pop(lb)
					heap.Push(lb, x)
					heap.Push(ub, t)
				} else {
					heap.Push(ub, x)
				}
			case 2:
				Fscan(rd,&y)
				e := heap.Pop(lb).(int)
				heap.Push(ub, e+y)
				f := heap.Pop(ub)
				heap.Push(lb, f)
			case 3:
				Fprintln(wr, lb.Peek())
		}
	}
}


type PQ struct {
	buf []int
	less func(x, y int) bool
}

func (pq PQ)Len() int { return len(pq.buf) }
func (pq PQ)Swap(i, j int) { IntSlice(pq.buf).Swap(i, j) }
func (pq PQ)Less(i, j int) bool { return pq.less(pq.buf[i], pq.buf[j]) }
func (pq PQ)Peek() int { return pq.buf[0] }
func (pq *PQ)Push(v any ) {
	pq.buf = append(pq.buf, v.(int))
}
func (pq *PQ)Pop() any {
	old := pq.buf
	n := len(old)
	v := old[n-1]
	pq.buf = old[:n-1]
	return v
}
0