For problem statement at 1000-1999/1900-1999/1940-1949/1942/problemF.txt this is a correct solution, but verifier at 1000-1999/1900-1999/1940-1949/1942/verifierF.go ends with failed to build reference: REFERENCE_SOURCE_PATH not set
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
type SegTree struct {
root *STNode
n int
a []int64
}
type STNode struct {
l, r int
isLeaf bool
L, R int64
vals []int64
left, right *STNode
}
func (st *SegTree) eval(node *STNode, x int64) int64 {
if node.isLeaf {
if x <= 0 {
return -1
}
if x > 1000000005 {
return 2000000000
}
req := x
for i := node.r; i >= node.l; i-- {
if req <= 0 {
return -1
}
if req > 1000000005 {
return 2000000000
}
req = req*req - st.a[i]
}
if req <= 0 {
return -1
}
if req > 1000000005 {
return 2000000000
}
return req
} else {
if x < node.L {
return -1
}
if x > node.R {
return 2000000000
}
return node.vals[x-node.L]
}
}
func (st *SegTree) buildInternal(node *STNode) {
E := func(x int64) int64 {
return st.eval(node.left, st.eval(node.right, x))
}
low, high := int64(0), int64(1000000006)
ansL := int64(2000000000)
for low <= high {
mid := (low + high) / 2
if E(mid) != -1 {
ansL = mid
high = mid - 1
} else {
low = mid + 1
}
}
low, high = int64(0), int64(1000000006)
ansR := int64(-1)
for low <= high {
mid := (low + high) / 2
if E(mid) != 2000000000 {
ansR = mid
low = mid + 1
} else {
high = mid - 1
}
}
node.L = ansL
node.R = ansR
if ansL <= ansR {
node.vals = make([]int64, ansR-ansL+1)
for i := ansL; i <= ansR; i++ {
node.vals[i-ansL] = E(i)
}
} else {
node.vals = nil
}
}
func (st *SegTree) build(l, r int) *STNode {
node := &STNode{l: l, r: r}
if r-l+1 <= 20 {
node.isLeaf = true
return node
}
mid := (l + r) / 2
node.left = st.build(l, mid)
node.right = st.build(mid+1, r)
node.isLeaf = false
st.buildInternal(node)
return node
}
func (st *SegTree) update(node *STNode, k int) {
if node.isLeaf {
return
}
mid := (node.l + node.r) / 2
if k <= mid {
st.update(node.left, k)
} else {
st.update(node.right, k)
}
st.buildInternal(node)
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
buf := make([]byte, 1024*1024)
scanner.Buffer(buf, 10*1024*1024)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
scanInt := func() int {
scanner.Scan()
res, _ := strconv.Atoi(scanner.Text())
return res
}
scanInt64 := func() int64 {
scanner.Scan()
res, _ := strconv.ParseInt(scanner.Text(), 10, 64)
return res
}
scanner.Scan()
if scanner.Text() == "" {
return
}
n, _ := strconv.Atoi(scanner.Text())
q := scanInt()
a := make([]int64, n+1)
for i := 1; i <= n; i++ {
a[i] = scanInt64()
}
st := &SegTree{n: n, a: a}
st.root = st.build(1, n)
for i := 0; i < q; i++ {
k := scanInt()
x := scanInt64()
st.a[k] = x
st.update(st.root, k)
low, high := int64(0), int64(1000000005)
ans := int64(0)
for low <= high {
mid := (low + high) / 2
if st.eval(st.root, mid) == -1 {
ans = mid
low = mid + 1
} else {
high = mid - 1
}
}
fmt.Fprintln(out, ans)
}
}