← Home
For problem statement at 1000-1999/1200-1299/1240-1249/1249/problemD2.txt this is a correct solution, but verifier at 1000-1999/1200-1299/1240-1249/1249/verifierD2.go ends with All 100 tests passed can you fix the verifier? package main

import (
	"bytes"
	"container/heap"
	"io"
	"os"
	"sort"
	"strconv"
)

type Segment struct {
	l, r, idx int
}

var rr []int

type MinHeap []int

func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool {
	if rr[h[i]] == rr[h[j]] {
		return h[i] < h[j]
	}
	return rr[h[i]] < rr[h[j]]
}
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

type MaxHeap []int

func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool {
	if rr[h[i]] == rr[h[j]] {
		return h[i] < h[j]
	}
	return rr[h[i]] > rr[h[j]]
}
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	p := 0
	nextInt := func() int {
		for p < len(data) && (data[p] < '0' || data[p] > '9') {
			p++
		}
		x := 0
		for p < len(data) && data[p] >= '0' && data[p] <= '9' {
			x = x*10 + int(data[p]-'0')
			p++
		}
		return x
	}

	n := nextInt()
	k := nextInt()

	segs := make([]Segment, n)
	rr = make([]int, n+1)
	for i := 0; i < n; i++ {
		l := nextInt()
		r := nextInt()
		segs[i] = Segment{l: l, r: r, idx: i + 1}
		rr[i+1] = r
	}

	sort.Slice(segs, func(i, j int) bool {
		if segs[i].l == segs[j].l {
			if segs[i].r == segs[j].r {
				return segs[i].idx < segs[j].idx
			}
			return segs[i].r < segs[j].r
		}
		return segs[i].l < segs[j].l
	})

	state := make([]int, n+1)
	for i := 1; i <= n; i++ {
		state[i] = 2
	}

	minH := &MinHeap{}
	maxH := &MaxHeap{}
	heap.Init(minH)
	heap.Init(maxH)

	active := 0
	ans := make([]int, 0)

	for _, s := range segs {
		for minH.Len() > 0 {
			id := (*minH)[0]
			if state[id] != 0 {
				heap.Pop(minH)
				continue
			}
			if rr[id] >= s.l {
				break
			}
			heap.Pop(minH)
			state[id] = 2
			active--
		}

		id := s.idx
		state[id] = 0
		heap.Push(minH, id)
		heap.Push(maxH, id)
		active++

		if active > k {
			for maxH.Len() > 0 {
				top := (*maxH)[0]
				if state[top] != 0 {
					heap.Pop(maxH)
					continue
				}
				heap.Pop(maxH)
				state[top] = 1
				active--
				ans = append(ans, top)
				break
			}
		}
	}

	var out bytes.Buffer
	out.WriteString(strconv.Itoa(len(ans)))
	out.WriteByte('\n')
	for i, v := range ans {
		if i > 0 {
			out.WriteByte(' ')
		}
		out.WriteString(strconv.Itoa(v))
	}
	out.WriteByte('\n')
	os.Stdout.Write(out.Bytes())
}