← Home
For problem statement at 0-999/900-999/990-999/992/problemE.txt this is a correct solution, but verifier at 0-999/900-999/990-999/992/verifierE.go ends with All tests passed can you fix the verifier? package main

import (
	"io/ioutil"
	"os"
)

var (
	Sum []int64
	Max []int64
	A   []int64
)

func max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

func build(node, L, R int) {
	if L == R {
		Sum[node] = A[L]
		Max[node] = A[L]
		return
	}
	mid := (L + R) / 2
	build(2*node, L, mid)
	build(2*node+1, mid+1, R)
	Sum[node] = Sum[2*node] + Sum[2*node+1]
	Max[node] = max(Max[2*node], Max[2*node+1])
}

func update(node, L, R, pos int, val int64) {
	if L == R {
		Sum[node] = val
		Max[node] = val
		return
	}
	mid := (L + R) / 2
	if pos <= mid {
		update(2*node, L, mid, pos, val)
	} else {
		update(2*node+1, mid+1, R, pos, val)
	}
	Sum[node] = Sum[2*node] + Sum[2*node+1]
	Max[node] = max(Max[2*node], Max[2*node+1])
}

func querySum(node, L, R, ql, qr int) int64 {
	if ql > R || qr < L {
		return 0
	}
	if ql <= L && R <= qr {
		return Sum[node]
	}
	mid := (L + R) / 2
	return querySum(2*node, L, mid, ql, qr) + querySum(2*node+1, mid+1, R, ql, qr)
}

func findFirst(node, L, R, ql int, val int64) int {
	if Max[node] < val || ql > R {
		return -1
	}
	if L == R {
		return L
	}
	mid := (L + R) / 2
	res := findFirst(2*node, L, mid, ql, val)
	if res != -1 {
		return res
	}
	return findFirst(2*node+1, mid+1, R, ql, val)
}

func main() {
	data, _ := ioutil.ReadAll(os.Stdin)
	ptr := 0

	nextInt := func() int {
		for ptr < len(data) && data[ptr] <= ' ' {
			ptr++
		}
		if ptr >= len(data) {
			return 0
		}
		res := 0
		for ptr < len(data) && data[ptr] > ' ' {
			res = res*10 + int(data[ptr]-'0')
			ptr++
		}
		return res
	}

	nextInt64 := func() int64 {
		for ptr < len(data) && data[ptr] <= ' ' {
			ptr++
		}
		if ptr >= len(data) {
			return 0
		}
		var res int64 = 0
		for ptr < len(data) && data[ptr] > ' ' {
			res = res*10 + int64(data[ptr]-'0')
			ptr++
		}
		return res
	}

	n := nextInt()
	q := nextInt()

	if n == 0 {
		return
	}

	A = make([]int64, n+1)
	for i := 1; i <= n; i++ {
		A[i] = nextInt64()
	}

	Sum = make([]int64, 4*n+1)
	Max = make([]int64, 4*n+1)
	build(1, 1, n)

	out := make([]byte, 0, 16*q)

	for i := 0; i < q; i++ {
		p := nextInt()
		x := nextInt64()

		A[p] = x
		update(1, 1, n, p, x)

		ans := -1
		if A[1] == 0 {
			ans = 1
		} else {
			idx := 1
			currSum := A[1]
			for idx < n {
				nextIdx := findFirst(1, 1, n, idx+1, currSum)
				if nextIdx == -1 {
					break
				}
				prevSum := querySum(1, 1, n, 1, nextIdx-1)
				if A[nextIdx] == prevSum {
					ans = nextIdx
					break
				}
				idx = nextIdx
				currSum = prevSum + A[nextIdx]
			}
		}
		out = appendInt(out, ans)
	}
	os.Stdout.Write(out)
}

func appendInt(b []byte, v int) []byte {
	if v == -1 {
		b = append(b, '-', '1', '\n')
		return b
	}
	if v == 0 {
		b = append(b, '0', '\n')
		return b
	}
	var buf [32]byte
	idx := 32
	for v > 0 {
		idx--
		buf[idx] = byte('0' + v%10)
		v /= 10
	}
	b = append(b, buf[idx:]...)
	b = append(b, '\n')
	return b
}