← Home
For problem statement at 1000-1999/1300-1399/1390-1399/1398/problemE.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1390-1399/1398/verifierE.go ends with case 3 failed: expected "7\n19\n40\n14" got "7\n19\n28\n14"
input:
4
1 7
0 6
1 2
1 -7
exit status 1 can you fix the verifier? ```go
package main

import (
	"io"
	"math"
	"os"
	"sort"
)

var buffer []byte
var cursor int

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

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

type Query struct {
	tp int
	d  int64
}

type Node struct {
	count int
	sum   int64
	minC  int64
	maxF  int64
}

var tree []Node

func build(node, l, r int) {
	tree[node].minC = math.MaxInt64
	tree[node].maxF = -1
	if l == r {
		return
	}
	mid := (l + r) / 2
	build(node<<1, l, mid)
	build(node<<1|1, mid+1, r)
}

func update(node, l, r, idx int, tp int, val int64, isAdd bool) {
	if l == r {
		if isAdd {
			tree[node].count = 1
			tree[node].sum = val
			if tp == 0 {
				tree[node].maxF = val
				tree[node].minC = math.MaxInt64
			} else {
				tree[node].minC = val
				tree[node].maxF = -1
			}
		} else {
			tree[node].count = 0
			tree[node].sum = 0
			tree[node].maxF = -1
			tree[node].minC = math.MaxInt64
		}
		return
	}
	mid := (l + r) / 2
	if idx <= mid {
		update(node<<1, l, mid, idx, tp, val, isAdd)
	} else {
		update(node<<1|1, mid+1, r, idx, tp, val, isAdd)
	}
	lc := node << 1
	rc := node<<1 | 1
	tree[node].count = tree[lc].count + tree[rc].count
	tree[node].sum = tree[lc].sum + tree[rc].sum

	tree[node].minC = tree[lc].minC
	if tree[rc].minC < tree[node].minC {
		tree[node].minC = tree[rc].minC
	}

	tree[node].maxF = tree[lc].maxF
	if tree[rc].maxF > tree[node].maxF {
		tree[node].maxF = tree[rc].maxF
	}
}

func queryTopSum(node, l, r, k int) int64 {
	if k == 0 {
		return 0
	}
	if tree[node].count <= k {
		return tree[node].sum
	}
	if l == r {
		return tree[node].sum
	}
	mid := (l + r) / 2
	rc := node<<1 | 1
	rightCount := tree[rc].count
	if rightCount >= k {
		return queryTopSum(rc, mid+1, r, k)
	} else {
		return tree[rc].sum + queryTopSum(node<<1, l, mid, k-rightCount)
	}
}

func getIdx(uniqueVals []int64, val int64) int {
	l, r := 0, len(uniqueVals)-1
	for l <= r {
		mid := (l + r) / 2
		if uniqueVals[mid] == val {
			return mid + 1
		} else if uniqueVals[mid] < val {
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	return -1
}

func appendInt64(b []byte, i int64) []byte {
	if i == 0 {
		return append(b, '0')
	}
	if i < 0 {
		b = append(b, '-')
		i = -i
	}
	var buf [20]byte
	pos := 20
	for i > 0 {
		pos--
		buf[pos] = byte('0' + i%10)
		i /= 10
	}
	return append(b, buf[pos:]...)
}

type int64Slice []int64

func (a int64Slice) Len() int           { return len(a) }
func (a int64Slice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a int64Slice) Less(i, j int) bool { return a[i] < a[j] }

func main() {
	buffer, _ = io.ReadAll(os.Stdin)
	n := nextInt()
	if n == 0 {
		return
	}

	queries := make([]Query, n)
	vals := make([]int64, n)

	for i := 0; i < n; i++ {
		queries[i].tp = nextInt()
		queries[i].d = nextInt64()
		if queries[i].d < 0 {
			vals[i] = -queries[i].d
		} else {
			vals[i] = queries[i].d
		}
	}

	sort.Sort(int64Slice(vals))
	uniqueVals := make([]int64, 0, n)
	for i, v := range vals {
		if i == 0 || v != vals[i-1] {
			uniqueVals = append(uniqueVals, v)
		}
	}

	M := len(uniqueVals)
	tree = make([]Node, 4*M+1)
	build(1, 1, M)

	L_count := 0
	out := make([]byte, 0, n*20)

	for _, q := range queries {
		val := q.d
		isAdd := true
		if val < 0 {
			val = -val
			isAdd = false
		}

		idx := getIdx(uniqueVals, val)

		if isAdd {
			if q.tp == 1 {
				L_count++
			}
		} else {
			if q.tp == 1 {
				L_count--
			}
		}

		update(1, 1, M, idx, q.tp, val, isAdd)

		base := tree[1].sum
		bonus := queryTopSum(1, 1, M, L_count)

		if L_count > 0 && tree[1].minC > tree[1].maxF {
			bonus -= tree[1].minC
			if tree[1].maxF != -1 {
				bonus += tree[1].maxF
			}
		}

		ans := base + bonus
		out = appendInt64(out, ans)
		out = append(out, '\n')
	}
	os.Stdout.Write(out)
}
```