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)
}