For problem statement at 2000-2999/2000-2099/2010-2019/2018/problemE1.txt this is a correct solution, but verifier at 2000-2999/2000-2099/2010-2019/2018/verifierE1.go ends with mismatch on test 11
Input:
3
1
2
2
2
4 3
4 3
6
4 11 7 6 11 8
4 11 10 12 11 10
Expected: 1
2
3
Got: 1
2
4
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
)
type Segment struct {
l, r int
}
var maxTree []int
var addTree []int
func update(node, l, r, ql, qr, val int) {
if ql <= l && r <= qr {
addTree[node] += val
maxTree[node] += val
return
}
mid := (l + r) >> 1
left := node << 1
right := left | 1
if ql <= mid {
update(left, l, mid, ql, qr, val)
}
if qr > mid {
update(right, mid+1, r, ql, qr, val)
}
if maxTree[left] > maxTree[right] {
maxTree[node] = maxTree[left] + addTree[node]
} else {
maxTree[node] = maxTree[right] + addTree[node]
}
}
func main() {
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
var t int
fmt.Fscan(reader, &t)
for tc := 0; tc < t; tc++ {
var n int
fmt.Fscan(reader, &n)
lArr := make([]int, n)
rArr := make([]int, n)
for i := 0; i < n; i++ {
fmt.Fscan(reader, &lArr[i])
}
for i := 0; i < n; i++ {
fmt.Fscan(reader, &rArr[i])
}
segsByR := make([][]Segment, 2*n+2)
segsByL := make([][]Segment, 2*n+2)
for i := 0; i < n; i++ {
seg := Segment{lArr[i], rArr[i]}
segsByR[seg.r] = append(segsByR[seg.r], seg)
segsByL[seg.l] = append(segsByL[seg.l], seg)
}
treeSize := 8*n + 5
if len(maxTree) < treeSize {
maxTree = make([]int, treeSize)
addTree = make([]int, treeSize)
}
RMin := make([]int, 2*n+2)
bestAns := 0
for k := 1; k <= n; k++ {
for i := 0; i < treeSize; i++ {
maxTree[i] = 0
addTree[i] = 0
}
R := 1
for L := 1; L <= 2*n; L++ {
for maxTree[1] < k && R <= 2*n {
for _, seg := range segsByR[R] {
if seg.l >= L {
update(1, 1, 2*n, seg.l, R, 1)
}
}
R++
}
if maxTree[1] >= k {
RMin[L] = R - 1
} else {
RMin[L] = 2*n + 1
}
for _, seg := range segsByL[L] {
if seg.r < R {
update(1, 1, 2*n, seg.l, seg.r, -1)
}
}
}
cnt := 0
currL := 1
for currL <= 2*n {
rVal := RMin[currL]
if rVal > 2*n {
break
}
cnt++
currL = rVal + 1
}
if cnt*k > bestAns {
bestAns = cnt * k
}
if cnt == 0 {
break
}
}
fmt.Fprintln(writer, bestAns)
}
}