For problem statement at 0-999/500-599/550-559/551/problemE.txt this is a correct solution, but verifier at 0-999/500-599/550-559/551/verifierE.go ends with All 100 tests passed can you fix the verifier? package main
import (
"bufio"
"io"
"os"
)
type fastReader struct {
buf []byte
pos int
}
func newFastReader() *fastReader {
b, _ := io.ReadAll(os.Stdin)
return &fastReader{buf: b, pos: 0}
}
func (r *fastReader) nextInt() int {
for r.pos < len(r.buf) && r.buf[r.pos] <= ' ' {
r.pos++
}
if r.pos >= len(r.buf) {
return 0
}
res := 0
for r.pos < len(r.buf) && r.buf[r.pos] > ' ' {
res = res*10 + int(r.buf[r.pos]-'0')
r.pos++
}
return res
}
func writeInt(out *bufio.Writer, n int) {
if n == 0 {
out.WriteByte('0')
out.WriteByte('\n')
return
}
var buf [20]byte
i := 19
for n > 0 {
buf[i] = byte('0' + n%10)
n /= 10
i--
}
out.Write(buf[i+1:])
out.WriteByte('\n')
}
func sortUint64(a []uint64) {
if len(a) < 2 {
return
}
pivot := a[len(a)/2]
i, j := 0, len(a)-1
for i <= j {
for a[i] < pivot {
i++
}
for a[j] > pivot {
j--
}
if i <= j {
a[i], a[j] = a[j], a[i]
i++
j--
}
}
if 0 < j {
sortUint64(a[:j+1])
}
if i < len(a)-1 {
sortUint64(a[i:])
}
}
const CAP = 2000000005
const B = 800
func main() {
in := newFastReader()
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
n := in.nextInt()
if n == 0 {
return
}
q := in.nextInt()
A := make([]int64, n)
for i := 0; i < n; i++ {
val := in.nextInt()
if val > CAP {
val = CAP
}
A[i] = int64(val)
}
numBlocks := (n + B - 1) / B
elements := make([][]uint64, numBlocks)
lazy := make([]int64, numBlocks)
rebuild := func(k int) {
start := k * B
end := start + B
if end > n {
end = n
}
for i := start; i < end; i++ {
elements[k][i-start] = (uint64(A[i]) << 20) | uint64(i)
}
sortUint64(elements[k])
}
for k := 0; k < numBlocks; k++ {
start := k * B
end := start + B
if end > n {
end = n
}
elements[k] = make([]uint64, end-start)
rebuild(k)
}
for i := 0; i < q; i++ {
typ := in.nextInt()
if typ == 1 {
l := in.nextInt() - 1
r := in.nextInt() - 1
x := in.nextInt()
startBlock := l / B
endBlock := r / B
if startBlock == endBlock {
for j := l; j <= r; j++ {
A[j] += int64(x)
if A[j] > CAP {
A[j] = CAP
}
}
rebuild(startBlock)
} else {
for j := l; j < (startBlock+1)*B; j++ {
A[j] += int64(x)
if A[j] > CAP {
A[j] = CAP
}
}
rebuild(startBlock)
for k := startBlock + 1; k < endBlock; k++ {
lazy[k] += int64(x)
if lazy[k] > CAP {
lazy[k] = CAP
}
}
for j := endBlock*B; j <= r; j++ {
A[j] += int64(x)
if A[j] > CAP {
A[j] = CAP
}
}
rebuild(endBlock)
}
} else if typ == 2 {
y := in.nextInt()
y64 := int64(y)
minIdx := -1
for k := 0; k < numBlocks; k++ {
target := y64 - lazy[k]
if target < 0 {
continue
}
left, right := 0, len(elements[k])
t := uint64(target) << 20
for left < right {
mid := (left + right) / 2
if elements[k][mid] >= t {
right = mid
} else {
left = mid + 1
}
}
if left < len(elements[k]) && (elements[k][left]>>20) == uint64(target) {
minIdx = int(elements[k][left] & 0xFFFFF)
break
}
}
if minIdx == -1 {
out.WriteString("-1\n")
continue
}
maxIdx := -1
for k := numBlocks - 1; k >= 0; k-- {
target := y64 - lazy[k]
if target < 0 {
continue
}
left, right := 0, len(elements[k])
t := (uint64(target) << 20) | 0xFFFFF
for left < right {
mid := (left + right) / 2
if elements[k][mid] > t {
right = mid
} else {
left = mid + 1
}
}
left--
if left >= 0 && (elements[k][left]>>20) == uint64(target) {
maxIdx = int(elements[k][left] & 0xFFFFF)
break
}
}
writeInt(out, maxIdx-minIdx)
}
}
}