← Home
For problem statement at 0-999/300-399/310-319/319/problemE.txt this is a correct solution, but verifier at 0-999/300-399/310-319/319/verifierE.go ends with  can you fix the verifier? package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"sort"
)

const INF = 2000000007

type Item struct {
	R, id int
}

type PQ []Item

func (pq PQ) Len() int           { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].R > pq[j].R }
func (pq PQ) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x any)        { *pq = append(*pq, x.(Item)) }
func (pq *PQ) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[:n-1]
	return item
}
func (pq PQ) Top() Item {
	if len(pq) == 0 {
		return Item{-INF, -1}
	}
	return pq[0]
}

type TreeNode struct {
	max_R int
	leaf  int
}

var (
	tree []TreeNode
	pqs  []PQ
)

func build(node, l, r int) {
	if l == r {
		tree[node] = TreeNode{-INF, l}
		return
	}
	mid := l + (r-l)/2
	build(2*node, l, mid)
	build(2*node+1, mid+1, r)
	tree[node] = TreeNode{-INF, l}
}

func update(node, l, r, p, val int) {
	if l == r {
		tree[node] = TreeNode{val, l}
		return
	}
	mid := l + (r-l)/2
	if p <= mid {
		update(2*node, l, mid, p, val)
	} else {
		update(2*node+1, mid+1, r, p, val)
	}
	if tree[2*node].max_R > tree[2*node+1].max_R {
		tree[node] = tree[2*node]
	} else {
		tree[node] = tree[2*node+1]
	}
}

func query(node, l, r, ql, qr int) TreeNode {
	if ql > r || qr < l {
		return TreeNode{-INF, -1}
	}
	if ql <= l && r <= qr {
		return tree[node]
	}
	mid := l + (r-l)/2
	left := query(2*node, l, mid, ql, qr)
	right := query(2*node+1, mid+1, r, ql, qr)
	if left.max_R > right.max_R {
		return left
	}
	return right
}

var parent []int

func find(i int) int {
	if parent[i] == i {
		return i
	}
	parent[i] = find(parent[i])
	return parent[i]
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	buf := make([]byte, 1024*1024)
	scanner.Buffer(buf, 10*1024*1024)
	scanner.Split(bufio.ScanWords)

	scanInt := func() int {
		scanner.Scan()
		res := 0
		sign := 1
		for _, b := range scanner.Bytes() {
			if b == '-' {
				sign = -1
			} else {
				res = res*10 + int(b-'0')
			}
		}
		return res * sign
	}

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	if !scanner.Scan() {
		return
	}
	res := 0
	for _, b := range scanner.Bytes() {
		res = res*10 + int(b-'0')
	}
	n := res

	type Query struct {
		t, a, b int
	}
	queries := make([]Query, n)
	coords := make([]int, 0, 2*n)

	for i := 0; i < n; i++ {
		queries[i].t = scanInt()
		queries[i].a = scanInt()
		queries[i].b = scanInt()
		if queries[i].t == 1 {
			coords = append(coords, queries[i].a, queries[i].b)
		}
	}

	sort.Ints(coords)
	unique_coords := make([]int, 0, len(coords))
	for i, v := range coords {
		if i == 0 || v != coords[i-1] {
			unique_coords = append(unique_coords, v)
		}
	}

	M := len(unique_coords)
	if M == 0 {
		return
	}

	get_comp := func(val int) int {
		l, r := 0, M-1
		for l <= r {
			mid := l + (r-l)/2
			if unique_coords[mid] == val {
				return mid
			} else if unique_coords[mid] < val {
				l = mid + 1
			} else {
				r = mid - 1
			}
		}
		return -1
	}

	tree = make([]TreeNode, 4*M)
	pqs = make([]PQ, M)
	build(1, 0, M-1)

	parent = make([]int, n+1)
	for i := 1; i <= n; i++ {
		parent[i] = i
	}
	L_scc := make([]int, n+1)
	R_scc := make([]int, n+1)
	x_orig := make([]int, n+1)
	y_orig := make([]int, n+1)

	add_count := 0

	for _, q := range queries {
		if q.t == 1 {
			add_count++
			x := q.a
			y := q.b
			cur_id := add_count
			cur_L := x
			cur_R := y

			for _, X := range []int{x, y} {
				idx := get_comp(X)
				for {
					if idx == 0 {
						break
					}
					res := query(1, 0, M-1, 0, idx-1)
					if res.max_R > X {
						item := heap.Pop(&pqs[res.leaf]).(Item)
						update(1, 0, M-1, res.leaf, pqs[res.leaf].Top().R)

						root_id := find(item.id)
						parent[root_id] = cur_id
						if L_scc[root_id] < cur_L {
							cur_L = L_scc[root_id]
						}
						if R_scc[root_id] > cur_R {
							cur_R = R_scc[root_id]
						}
					} else {
						break
					}
				}
			}

			L_scc[cur_id] = cur_L
			R_scc[cur_id] = cur_R
			x_orig[cur_id] = x
			y_orig[cur_id] = y

			cur_L_idx := get_comp(cur_L)
			heap.Push(&pqs[cur_L_idx], Item{cur_R, cur_id})
			update(1, 0, M-1, cur_L_idx, pqs[cur_L_idx].Top().R)

		} else {
			A := q.a
			B := q.b
			root_B := find(B)
			if x_orig[A] >= L_scc[root_B] && y_orig[A] <= R_scc[root_B] {
				fmt.Fprintln(out, "YES")
			} else {
				fmt.Fprintln(out, "NO")
			}
		}
	}
}