← Home
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()
}