For problem statement at 0-999/700-799/780-789/785/problemE.txt this is a correct solution, but verifier at 0-999/700-799/780-789/785/verifierE.go ends with all tests passed can you fix the verifier? package main
import (
"io"
"os"
"sort"
"strconv"
)
const B = 700
var n int
var arr []int
var blocks [][]int
func min(a, b int) int {
if a < b {
return a
}
return b
}
func countRange(l, r, low, high int) int {
if l > r || low > high {
return 0
}
bl := (l - 1) / B
br := (r - 1) / B
cnt := 0
if bl == br {
for i := l; i <= r; i++ {
v := arr[i]
if v >= low && v <= high {
cnt++
}
}
return cnt
}
endBl := min(n, (bl+1)*B)
for i := l; i <= endBl; i++ {
v := arr[i]
if v >= low && v <= high {
cnt++
}
}
for b := bl + 1; b <= br-1; b++ {
s := blocks[b]
cnt += sort.SearchInts(s, high+1) - sort.SearchInts(s, low)
}
startBr := br*B + 1
for i := startBr; i <= r; i++ {
v := arr[i]
if v >= low && v <= high {
cnt++
}
}
return cnt
}
func updateBlock(b, oldVal, newVal int) {
s := blocks[b]
idx := sort.SearchInts(s, oldVal)
copy(s[idx:], s[idx+1:])
s = s[:len(s)-1]
pos := sort.SearchInts(s, newVal)
s = append(s, 0)
copy(s[pos+1:], s[pos:])
s[pos] = newVal
blocks[b] = s
}
func main() {
data, _ := io.ReadAll(os.Stdin)
idx := 0
nextInt := func() int {
for idx < len(data) && (data[idx] < '0' || data[idx] > '9') {
idx++
}
val := 0
for idx < len(data) && data[idx] >= '0' && data[idx] <= '9' {
val = val*10 + int(data[idx]-'0')
idx++
}
return val
}
n = nextInt()
q := nextInt()
arr = make([]int, n+1)
numBlocks := (n + B - 1) / B
blocks = make([][]int, numBlocks)
for b := 0; b < numBlocks; b++ {
st := b*B + 1
en := min(n, (b+1)*B)
s := make([]int, en-st+1)
for i := st; i <= en; i++ {
arr[i] = i
s[i-st] = i
}
blocks[b] = s
}
var inv int64
out := make([]byte, 0, q*16)
for ; q > 0; q-- {
l := nextInt()
r := nextInt()
if l != r {
if l > r {
l, r = r, l
}
x := arr[l]
y := arr[r]
var c int
if x < y {
if l+1 <= r-1 && x+1 <= y-1 {
c = countRange(l+1, r-1, x+1, y-1)
}
inv += int64(2*c + 1)
} else {
if l+1 <= r-1 && y+1 <= x-1 {
c = countRange(l+1, r-1, y+1, x-1)
}
inv -= int64(2*c + 1)
}
bl := (l - 1) / B
br := (r - 1) / B
updateBlock(bl, x, y)
updateBlock(br, y, x)
arr[l], arr[r] = y, x
}
out = strconv.AppendInt(out, inv, 10)
out = append(out, '\n')
}
os.Stdout.Write(out)
}