結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
|
提出日時 | 2020-01-03 19:29:25 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 364 ms / 3,000 ms |
コード長 | 7,098 bytes |
コンパイル時間 | 13,469 ms |
コンパイル使用メモリ | 224,724 KB |
実行使用メモリ | 36,992 KB |
最終ジャッジ日時 | 2024-11-22 19:21:19 |
合計ジャッジ時間 | 19,087 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
package mainimport ("bufio""errors""fmt""io""math""os""sort""strconv")/*********** I/O ***********/var (// ReadString returns a WORD string.ReadString func() stringstdout *bufio.Writer)func init() {ReadString = newReadString(os.Stdin)stdout = bufio.NewWriter(os.Stdout)}func newReadString(ior io.Reader) func() string {r := bufio.NewScanner(ior)// r.Buffer(make([]byte, 1024), int(1e+11)) // for AtCoderr.Buffer(make([]byte, 1024), int(1e+9)) // for Codeforces// Split sets the split function for the Scanner. The default split function is ScanLines.// Split panics if it is called after scanning has started.r.Split(bufio.ScanWords)return func() string {if !r.Scan() {panic("Scan failed")}return r.Text()}}// ReadInt returns an integer.func ReadInt() int {return int(readInt64())}func ReadInt2() (int, int) {return int(readInt64()), int(readInt64())}func ReadInt3() (int, int, int) {return int(readInt64()), int(readInt64()), int(readInt64())}func ReadInt4() (int, int, int, int) {return int(readInt64()), int(readInt64()), int(readInt64()), int(readInt64())}// ReadInt64 returns as integer as int64.func ReadInt64() int64 {return readInt64()}func ReadInt64_2() (int64, int64) {return readInt64(), readInt64()}func ReadInt64_3() (int64, int64, int64) {return readInt64(), readInt64(), readInt64()}func ReadInt64_4() (int64, int64, int64, int64) {return readInt64(), readInt64(), readInt64(), readInt64()}func readInt64() int64 {i, err := strconv.ParseInt(ReadString(), 0, 64)if err != nil {panic(err.Error())}return i}// ReadIntSlice returns an integer slice that has n integers.func ReadIntSlice(n int) []int {b := make([]int, n)for i := 0; i < n; i++ {b[i] = ReadInt()}return b}// ReadInt64Slice returns as int64 slice that has n integers.func ReadInt64Slice(n int) []int64 {b := make([]int64, n)for i := 0; i < n; i++ {b[i] = ReadInt64()}return b}// ReadFloat64 returns an float64.func ReadFloat64() float64 {return float64(readFloat64())}func readFloat64() float64 {f, err := strconv.ParseFloat(ReadString(), 64)if err != nil {panic(err.Error())}return f}// ReadFloatSlice returns an float64 slice that has n float64.func ReadFloat64Slice(n int) []float64 {b := make([]float64, n)for i := 0; i < n; i++ {b[i] = ReadFloat64()}return b}// ReadRuneSlice returns a rune slice.func ReadRuneSlice() []rune {return []rune(ReadString())}/*********** Debugging ***********/// ZeroPaddingRuneSlice returns binary expressions of integer n with zero padding.// For debugging use.func ZeroPaddingRuneSlice(n, digitsNum int) []rune {sn := fmt.Sprintf("%b", n)residualLength := digitsNum - len(sn)if residualLength <= 0 {return []rune(sn)}zeros := make([]rune, residualLength)for i := 0; i < len(zeros); i++ {zeros[i] = '0'}res := []rune{}res = append(res, zeros...)res = append(res, []rune(sn)...)return res}// Strtoi is a wrapper of strconv.Atoi().// If strconv.Atoi() returns an error, Strtoi calls panic.func Strtoi(s string) int {if i, err := strconv.Atoi(s); err != nil {panic(errors.New("[argument error]: Strtoi only accepts integer string"))} else {return i}}// PrintIntsLine returns integers string delimited by a space.func PrintIntsLine(A ...int) string {res := []rune{}for i := 0; i < len(A); i++ {str := strconv.Itoa(A[i])res = append(res, []rune(str)...)if i != len(A)-1 {res = append(res, ' ')}}return string(res)}// PrintIntsLine returns integers string delimited by a space.func PrintInts64Line(A ...int64) string {res := []rune{}for i := 0; i < len(A); i++ {str := strconv.FormatInt(A[i], 10) // 64bit int versionres = append(res, []rune(str)...)if i != len(A)-1 {res = append(res, ' ')}}return string(res)}// PrintDebug is wrapper of fmt.Fprintf(os.Stderr, format, a...)func PrintDebug(format string, a ...interface{}) {fmt.Fprintf(os.Stderr, format, a...)}/********** FAU standard libraries **********///fmt.Sprintf("%b\n", 255) // binary expression/********** I/O usage **********///str := ReadString()//i := ReadInt()//X := ReadIntSlice(n)//S := ReadRuneSlice()//a := ReadFloat64()//A := ReadFloat64Slice(n)//str := ZeroPaddingRuneSlice(num, 32)//str := PrintIntsLine(X...)/*******************************************************************/const MOD = 1000000000 + 7const ALPHABET_NUM = 26const INF_INT64 = math.MaxInt64const INF_BIT60 = 1 << 60const INF_INT32 = math.MaxInt32const INF_BIT30 = 1 << 30var q, k intvar queries [][]intfunc main() {q, k = ReadInt2()for i := 0; i < q; i++ {c := ReadInt()if c == 1 {v := ReadInt()queries = append(queries, []int{c, v})} else {queries = append(queries, []int{c})}}elems := []int{}for i := 0; i < q; i++ {if len(queries[i]) == 1 {continue}elems = append(elems, queries[i][1])}_, otop, ptoo := ZaAtsu1Dim(elems, 1)bit := NewBIT(200000 + 5)num := 0for i := 0; i < q; i++ {que := queries[i]if que[0] == 1 {v := que[1]vv := otop[v]bit.Add(vv, 1)num++} else {if num < k {fmt.Println(-1)} else {v := bit.LowerBound(k)vv := ptoo[v]fmt.Println(vv)bit.Add(v, -1)num--}}}}type BinaryIndexedTree struct {bit []intn intminPow2 int}// n(>=1) is number of elements of original datafunc NewBIT(n int) *BinaryIndexedTree {newBit := new(BinaryIndexedTree)newBit.bit = make([]int, n+1)newBit.n = nnewBit.minPow2 = 1for {if (newBit.minPow2 << 1) > n {break}newBit.minPow2 <<= 1}return newBit}// Sum of [1, i](1-based)func (b *BinaryIndexedTree) Sum(i int) int {s := 0for i > 0 {s += b.bit[i]i -= i & (-i)}return s}// Add x to i(1-based)func (b *BinaryIndexedTree) Add(i, x int) {for i <= b.n {b.bit[i] += xi += i & (-i)}}// LowerBound returns minimum i such that bit.Sum(i) >= w.func (b *BinaryIndexedTree) LowerBound(w int) int {if w <= 0 {return 0}x := 0for k := b.minPow2; k > 0; k /= 2 {if x+k <= b.n && b.bit[x+k] < w {w -= b.bit[x+k]x += k}}return x + 1}// ---// ZaAtsu1Dim returns 3 values.// pressed: pressed slice of the original slice// orgToPress: map for translating original value to pressed value// pressToOrg: reverse resolution of orgToPress// O(nlogn)func ZaAtsu1Dim(org []int, initVal int) (pressed []int, orgToPress, pressToOrg map[int]int) {pressed = make([]int, len(org))copy(pressed, org)sort.Sort(sort.IntSlice(pressed))orgToPress = make(map[int]int)for i := 0; i < len(org); i++ {if i == 0 {orgToPress[pressed[0]] = initValcontinue}if pressed[i-1] != pressed[i] {initVal++orgToPress[pressed[i]] = initVal}}for i := 0; i < len(org); i++ {pressed[i] = orgToPress[org[i]]}pressToOrg = make(map[int]int)for k, v := range orgToPress {pressToOrg[v] = k}return}