For problem statement at 1000-1999/1800-1899/1880-1889/1887/problemD.txt this is a correct solution, but verifier at 1000-1999/1800-1899/1880-1889/1887/verifierD.go ends with case 11 failed: expected Yes
Yes
No
No got Yes
Yes
Yes
No
exit status 1 can you fix the verifier? package main
import (
"bufio"
"io"
"os"
)
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
const INF int = 1e9
var (
treeA []int
treeM []NodeM
treeB []NodeB
)
type NodeM struct {
max_val int
lazy int
}
type NodeB struct {
min_val int
lazy_id bool
}
func buildA(node, l, r int, a []int) {
if l == r {
treeA[node] = a[l]
return
}
mid := (l + r) / 2
buildA(node*2, l, mid, a)
buildA(node*2+1, mid+1, r, a)
treeA[node] = max(treeA[node*2], treeA[node*2+1])
}
func findMaxIndexA(node, l, r, query_R, val int) int {
if l > query_R || treeA[node] <= val {
return 0
}
if l == r {
return l
}
mid := (l + r) / 2
res := findMaxIndexA(node*2+1, mid+1, r, query_R, val)
if res == 0 {
res = findMaxIndexA(node*2, l, mid, query_R, val)
}
return res
}
func buildM(node, l, r int) {
treeM[node].max_val = INF
treeM[node].lazy = 0
if l == r {
return
}
mid := (l + r) / 2
buildM(node*2, l, mid)
buildM(node*2+1, mid+1, r)
}
func applyM(node, val int) {
treeM[node].max_val = val
treeM[node].lazy = val
}
func pushDownM(node int) {
if treeM[node].lazy != 0 {
applyM(node*2, treeM[node].lazy)
applyM(node*2+1, treeM[node].lazy)
treeM[node].lazy = 0
}
}
func updateM(node, l, r, ql, qr, val int) {
if ql <= l && r <= qr {
applyM(node, val)
return
}
pushDownM(node)
mid := (l + r) / 2
if ql <= mid {
updateM(node*2, l, mid, ql, qr, val)
}
if qr > mid {
updateM(node*2+1, mid+1, r, ql, qr, val)
}
treeM[node].max_val = max(treeM[node*2].max_val, treeM[node*2+1].max_val)
}
func getFirstGreaterM(node, l, r, val int) int {
if treeM[node].max_val <= val {
return -1
}
if l == r {
return l
}
pushDownM(node)
mid := (l + r) / 2
res := getFirstGreaterM(node*2, l, mid, val)
if res != -1 {
return res
}
return getFirstGreaterM(node*2+1, mid+1, r, val)
}
func buildB(node, l, r int) {
treeB[node].min_val = INF
treeB[node].lazy_id = false
if l == r {
return
}
mid := (l + r) / 2
buildB(node*2, l, mid)
buildB(node*2+1, mid+1, r)
}
func applyB(node, l, r int) {
treeB[node].min_val = l
treeB[node].lazy_id = true
}
func pushDownB(node, l, r int) {
if treeB[node].lazy_id {
mid := (l + r) / 2
applyB(node*2, l, mid)
applyB(node*2+1, mid+1, r)
treeB[node].lazy_id = false
}
}
func updatePointB(node, l, r, idx, val int) {
if l == r {
treeB[node].min_val = val
return
}
pushDownB(node, l, r)
mid := (l + r) / 2
if idx <= mid {
updatePointB(node*2, l, mid, idx, val)
} else {
updatePointB(node*2+1, mid+1, r, idx, val)
}
treeB[node].min_val = min(treeB[node*2].min_val, treeB[node*2+1].min_val)
}
func updateRangeIdB(node, l, r, ql, qr int) {
if ql <= l && r <= qr {
applyB(node, l, r)
return
}
pushDownB(node, l, r)
mid := (l + r) / 2
if ql <= mid {
updateRangeIdB(node*2, l, mid, ql, qr)
}
if qr > mid {
updateRangeIdB(node*2+1, mid+1, r, ql, qr)
}
treeB[node].min_val = min(treeB[node*2].min_val, treeB[node*2+1].min_val)
}
func queryB(node, l, r, ql, qr int) int {
if ql <= l && r <= qr {
return treeB[node].min_val
}
pushDownB(node, l, r)
mid := (l + r) / 2
res := INF
if ql <= mid {
res = min(res, queryB(node*2, l, mid, ql, qr))
}
if qr > mid {
res = min(res, queryB(node*2+1, mid+1, r, ql, qr))
}
return res
}
type Query struct {
l, id int
}
func main() {
bytes, _ := io.ReadAll(os.Stdin)
var head int
nextInt := func() int {
for head < len(bytes) && bytes[head] <= 32 {
head++
}
if head >= len(bytes) {
return 0
}
res := 0
for head < len(bytes) && bytes[head] > 32 {
res = res*10 + int(bytes[head]-'0')
head++
}
return res
}
n := nextInt()
if n == 0 {
return
}
a := make([]int, n+1)
for i := 1; i <= n; i++ {
a[i] = nextInt()
}
q := nextInt()
queries := make([][]Query, n+1)
for i := 0; i < q; i++ {
l := nextInt()
r := nextInt()
queries[r] = append(queries[r], Query{l, i})
}
treeA = make([]int, 4*n+1)
treeM = make([]NodeM, 4*n+1)
treeB = make([]NodeB, 4*n+1)
buildA(1, 1, n, a)
buildM(1, 1, n)
buildB(1, 1, n)
ans := make([]string, q)
for i := 1; i <= n; i++ {
if i > 1 {
K := getFirstGreaterM(1, 1, n, a[i])
val := findMaxIndexA(1, 1, n, K, a[i])
updatePointB(1, 1, n, K, val)
if K+1 <= i-1 {
updateRangeIdB(1, 1, n, K+1, i-1)
}
if K <= i-1 {
updateM(1, 1, n, K, i-1, a[i])
}
}
for _, qry := range queries[i] {
if queryB(1, 1, n, qry.l, i-1) < qry.l {
ans[qry.id] = "Yes\n"
} else {
ans[qry.id] = "No\n"
}
}
}
out := bufio.NewWriter(os.Stdout)
for i := 0; i < q; i++ {
out.WriteString(ans[i])
}
out.Flush()
}