← Home
For problem statement at 0-999/500-599/540-549/542/problemB.txt this is a correct solution, but verifier at 0-999/500-599/540-549/542/verifierB.go ends with reference runtime error: exec: "ref542B.bin": executable file not found in $PATH can you fix the verifier? package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"sort"
)

type Event struct {
	X      int64
	DuckID int
}

type Int64Heap []int64

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

type SegTree struct {
	maxVal []int64
	lazy   []int64
}

func NewSegTree(size int) *SegTree {
	return &SegTree{
		maxVal: make([]int64, 4*size),
		lazy:   make([]int64, 4*size),
	}
}

func max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

func (st *SegTree) push(node int) {
	if st.lazy[node] != 0 {
		st.maxVal[2*node] += st.lazy[node]
		st.lazy[2*node] += st.lazy[node]
		st.maxVal[2*node+1] += st.lazy[node]
		st.lazy[2*node+1] += st.lazy[node]
		st.lazy[node] = 0
	}
}

func (st *SegTree) Add(node, l, r, ql, qr int, val int64) {
	if ql <= l && r <= qr {
		st.maxVal[node] += val
		st.lazy[node] += val
		return
	}
	st.push(node)
	mid := (l + r) / 2
	if ql <= mid {
		st.Add(2*node, l, mid, ql, qr, val)
	}
	if qr > mid {
		st.Add(2*node+1, mid+1, r, ql, qr, val)
	}
	st.maxVal[node] = max(st.maxVal[2*node], st.maxVal[2*node+1])
}

func (st *SegTree) QueryMax(node, l, r, ql, qr int) int64 {
	if ql <= l && r <= qr {
		return st.maxVal[node]
	}
	st.push(node)
	mid := (l + r) / 2
	res := int64(-2e18)
	if ql <= mid {
		res = max(res, st.QueryMax(2*node, l, mid, ql, qr))
	}
	if qr > mid {
		res = max(res, st.QueryMax(2*node+1, mid+1, r, ql, qr))
	}
	return res
}

func (st *SegTree) Set(node, l, r, idx int, val int64) {
	if l == r {
		st.maxVal[node] = val
		return
	}
	st.push(node)
	mid := (l + r) / 2
	if idx <= mid {
		st.Set(2*node, l, mid, idx, val)
	} else {
		st.Set(2*node+1, mid+1, r, idx, val)
	}
	st.maxVal[node] = max(st.maxVal[2*node], st.maxVal[2*node+1])
}

func upperBound(arr []int64, val int64) int {
	l, r := 0, len(arr)
	for l < r {
		mid := (l + r) / 2
		if arr[mid] <= val {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return l
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n int
	var r int64
	fmt.Fscan(reader, &n, &r)

	type Duck struct {
		L, R int64
	}
	ducks := make([]Duck, 0, n)
	startEvents := make([]Event, 0, n)
	endEvents := make([]Event, 0, n)

	for i := 0; i < n; i++ {
		var h, t int64
		fmt.Fscan(reader, &h, &t)
		if t < 0 {
			continue
		}
		L := max(0, h)
		R := t
		if L > R {
			continue
		}
		id := len(ducks)
		ducks = append(ducks, Duck{L, R})
		startEvents = append(startEvents, Event{L, id})
		endEvents = append(endEvents, Event{R, id})
	}

	sort.Slice(startEvents, func(i, j int) bool { return startEvents[i].X < startEvents[j].X })
	sort.Slice(endEvents, func(i, j int) bool { return endEvents[i].X < endEvents[j].X })

	hp := &Int64Heap{}
	heap.Init(hp)

	p1, p2 := 0, 0
	maxF := int64(0)
	yArray := []int64{-2e18}

	maxTreeSize := n + 2
	st := NewSegTree(maxTreeSize)
	st.Set(1, 0, maxTreeSize, 0, 0)

	for {
		nextX := int64(3e18)
		if p1 < len(startEvents) && startEvents[p1].X < nextX {
			nextX = startEvents[p1].X
		}
		if p2 < len(endEvents) && endEvents[p2].X < nextX {
			nextX = endEvents[p2].X
		}
		if hp.Len() > 0 && (*hp)[0] < nextX {
			nextX = (*hp)[0]
		}
		if nextX == 3e18 {
			break
		}

		var startsAtX, endsAtX []int
		for p1 < len(startEvents) && startEvents[p1].X == nextX {
			startsAtX = append(startsAtX, startEvents[p1].DuckID)
			p1++
		}
		for p2 < len(endEvents) && endEvents[p2].X == nextX {
			endsAtX = append(endsAtX, endEvents[p2].DuckID)
			p2++
		}
		for hp.Len() > 0 && (*hp)[0] == nextX {
			heap.Pop(hp)
		}

		for _, duckID := range startsAtX {
			L := ducks[duckID].L
			idx := upperBound(yArray, L-1)
			if idx-1 >= 0 {
				st.Add(1, 0, maxTreeSize, 0, idx-1, 1)
			}
		}

		idx := upperBound(yArray, nextX-r)
		if idx-1 >= 0 {
			val := st.QueryMax(1, 0, maxTreeSize, 0, idx-1)
			if val > maxF {
				maxF = val
				yArray = append(yArray, nextX)
				newIdx := len(yArray) - 1
				st.Set(1, 0, maxTreeSize, newIdx, val)
				heap.Push(hp, nextX+r)
			}
		}

		for _, duckID := range endsAtX {
			L := ducks[duckID].L
			idx := upperBound(yArray, L-1)
			if idx-1 >= 0 {
				st.Add(1, 0, maxTreeSize, 0, idx-1, -1)
			}
		}
	}

	fmt.Println(maxF)
}