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