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