For problem statement at 0-999/0-99/60-69/68/problemD.txt this is a correct solution, but verifier at 0-999/0-99/60-69/68/verifierD.go ends with All tests passed can you fix the verifier? package main
import (
"bufio"
"io"
"math/bits"
"os"
"strconv"
)
const (
segCap = 5500000
infVal = int32(1 << 30)
)
type FastScanner struct {
data []byte
idx int
n int
}
func NewFastScanner() *FastScanner {
data, _ := io.ReadAll(os.Stdin)
return &FastScanner{data: data, n: len(data)}
}
func (fs *FastScanner) nextInt() int {
for fs.idx < fs.n && fs.data[fs.idx] <= ' ' {
fs.idx++
}
val := 0
for fs.idx < fs.n && fs.data[fs.idx] > ' ' {
val = val*10 + int(fs.data[fs.idx]-'0')
fs.idx++
}
return val
}
func (fs *FastScanner) nextCmd() byte {
for fs.idx < fs.n && fs.data[fs.idx] <= ' ' {
fs.idx++
}
c := fs.data[fs.idx]
for fs.idx < fs.n && fs.data[fs.idx] > ' ' {
fs.idx++
}
return c
}
type IntMap struct {
keys []uint32
vals []int32
mask uint32
}
func NewIntMap(pow uint) *IntMap {
size := 1 << pow
return &IntMap{
keys: make([]uint32, size),
vals: make([]int32, size),
mask: uint32(size - 1),
}
}
func (m *IntMap) Get(k uint32) int32 {
i := (k * 2654435761) & m.mask
for {
key := m.keys[i]
if key == 0 {
return 0
}
if key == k {
return m.vals[i]
}
i = (i + 1) & m.mask
}
}
func (m *IntMap) Add(k uint32, delta int32) int32 {
i := (k * 2654435761) & m.mask
for {
key := m.keys[i]
if key == 0 {
m.keys[i] = k
m.vals[i] = delta
return delta
}
if key == k {
m.vals[i] += delta
return m.vals[i]
}
i = (i + 1) & m.mask
}
}
var (
h int
n int32
leftCh []int32
rightCh []int32
cntArr []int32
mnArr []int32
smnArr []int32
tagArr []int32
sumArr []int64
sumMap *IntMap
chargeMap *IntMap
)
func newNode(segLen int32, val int32) int32 {
idx := int32(len(mnArr))
leftCh = append(leftCh, 0)
rightCh = append(rightCh, 0)
cntArr = append(cntArr, segLen)
mnArr = append(mnArr, val)
smnArr = append(smnArr, infVal)
tagArr = append(tagArr, val)
sumArr = append(sumArr, int64(val)*int64(segLen))
return idx
}
func applyNode(idx int32, x int32) {
if x <= mnArr[idx] {
return
}
sumArr[idx] += int64(x-mnArr[idx]) * int64(cntArr[idx])
mnArr[idx] = x
if tagArr[idx] < x {
tagArr[idx] = x
}
}
func pushPartial(idx int32) {
t := tagArr[idx]
li := leftCh[idx]
if li != 0 && mnArr[li] < t {
applyNode(li, t)
}
ri := rightCh[idx]
if ri != 0 && mnArr[ri] < t {
applyNode(ri, t)
}
}
func pull(idx int32, segLen int32) {
half := segLen >> 1
t := tagArr[idx]
li := leftCh[idx]
var lmn, lsmn, lcnt int32
var lsum int64
if li == 0 {
lmn, lsmn, lcnt = t, infVal, half
lsum = int64(t) * int64(half)
} else {
lmn, lsmn, lcnt = mnArr[li], smnArr[li], cntArr[li]
lsum = sumArr[li]
}
ri := rightCh[idx]
var rmn, rsmn, rcnt int32
var rsum int64
if ri == 0 {
rmn, rsmn, rcnt = t, infVal, half
rsum = int64(t) * int64(half)
} else {
rmn, rsmn, rcnt = mnArr[ri], smnArr[ri], cntArr[ri]
rsum = sumArr[ri]
}
sumArr[idx] = lsum + rsum
if lmn < rmn {
mnArr[idx] = lmn
cntArr[idx] = lcnt
if lsmn < rmn {
smnArr[idx] = lsmn
} else {
smnArr[idx] = rmn
}
} else if lmn > rmn {
mnArr[idx] = rmn
cntArr[idx] = rcnt
if rsmn < lmn {
smnArr[idx] = rsmn
} else {
smnArr[idx] = lmn
}
} else {
mnArr[idx] = lmn
cntArr[idx] = lcnt + rcnt
if lsmn < rsmn {
smnArr[idx] = lsmn
} else {
smnArr[idx] = rsmn
}
}
}
func rangeWhole(idx int32, segLen int32, x int32) {
if x <= mnArr[idx] {
return
}
if x < smnArr[idx] || segLen == 1 {
applyNode(idx, x)
return
}
if tagArr[idx] < x {
tagArr[idx] = x
}
half := segLen >> 1
li := leftCh[idx]
if li != 0 {
rangeWhole(li, half, x)
}
ri := rightCh[idx]
if ri != 0 {
rangeWhole(ri, half, x)
}
pull(idx, segLen)
}
func updateToNode(idx int32, segLen int32, path uint32, depth int, x int32) {
if x <= mnArr[idx] {
return
}
if depth == 0 {
rangeWhole(idx, segLen, x)
return
}
pushPartial(idx)
half := segLen >> 1
if ((path >> uint(depth-1)) & 1) == 0 {
li := leftCh[idx]
if li == 0 {
li = newNode(half, tagArr[idx])
leftCh[idx] = li
}
updateToNode(li, half, path, depth-1, x)
} else {
ri := rightCh[idx]
if ri == 0 {
ri = newNode(half, tagArr[idx])
rightCh[idx] = ri
}
updateToNode(ri, half, path, depth-1, x)
}
pull(idx, segLen)
}
func subtreeChmax(v uint32, depth int, x int32) {
if x <= 0 {
return
}
var path uint32
if depth > 0 {
path = v ^ (uint32(1) << uint(depth))
}
updateToNode(1, n, path, depth, x)
}
func addVertex(v uint32, e int32) {
if e == 0 {
return
}
chargeV := chargeMap.Add(v, e)
var pathNodes [32]uint32
var pathSums [32]int32
cnt := 0
cur := v
for {
pathNodes[cnt] = cur
pathSums[cnt] = sumMap.Add(cur, e)
cnt++
if cur == 1 {
break
}
cur >>= 1
}
d := bits.Len32(v) - 1
if d == h {
subtreeChmax(v, d, chargeV)
} else {
lc := v << 1
rc := lc | 1
sumL := sumMap.Get(lc)
sumR := sumMap.Get(rc)
subtreeChmax(lc, d+1, chargeV+sumR)
subtreeChmax(rc, d+1, chargeV+sumL)
}
curDepth := d
for i := 0; i < cnt-1; i++ {
curNode := pathNodes[i]
parent := pathNodes[i+1]
sibling := curNode ^ 1
x := chargeMap.Get(parent) + pathSums[i]
subtreeChmax(sibling, curDepth, x)
curDepth--
}
}
func main() {
fs := NewFastScanner()
h = fs.nextInt()
q := fs.nextInt()
n = int32(1 << uint(h))
leftCh = make([]int32, 1, segCap)
rightCh = make([]int32, 1, segCap)
cntArr = make([]int32, 1, segCap)
mnArr = make([]int32, 1, segCap)
smnArr = make([]int32, 1, segCap)
tagArr = make([]int32, 1, segCap)
sumArr = make([]int64, 1, segCap)
newNode(n, 0)
sumMap = NewIntMap(22)
chargeMap = NewIntMap(18)
out := bufio.NewWriterSize(os.Stdout, 1<<20)
den := float64(int64(n))
for i := 0; i < q; i++ {
cmd := fs.nextCmd()
if cmd == 'a' {
v := uint32(fs.nextInt())
e := int32(fs.nextInt())
addVertex(v, e)
} else {
ans := float64(sumArr[1]) / den
var buf [64]byte
b := strconv.AppendFloat(buf[:0], ans, 'f', 10, 64)
out.Write(b)
out.WriteByte('\n')
}
}
out.Flush()
}