← Home
For problem statement at 0-999/500-599/520-529/524/problemE.txt this is a correct solution, but verifier at 0-999/500-599/520-529/524/verifierE.go ends with build ref failed: exit status 1
# command-line-arguments
./524E.go:51:28: invalid operation: st.tree[l] < res (mismatched types int and float64)
./524E.go:52:22: cannot use st.tree[l] (variable of type int) as float64 value in assignment
./524E.go:57:28: invalid operation: st.tree[r] < res (mismatched types int and float64)
./524E.go:58:22: cannot use st.tree[r] (variable of type int) as float64 value in assignment
./524E.go:65:11: cannot use res (variable of type float64) as int value in return statement can you fix the verifier? package main

import (
	"bufio"
	"io"
	"os"
	"sort"
)

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	b, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: b, n: len(b)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n && (fs.data[fs.idx] < '0' || fs.data[fs.idx] > '9') && fs.data[fs.idx] != '-' {
		fs.idx++
	}
	sign := 1
	if fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n && fs.data[fs.idx] >= '0' && fs.data[fs.idx] <= '9' {
		val = val*10 + int(fs.data[fs.idx]-'0')
		fs.idx++
	}
	return val * sign
}

type Rook struct {
	x int
	y int
}

type Query struct {
	x1  int
	y1  int
	x2  int
	y2  int
	idx int
}

type SegTree struct {
	size int
	tree []int
}

func NewSegTree(n int) *SegTree {
	size := 1
	for size < n {
		size <<= 1
	}
	return &SegTree{
		size: size,
		tree: make([]int, size<<1),
	}
}

func (st *SegTree) Update(pos, val int) {
	i := pos - 1 + st.size
	st.tree[i] = val
	for i >>= 1; i > 0; i >>= 1 {
		if st.tree[i<<1] < st.tree[i<<1|1] {
			st.tree[i] = st.tree[i<<1]
		} else {
			st.tree[i] = st.tree[i<<1|1]
		}
	}
}

func (st *SegTree) Query(l, r int) int {
	const INF int = int(^uint(0) >> 1)
	res := INF
	l = l - 1 + st.size
	r = r - 1 + st.size
	for l <= r {
		if l&1 == 1 {
			if st.tree[l] < res {
				res = st.tree[l]
			}
			l++
		}
		if r&1 == 0 {
			if st.tree[r] < res {
				res = st.tree[r]
			}
			r--
		}
		l >>= 1
		r >>= 1
	}
	return res
}

func main() {
	fs := NewFastScanner()

	n := fs.NextInt()
	m := fs.NextInt()
	k := fs.NextInt()
	q := fs.NextInt()

	rooks := make([]Rook, k)
	for i := 0; i < k; i++ {
		rooks[i] = Rook{fs.NextInt(), fs.NextInt()}
	}

	queries := make([]Query, q)
	for i := 0; i < q; i++ {
		queries[i] = Query{fs.NextInt(), fs.NextInt(), fs.NextInt(), fs.NextInt(), i}
	}

	rowOK := make([]bool, q)
	colOK := make([]bool, q)

	rooksByY := make([]Rook, k)
	copy(rooksByY, rooks)
	sort.Slice(rooksByY, func(i, j int) bool {
		if rooksByY[i].y == rooksByY[j].y {
			return rooksByY[i].x < rooksByY[j].x
		}
		return rooksByY[i].y < rooksByY[j].y
	})

	queriesByY2 := make([]Query, q)
	copy(queriesByY2, queries)
	sort.Slice(queriesByY2, func(i, j int) bool {
		if queriesByY2[i].y2 == queriesByY2[j].y2 {
			return queriesByY2[i].idx < queriesByY2[j].idx
		}
		return queriesByY2[i].y2 < queriesByY2[j].y2
	})

	stRows := NewSegTree(n)
	p := 0
	for _, qu := range queriesByY2 {
		for p < k && rooksByY[p].y <= qu.y2 {
			stRows.Update(rooksByY[p].x, rooksByY[p].y)
			p++
		}
		if stRows.Query(qu.x1, qu.x2) >= qu.y1 {
			rowOK[qu.idx] = true
		}
	}

	rooksByX := make([]Rook, k)
	copy(rooksByX, rooks)
	sort.Slice(rooksByX, func(i, j int) bool {
		if rooksByX[i].x == rooksByX[j].x {
			return rooksByX[i].y < rooksByX[j].y
		}
		return rooksByX[i].x < rooksByX[j].x
	})

	queriesByX2 := make([]Query, q)
	copy(queriesByX2, queries)
	sort.Slice(queriesByX2, func(i, j int) bool {
		if queriesByX2[i].x2 == queriesByX2[j].x2 {
			return queriesByX2[i].idx < queriesByX2[j].idx
		}
		return queriesByX2[i].x2 < queriesByX2[j].x2
	})

	stCols := NewSegTree(m)
	p = 0
	for _, qu := range queriesByX2 {
		for p < k && rooksByX[p].x <= qu.x2 {
			stCols.Update(rooksByX[p].y, rooksByX[p].x)
			p++
		}
		if stCols.Query(qu.y1, qu.y2) >= qu.x1 {
			colOK[qu.idx] = true
		}
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	for i := 0; i < q; i++ {
		if rowOK[i] || colOK[i] {
			out.WriteString("YES\n")
		} else {
			out.WriteString("NO\n")
		}
	}
	out.Flush()
}