← Home
For problem statement at 2000-2999/2000-2099/2070-2079/2071/problemF.txt this is a correct solution, but verifier at 2000-2999/2000-2099/2070-2079/2071/verifierF.go ends with failed to compile Java reference: exec: "javac": executable file not found in $PATH

exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
)

const MAXN = 200005

var maxVal []int32
var lazy []int32
var L []int32
var R []int32
var a []int

func build(node, l, r int) {
	maxVal[node] = 0
	lazy[node] = 0
	if l == r {
		return
	}
	mid := l + (r-l)/2
	build(node*2, l, mid)
	build(node*2+1, mid+1, r)
}

func pushDown(node int) {
	if lazy[node] != 0 {
		lz := lazy[node]
		lazy[node*2] += lz
		maxVal[node*2] += lz
		lazy[node*2+1] += lz
		maxVal[node*2+1] += lz
		lazy[node] = 0
	}
}

func updatePoint(node, l, r, idx int, val int32) {
	if l == r {
		maxVal[node] = val
		return
	}
	pushDown(node)
	mid := l + (r-l)/2
	if idx <= mid {
		updatePoint(node*2, l, mid, idx, val)
	} else {
		updatePoint(node*2+1, mid+1, r, idx, val)
	}
	if maxVal[node*2] > maxVal[node*2+1] {
		maxVal[node] = maxVal[node*2]
	} else {
		maxVal[node] = maxVal[node*2+1]
	}
}

func updateRange(node, l, r, ql, qr int, val int32) {
	if l > qr || r < ql {
		return
	}
	if ql <= l && r <= qr {
		maxVal[node] += val
		lazy[node] += val
		return
	}
	pushDown(node)
	mid := l + (r-l)/2
	updateRange(node*2, l, mid, ql, qr, val)
	updateRange(node*2+1, mid+1, r, ql, qr, val)
	if maxVal[node*2] > maxVal[node*2+1] {
		maxVal[node] = maxVal[node*2]
	} else {
		maxVal[node] = maxVal[node*2+1]
	}
}

func findFirst(node, l, r, ql, qr int, X int32) int {
	if l > qr || r < ql || maxVal[node] < X {
		return -1
	}
	if l == r {
		return l
	}
	pushDown(node)
	mid := l + (r-l)/2
	res := findFirst(node*2, l, mid, ql, qr, X)
	if res == -1 {
		res = findFirst(node*2+1, mid+1, r, ql, qr, X)
	}
	return res
}

func findLast(node, l, r, ql, qr int, X int32) int {
	if l > qr || r < ql || maxVal[node] < X {
		return -1
	}
	if l == r {
		return l
	}
	pushDown(node)
	mid := l + (r-l)/2
	res := findLast(node*2+1, mid+1, r, ql, qr, X)
	if res == -1 {
		res = findLast(node*2, l, mid, ql, qr, X)
	}
	return res
}

func collect(node, l, r int, out []int32) {
	if l == r {
		out[l] = maxVal[node]
		return
	}
	pushDown(node)
	mid := l + (r-l)/2
	collect(node*2, l, mid, out)
	collect(node*2+1, mid+1, r, out)
}

func check(n, k, p int) bool {
	build(1, 1, n)
	for j := n; j >= 1; j-- {
		updatePoint(1, 1, n, j, 1)
		if j < n {
			X := int32(p - a[j])
			idx := findFirst(1, 1, n, j+1, n, X)
			if idx != -1 {
				updateRange(1, 1, n, idx, n, 1)
			}
		}
	}
	collect(1, 1, n, L)

	build(1, 1, n)
	for j := 1; j <= n; j++ {
		updatePoint(1, 1, n, j, 1)
		if j > 1 {
			X := int32(p - a[j])
			idx := findLast(1, 1, n, 1, j-1, X)
			if idx != -1 {
				updateRange(1, 1, n, 1, idx, 1)
			}
		}
	}
	collect(1, 1, n, R)

	target := int32(n - k)
	for i := 1; i <= n; i++ {
		if a[i] >= p {
			if L[i]+R[i]-1 >= target {
				return true
			}
		}
	}
	return false
}

func readInt(reader *bufio.Reader) int {
	var n int
	var sign int = 1
	c, err := reader.ReadByte()
	for err == nil && (c < '0' || c > '9') && c != '-' {
		c, err = reader.ReadByte()
	}
	if c == '-' {
		sign = -1
		c, err = reader.ReadByte()
	}
	for err == nil && c >= '0' && c <= '9' {
		n = n*10 + int(c-'0')
		c, err = reader.ReadByte()
	}
	return n * sign
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	maxVal = make([]int32, 4*MAXN+5)
	lazy = make([]int32, 4*MAXN+5)
	L = make([]int32, MAXN+5)
	R = make([]int32, MAXN+5)
	a = make([]int, MAXN+5)

	t := readInt(reader)
	for i := 0; i < t; i++ {
		n := readInt(reader)
		k := readInt(reader)
		for j := 1; j <= n; j++ {
			a[j] = readInt(reader)
		}

		low := -200005
		high := 1000000005
		ans := low
		for low <= high {
			mid := low + (high-low)/2
			if check(n, k, mid) {
				ans = mid
				low = mid + 1
			} else {
				high = mid - 1
			}
		}
		fmt.Fprintln(writer, ans)
	}
}