← Home
For problem statement at 2000-2999/2000-2099/2040-2049/2042/problemF.txt this is a correct solution, but verifier at 2000-2999/2000-2099/2040-2049/2042/verifierF.go ends with failed to parse input: EOF
exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"os"
)

type Node struct {
	sum  int64
	p    int64
	q    int64
	pq   int64
	qp   int64
	pqp  int64
	qpq  int64
	pqpq int64
}

const INF int64 = 10000000000000000

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

func max3(a, b, c int64) int64 {
	return max(max(a, b), c)
}

func max4(a, b, c, d int64) int64 {
	return max(max(a, b), max(c, d))
}

func max5(a, b, c, d, e int64) int64 {
	return max(max(a, b), max3(c, d, e))
}

func makeLeaf(a, b int64) Node {
	return Node{
		sum:  a,
		p:    b,
		q:    a + b,
		pq:   a + 2*b,
		qp:   -INF,
		pqp:  -INF,
		qpq:  -INF,
		pqpq: -INF,
	}
}

func merge(L, R Node) Node {
	var res Node
	res.sum = L.sum + R.sum

	rp_eff := R.p - L.sum
	rq_eff := R.q + L.sum
	rpqp_eff := R.pqp - L.sum
	rqpq_eff := R.qpq + L.sum

	res.p = max(L.p, rp_eff)
	res.q = max(L.q, rq_eff)

	res.pq = max3(L.pq, R.pq, L.p+rq_eff)
	res.qp = max3(L.qp, R.qp, L.q+rp_eff)

	res.pqp = max4(L.pqp, rpqp_eff, L.pq+rp_eff, L.p+R.qp)
	res.qpq = max4(L.qpq, rqpq_eff, L.qp+rq_eff, L.q+R.pq)

	res.pqpq = max5(L.pqpq, R.pqpq, L.pqp+rq_eff, L.pq+R.pq, L.p+rqpq_eff)

	return res
}

var tree []Node

func build(node, l, r int, a, b []int64) {
	if l == r {
		tree[node] = makeLeaf(a[l], b[l])
		return
	}
	mid := (l + r) / 2
	build(2*node, l, mid, a, b)
	build(2*node+1, mid+1, r, a, b)
	tree[node] = merge(tree[2*node], tree[2*node+1])
}

func updateA(node, l, r, p int, val int64) {
	if l == r {
		tree[node].sum = val
		tree[node].q = val + tree[node].p
		tree[node].pq = val + 2*tree[node].p
		return
	}
	mid := (l + r) / 2
	if p <= mid {
		updateA(2*node, l, mid, p, val)
	} else {
		updateA(2*node+1, mid+1, r, p, val)
	}
	tree[node] = merge(tree[2*node], tree[2*node+1])
}

func updateB(node, l, r, p int, val int64) {
	if l == r {
		tree[node].p = val
		tree[node].q = tree[node].sum + val
		tree[node].pq = tree[node].sum + 2*val
		return
	}
	mid := (l + r) / 2
	if p <= mid {
		updateB(2*node, l, mid, p, val)
	} else {
		updateB(2*node+1, mid+1, r, p, val)
	}
	tree[node] = merge(tree[2*node], tree[2*node+1])
}

func query(node, l, r, ql, qr int) Node {
	if ql <= l && r <= qr {
		return tree[node]
	}
	mid := (l + r) / 2
	if qr <= mid {
		return query(2*node, l, mid, ql, qr)
	}
	if ql > mid {
		return query(2*node+1, mid+1, r, ql, qr)
	}
	return merge(query(2*node, l, mid, ql, qr), query(2*node+1, mid+1, r, ql, qr))
}

func readInt(reader *bufio.Reader) int64 {
	var res int64
	var sign int64 = 1
	for {
		b, err := reader.ReadByte()
		if err != nil {
			break
		}
		if b == '-' {
			sign = -1
			continue
		}
		if b >= '0' && b <= '9' {
			res = int64(b - '0')
			for {
				b, err := reader.ReadByte()
				if err != nil || b < '0' || b > '9' {
					break
				}
				res = res*10 + int64(b-'0')
			}
			return res * sign
		}
	}
	return 0
}

func writeInt(writer *bufio.Writer, n int64) {
	if n == 0 {
		writer.WriteByte('0')
		writer.WriteByte('\n')
		return
	}
	if n < 0 {
		writer.WriteByte('-')
		n = -n
	}
	var buf [20]byte
	pos := 20
	for n > 0 {
		pos--
		buf[pos] = byte(n%10 + '0')
		n /= 10
	}
	writer.Write(buf[pos:])
	writer.WriteByte('\n')
}

func main() {
	reader := bufio.NewReaderSize(os.Stdin, 1024*1024)
	writer := bufio.NewWriterSize(os.Stdout, 1024*1024)
	defer writer.Flush()

	n := int(readInt(reader))
	if n == 0 {
		return
	}

	a := make([]int64, n+1)
	b := make([]int64, n+1)

	for i := 1; i <= n; i++ {
		a[i] = readInt(reader)
	}
	for i := 1; i <= n; i++ {
		b[i] = readInt(reader)
	}

	tree = make([]Node, 4*n+1)
	build(1, 1, n, a, b)

	q := int(readInt(reader))

	for i := 0; i < q; i++ {
		typ := int(readInt(reader))
		if typ == 1 {
			p := int(readInt(reader))
			x := readInt(reader)
			updateA(1, 1, n, p, x)
		} else if typ == 2 {
			p := int(readInt(reader))
			x := readInt(reader)
			updateB(1, 1, n, p, x)
		} else if typ == 3 {
			l := int(readInt(reader))
			r := int(readInt(reader))
			res := query(1, 1, n, l, r)
			writeInt(writer, res.pqpq)
		}
	}
}