← Home
For problem statement at 0-999/100-199/170-179/173/problemE.txt this is a correct solution, but verifier at 0-999/100-199/170-179/173/verifierE.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

type Member struct {
	id int
	r  int
	a  int
	c  int
}

type Query struct {
	id   int
	x    int
	y    int
	Amin int
	Amax int
	Rmin int
	ans  int
}

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
}

func getLeftIdx(u []int, val int) int {
	l, r := 0, len(u)-1
	ans := len(u)
	for l <= r {
		mid := (l + r) / 2
		if u[mid] >= val {
			ans = mid
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	return ans + 1
}

func getRightIdx(u []int, val int) int {
	l, r := 0, len(u)-1
	ans := -1
	for l <= r {
		mid := (l + r) / 2
		if u[mid] <= val {
			ans = mid
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	return ans + 1
}

func add(fw []int, idx int, val int) {
	for i := idx; i < len(fw); i += i & -i {
		fw[i] += val
	}
}

func queryFW(fw []int, idx int) int {
	sum := 0
	for i := idx; i > 0; i -= i & -i {
		sum += fw[i]
	}
	return sum
}

func updateST(st []int, node, l, r, idx, val int) {
	if l == r {
		if val > st[node] {
			st[node] = val
		}
		return
	}
	mid := (l + r) / 2
	if idx <= mid {
		updateST(st, 2*node, l, mid, idx, val)
	} else {
		updateST(st, 2*node+1, mid+1, r, idx, val)
	}
	st[node] = max(st[2*node], st[2*node+1])
}

func queryST(st []int, node, l, r, ql, qr int) int {
	if ql > r || qr < l {
		return -1
	}
	if ql <= l && r <= qr {
		return st[node]
	}
	mid := (l + r) / 2
	res1 := queryST(st, 2*node, l, mid, ql, qr)
	res2 := queryST(st, 2*node+1, mid+1, r, ql, qr)
	return max(res1, res2)
}

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

	nextInt := func() int {
		scanner.Scan()
		res, _ := strconv.Atoi(scanner.Text())
		return res
	}

	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())
	k := nextInt()

	origR := make([]int, n)
	for i := 0; i < n; i++ {
		origR[i] = nextInt()
	}

	origA := make([]int, n)
	for i := 0; i < n; i++ {
		origA[i] = nextInt()
	}

	members := make([]Member, n)
	u := make([]int, n)
	for i := 0; i < n; i++ {
		members[i] = Member{id: i, r: origR[i], a: origA[i]}
		u[i] = origA[i]
	}

	sort.Ints(u)
	m := 0
	for i := 0; i < n; i++ {
		if i == 0 || u[i] != u[i-1] {
			u[m] = u[i]
			m++
		}
	}
	u = u[:m]

	sort.Slice(members, func(i, j int) bool {
		return members[i].r < members[j].r
	})

	fw := make([]int, m+1)
	for i := 0; i < n; {
		j := i
		for j < n && members[j].r == members[i].r {
			idx := getLeftIdx(u, members[j].a)
			add(fw, idx, 1)
			j++
		}
		for v := i; v < j; v++ {
			lIdx := getLeftIdx(u, members[v].a-k)
			rIdx := getRightIdx(u, members[v].a+k)
			members[v].c = queryFW(fw, rIdx) - queryFW(fw, lIdx-1)
		}
		i = j
	}

	q := nextInt()
	queries := make([]Query, q)
	for i := 0; i < q; i++ {
		x := nextInt() - 1
		y := nextInt() - 1

		ax := origA[x]
		ay := origA[y]
		rx := origR[x]
		ry := origR[y]

		Amin := max(ax, ay) - k
		Amax := min(ax, ay) + k
		Rmin := max(rx, ry)

		queries[i] = Query{id: i, x: x, y: y, Amin: Amin, Amax: Amax, Rmin: Rmin}
	}

	sort.Slice(members, func(i, j int) bool {
		return members[i].r > members[j].r
	})

	sort.Slice(queries, func(i, j int) bool {
		return queries[i].Rmin > queries[j].Rmin
	})

	st := make([]int, 4*(m+1))
	for i := range st {
		st[i] = -1
	}

	ptr := 0
	for i := range queries {
		if queries[i].Amin > queries[i].Amax {
			queries[i].ans = -1
			continue
		}
		for ptr < n && members[ptr].r >= queries[i].Rmin {
			idx := getLeftIdx(u, members[ptr].a)
			updateST(st, 1, 1, m, idx, members[ptr].c)
			ptr++
		}
		lIdx := getLeftIdx(u, queries[i].Amin)
		rIdx := getRightIdx(u, queries[i].Amax)
		if lIdx > rIdx {
			queries[i].ans = -1
		} else {
			queries[i].ans = queryST(st, 1, 1, m, lIdx, rIdx)
		}
	}

	sort.Slice(queries, func(i, j int) bool {
		return queries[i].id < queries[j].id
	})

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	for i := range queries {
		fmt.Fprintln(out, queries[i].ans)
	}
}