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