← 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 test 1 failed
input:
2 2
0.556732 0.542621
2 2.527093
2 0.960721

expected:1
1
got:16569
15967

exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

func isqrt(n int64) int64 {
	if n == 0 {
		return 0
	}
	x := int64(math.Sqrt(float64(n)))
	for (x+1)*(x+1) <= n {
		x++
	}
	for x*x > n {
		x--
	}
	return x
}

var a []int64

type Block struct {
	L, R int
	V0   int64
	T    int64
	Diff bool
}

const CAP = 2000000000

func eval_forward(L, R int, X int64) int64 {
	for i := L; i <= R; i++ {
		X = isqrt(a[i] + X)
	}
	return X
}

func (b *Block) rebuild() {
	v0 := eval_forward(b.L, b.R, 0)
	v1 := eval_forward(b.L, b.R, CAP)
	b.V0 = v0
	if v1 == v0 {
		b.Diff = false
		b.T = 0
	} else if v1 == v0+1 {
		b.Diff = true
		req := v1
		for i := b.R; i >= b.L; i-- {
			if req > CAP {
				req = CAP
			}
			val := req*req - a[i]
			if val < 0 {
				req = 0
			} else {
				req = val
			}
		}
		b.T = req
	} else {
		b.Diff = false
		b.T = -1
	}
}

func (b *Block) eval(X int64) int64 {
	if b.T == -1 {
		return eval_forward(b.L, b.R, X)
	}
	if b.Diff && X >= b.T {
		return b.V0 + 1
	}
	return b.V0
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]byte, 1024*1024*10), 1024*1024*10)
	scanner.Split(bufio.ScanWords)

	if !scanner.Scan() {
		return
	}
	n := parseInt(scanner.Text())
	scanner.Scan()
	q := parseInt(scanner.Text())

	a = make([]int64, n)
	for i := 0; i < n; i++ {
		scanner.Scan()
		a[i] = parseIn64(scanner.Text())
	}

	B := 400
	numBlocks := (n + B - 1) / B
	blocks := make([]Block, numBlocks)
	for i := 0; i < numBlocks; i++ {
		L := i * B
		R := L + B - 1
		if R >= n {
			R = n - 1
		}
		blocks[i] = Block{L: L, R: R}
		blocks[i].rebuild()
	}

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for i := 0; i < q; i++ {
		scanner.Scan()
		k := parseInt(scanner.Text())
		scanner.Scan()
		x := parseIn64(scanner.Text())

		idx := k - 1
		a[idx] = x
		b_idx := idx / B
		blocks[b_idx].rebuild()

		X := int64(0)
		for j := 0; j < numBlocks; j++ {
			X = blocks[j].eval(X)
		}
		fmt.Fprintln(out, X)
	}
}

func parseInt(s string) int {
	res := 0
	for i := 0; i < len(s); i++ {
		res = res*10 + int(s[i]-'0')
	}
	return res
}

func parseIn64(s string) int64 {
	var res int64 = 0
	for i := 0; i < len(s); i++ {
		res = res*10 + int64(s[i]-'0')
	}
	return res
}