← Home
For problem statement at 1000-1999/1100-1199/1180-1189/1187/problemD.txt this is a correct solution, but verifier at 1000-1999/1100-1199/1180-1189/1187/verifierD.go ends with case 15 failed: expected
NO
YES
got
NO
NO
input:2
7
5 2 6 7 5 4 5
7 4 7 7 5 6 2
3
2 3 1
1 3 2
exit status 1 can you fix the verifier? package main

import (
	"bytes"
	"io"
	"os"
)

const INF = int(1e9)
const MAXN = 300000
const MAXSIZE = 1 << 19

var data []byte
var idx int

func nextInt() int {
	n := len(data)
	for idx < n {
		c := data[idx]
		if c >= '0' && c <= '9' {
			break
		}
		idx++
	}
	v := 0
	for idx < n {
		c := data[idx]
		if c < '0' || c > '9' {
			break
		}
		v = v*10 + int(c-'0')
		idx++
	}
	return v
}

func main() {
	data, _ = io.ReadAll(os.Stdin)

	pos := make([][]int, MAXN+1)
	ptr := make([]int, MAXN+1)
	tree := make([]int, 2*MAXSIZE)
	usedBuf := make([]int, 0, MAXN)

	t := nextInt()
	var out bytes.Buffer

	for ; t > 0; t-- {
		n := nextInt()
		used := usedBuf[:0]

		for i := 1; i <= n; i++ {
			x := nextInt()
			if len(pos[x]) == 0 {
				used = append(used, x)
			}
			pos[x] = append(pos[x], i)
		}

		size := 1
		for size < n {
			size <<= 1
		}
		limit := size << 1
		for i := 1; i < limit; i++ {
			tree[i] = INF
		}
		for _, x := range used {
			tree[size+x-1] = pos[x][0]
		}
		for i := size - 1; i > 0; i-- {
			if tree[i<<1] < tree[i<<1|1] {
				tree[i] = tree[i<<1]
			} else {
				tree[i] = tree[i<<1|1]
			}
		}

		ok := true
		for i := 0; i < n; i++ {
			x := nextInt()
			if !ok {
				continue
			}
			if ptr[x] >= len(pos[x]) {
				ok = false
				continue
			}
			p := pos[x][ptr[x]]

			if x > 1 {
				l, r := size, size+x-1
				minv := INF
				for l < r {
					if l&1 == 1 {
						if tree[l] < minv {
							minv = tree[l]
						}
						l++
					}
					if r&1 == 1 {
						r--
						if tree[r] < minv {
							minv = tree[r]
						}
					}
					l >>= 1
					r >>= 1
				}
				if minv < p {
					ok = false
					continue
				}
			}

			ptr[x]++
			nv := INF
			if ptr[x] < len(pos[x]) {
				nv = pos[x][ptr[x]]
			}
			id := size + x - 1
			tree[id] = nv
			for id >>= 1; id > 0; id >>= 1 {
				if tree[id<<1] < tree[id<<1|1] {
					tree[id] = tree[id<<1]
				} else {
					tree[id] = tree[id<<1|1]
				}
			}
		}

		if ok {
			out.WriteString("YES\n")
		} else {
			out.WriteString("NO\n")
		}

		for _, x := range used {
			pos[x] = pos[x][:0]
			ptr[x] = 0
		}
	}

	os.Stdout.Write(out.Bytes())
}