For problem statement at 1000-1999/1700-1799/1720-1729/1725/problemL.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1720-1729/1725/verifierL.go ends with All tests passed can you fix the verifier? package main
import (
"bufio"
"fmt"
"io"
"os"
"sort"
)
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 {
c := fs.data[fs.idx]
if c != ' ' && c != '\n' && c != '\r' && c != '\t' {
break
}
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 {
bit []int
}
func NewFenwick(n int) *Fenwick {
return &Fenwick{bit: make([]int, n+1)}
}
func (f *Fenwick) Add(i, v int) {
for i < len(f.bit) {
f.bit[i] += v
i += i & -i
}
}
func (f *Fenwick) Sum(i int) int {
res := 0
for i > 0 {
res += f.bit[i]
i -= i & -i
}
return res
}
func main() {
in := NewFastScanner()
out := bufio.NewWriterSize(os.Stdout, 1<<20)
defer out.Flush()
n := int(in.NextInt64())
ps := make([]int64, 0, max(0, n-1))
var sum int64
for i := 1; i <= n; i++ {
x := in.NextInt64()
sum += x
if i < n {
ps = append(ps, sum)
}
}
if sum < 0 {
fmt.Fprint(out, -1)
return
}
for _, p := range ps {
if p < 0 || p > sum {
fmt.Fprint(out, -1)
return
}
}
if len(ps) == 0 {
fmt.Fprint(out, 0)
return
}
vals := append([]int64(nil), ps...)
sort.Slice(vals, func(i, j int) bool { return vals[i] < vals[j] })
uniq := vals[:0]
for _, v := range vals {
if len(uniq) == 0 || uniq[len(uniq)-1] != v {
uniq = append(uniq, v)
}
}
vals = uniq
rank := make(map[int64]int, len(vals))
for i, v := range vals {
rank[v] = i + 1
}
fw := NewFenwick(len(vals))
var inv int64
seen := 0
for _, p := range ps {
r := rank[p]
inv += int64(seen - fw.Sum(r))
fw.Add(r, 1)
seen++
}
fmt.Fprint(out, inv)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}