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")
}
}
}
}