For problem statement at 1000-1999/1900-1999/1920-1929/1928/problemF.txt this is a correct solution, but verifier at 1000-1999/1900-1999/1920-1929/1928/verifierF.go ends with panic: runtime error: index out of range [3] with length 3
goroutine 1 [running]:
main.(*Fenwick).Sum(...)
/home/ubuntu/codeforces/1000-1999/1900-1999/1920-1929/1928/1928F.go:29
main.contributionB(0x40000a0d58?)
/home/ubuntu/codeforces/1000-1999/1900-1999/1920-1929/1928/1928F.go:178 +0x1e8
main.addSegmentB(0x4)
/home/ubuntu/codeforces/1000-1999/1900-1999/1920-1929/1928/1928F.go:218 +0x90
main.main()
/home/ubuntu/codeforces/1000-1999/1900-1999/1920-1929/1928/1928F.go:326 +0xa44
exit status 2
reference error: exit status 1
exit status 1 can you fix the verifier? ```go
package main
import (
"io"
"os"
"strconv"
)
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) NextInt64() int64 {
for fs.idx < fs.n && fs.data[fs.idx] <= ' ' {
fs.idx++
}
sign := int64(1)
if fs.data[fs.idx] == '-' {
sign = -1
fs.idx++
}
var val int64
for fs.idx < fs.n {
c := fs.data[fs.idx]
if c < '0' || c > '9' {
break
}
val = val*10 + int64(c-'0')
fs.idx++
}
return sign * val
}
type Fenwick struct {
n int
tree []int64
}
func NewFenwick(n int) Fenwick {
if n < 1 {
n = 1
}
return Fenwick{n: n, tree: make([]int64, n+1)}
}
func (f *Fenwick) Add(i int, delta int64) {
for i <= f.n {
f.tree[i] += delta
i += i & -i
}
}
func (f *Fenwick) Sum(i int) int64 {
if i > f.n {
i = f.n
}
var res int64
for i > 0 {
res += f.tree[i]
i -= i & -i
}
return res
}
func (f *Fenwick) Kth(k int64) int {
idx := 0
step := 1
for (step << 1) <= f.n {
step <<= 1
}
for step > 0 {
next := idx + step
if next <= f.n && f.tree[next] < k {
idx = next
k -= f.tree[next]
}
step >>= 1
}
return idx + 1
}
type Dim struct {
n int
diff []int64
bad []bool
badBIT Fenwick
totBad int64
lenCnt Fenwick
lenS1 Fenwick
lenS2 Fenwick
lenS3 Fenwick
totBlocks int64
}
func NewDim(vals []int64, n int) *Dim {
d := &Dim{
n: n,
diff: make([]int64, n+1),
bad: make([]bool, n+1),
badBIT: NewFenwick(n - 1),
lenCnt: NewFenwick(n),
lenS1: NewFenwick(n),
lenS2: NewFenwick(n),
lenS3: NewFenwick(n),
}
prev := 0
for i := 1; i < n; i++ {
d.diff[i] = vals[i] - vals[i+1]
if d.diff[i] == 0 {
d.bad[i] = true
d.badBIT.Add(i, 1)
d.totBad++
d.addLen(i - prev)
prev = i
}
}
d.addLen(n - prev)
return d
}
func (d *Dim) addLen(l int) {
x := int64(l)
x2 := x * x
d.lenCnt.Add(l, 1)
d.lenS1.Add(l, x)
d.lenS2.Add(l, x2)
d.lenS3.Add(l, x2*x)
d.totBlocks++
}
func (d *Dim) removeLen(l int) {
x := int64(l)
x2 := x * x
d.lenCnt.Add(l, -1)
d.lenS1.Add(l, -x)
d.lenS2.Add(l, -x2)
d.lenS3.Add(l, -x2*x)
d.totBlocks--
}
func (d *Dim) Contribution(s int) int64 {
if s <= 0 {
return 0
}
x := s - 1
cL := d.lenCnt.Sum(x)
sumL := d.lenS1.Sum(x)
sum2L := d.lenS2.Sum(x)
sum3L := d.lenS3.Sum(x)
cR := d.totBlocks - cL
sumR := int64(d.n) - sumL
S := int64(s)
six := 3*S*(sum2L+sumL) + (sumL - sum3L) + 3*S*(S+1)*sumR + (S-S*S*S)*cR
return six / 6
}
func (d *Dim) prevSepBefore(i int) int {
cnt := d.badBIT.Sum(i - 1)
if cnt == 0 {
return 0
}
return d.badBIT.Kth(cnt)
}
func (d *Dim) nextSepAfter(i int) int {
cnt := d.badBIT.Sum(i)
if cnt == d.totBad {
return d.n
}
return d.badBIT.Kth(cnt + 1)
}
func (d *Dim) changeEdge(i int, newBad bool, other *Dim) int64 {
if newBad {
prev := d.prevSepBefore(i)
next := d.nextSepAfter(i)
whole := next - prev
left := i - prev
right := next - i
delta := -other.Contribution(whole) + other.Contribution(left) + other.Contribution(right)
d.removeLen(whole)
d.addLen(left)
d.addLen(right)
d.bad[i] = true
d.badBIT.Add(i, 1)
d.totBad++
return delta
}
prev := d.prevSepBefore(i)
next := d.nextSepAfter(i)
left := i - prev
right := next - i
delta := -other.Contribution(left) - other.Contribution(right) + other.Contribution(left+right)
d.removeLen(left)
d.removeLen(right)
d.addLen(left + right)
d.bad[i] = false
d.badBIT.Add(i, -1)
d.totBad--
return delta
}
func (d *Dim) applyEdgeDelta(i int, delta int64, other *Dim) int64 {
oldBad := d.bad[i]
d.diff[i] += delta
newBad := d.diff[i] == 0
if oldBad == newBad {
return 0
}
return d.changeEdge(i, newBad, other)
}
func (d *Dim) ApplyRange(l, r int, x int64, other *Dim) int64 {
var delta int64
if l > 1 {
delta += d.applyEdgeDelta(l-1, -x, other)
}
if r < d.n {
delta += d.applyEdgeDelta(r, x, other)
}
return delta
}
func main() {
fs := NewFastScanner()
n := int(fs.NextInt64())
m := int(fs.NextInt64())
q := int(fs.NextInt64())
a := make([]int64, n+1)
b := make([]int64, m+1)
for i := 1; i <= n; i++ {
a[i] = fs.NextInt64()
}
for i := 1; i <= m; i++ {
b[i] = fs.NextInt64()
}
rows := NewDim(a, n)
cols := NewDim(b, m)
var ans int64
prev := 0
for i := 1; i < n; i++ {
if rows.bad[i] {
ans += cols.Contribution(i - prev)
prev = i
}
}
ans += cols.Contribution(n - prev)
out := make([]byte, 0, (q+1)*24)
out = strconv.AppendInt(out, ans, 10)
out = append(out, '\n')
for ; q > 0; q-- {
t := int(fs.NextInt64())
l := int(fs.NextInt64())
r := int(fs.NextInt64())
x := fs.NextInt64()
if t == 1 {
ans += rows.ApplyRange(l, r, x, cols)
} else {
ans += cols.ApplyRange(l, r, x, rows)
}
out = strconv.AppendInt(out, ans, 10)
out = append(out, '\n')
}
os.Stdout.Write(out)
}
```