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"
"math"
"os"
)
var reader *bufio.Reader
var writer *bufio.Writer
func nextInt64() int64 {
var res int64
var sign int64 = 1
var b byte
for {
b, _ = reader.ReadByte()
if b >= '0' && b <= '9' || b == '-' {
break
}
}
if b == '-' {
sign = -1
b, _ = reader.ReadByte()
}
res = int64(b - '0')
for {
b, _ = reader.ReadByte()
if b < '0' || b > '9' {
break
}
res = res*10 + int64(b-'0')
}
return res * sign
}
func isqrt(n int64) int64 {
if n == 0 {
return 0
}
x := int64(math.Sqrt(float64(n)))
for (x+1)*(x+1) <= n && (x+1)*(x+1) > 0 {
x++
}
for x*x > n {
x--
}
return x
}
type Node struct {
base int64
jump int64
}
const INF int64 = 2000000000
func buildBlock(a []int64) Node {
var base int64 = 0
for _, x := range a {
base = isqrt(base + x)
}
var v int64 = base + 1
for i := len(a) - 1; i >= 0; i-- {
if v >= INF {
v = INF
continue
}
v = v*v - a[i]
if v < 0 {
v = 0
}
}
return Node{base: base, jump: v}
}
func merge(L, R Node) Node {
out0 := R.base
if L.base >= R.jump {
out0 = R.base + 1
}
if L.jump >= INF {
return Node{base: out0, jump: INF}
}
out1 := R.base
if L.base+1 >= R.jump {
out1 = R.base + 1
}
if out0 == out1 {
return Node{base: out0, jump: INF}
}
return Node{base: out0, jump: L.jump}
}
var a []int64
var tree []Node
var B int = 40
func build(node, l, r int) {
if l == r {
tree[node] = buildBlock(a[l*B : l*B+B])
return
}
mid := (l + r) / 2
build(node*2, l, mid)
build(node*2+1, mid+1, r)
tree[node] = merge(tree[node*2], tree[node*2+1])
}
func update(node, l, r, idx int) {
if l == r {
tree[node] = buildBlock(a[l*B : l*B+B])
return
}
mid := (l + r) / 2
if idx <= mid {
update(node*2, l, mid, idx)
} else {
update(node*2+1, mid+1, r, idx)
}
tree[node] = merge(tree[node*2], tree[node*2+1])
}
func main() {
reader = bufio.NewReaderSize(os.Stdin, 65536)
writer = bufio.NewWriterSize(os.Stdout, 65536)
defer writer.Flush()
n := int(nextInt64())
q := int(nextInt64())
a = make([]int64, n)
for i := 0; i < n; i++ {
a[i] = nextInt64()
}
M := n / B
if M > 0 {
tree = make([]Node, 4*M)
build(1, 0, M-1)
}
for i := 0; i < q; i++ {
k := int(nextInt64()) - 1
x := nextInt64()
a[k] = x
if k < M*B {
update(1, 0, M-1, k/B)
}
var V int64 = 0
if M > 0 {
V = tree[1].base
}
for j := M * B; j < n; j++ {
V = isqrt(V + a[j])
}
fmt.Fprintln(writer, V)
}
}