[BOJ]8983号:ハンター(Go,Golang)

質問リンク:白駿8983号です。
[質問へのアクセス]
完全にナビゲートすると、O(NM)タイムアウトが発生します.
射程の大きさが1~10万というのを見て、たぶんこの試みで解決できるかと思ったのですが、どうすればいいのか見つからず、他人の問題をリファレンスで解決しました.
動物の大きさを決定し,4世代の数をO(Nlogm)に変えた.

師団の位置を昇順に示すスライスarr.

動物の位置(x,y)が得られ、arr配列を二分探索した.

min = x - (l - y)max = x + (l - y)

動物を捕まえる4大候補はmin~maxである.

そのため、低候補間に死隊が存在すればans++後突破を行う.

師範大学がminより小さい場合は、より大きな師範大学を選択する必要があります.したがってstart=mid+1です.

師団がmaxより大きい場合は、より小さい師団を選択する必要がありますので、end=mid-1です.

最終出力ansでよい.

[ソースコード]

package main

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

var (
	r             = bufio.NewReader(os.Stdin)
	w             = bufio.NewWriter(os.Stdout)
	m, n, l, x, y int
)

func main() {
	defer w.Flush()
	fmt.Fscan(r, &m, &n, &l)
	arr := make([]int, m)
	for i := 0; i < m; i++ {
		fmt.Fscan(r, &arr[i])
	}
	sort.Sort(sort.IntSlice(arr))
	ans := 0
	for i := 0; i < n; i++ {
		fmt.Fscan(r, &x, &y)
		min := x - (l - y)
		max := x + (l - y)
		start := 0
		end := len(arr) - 1
		for start <= end {
			mid := (start + end) / 2
			target := arr[mid]
			if min <= target && max >= target {
				ans++
				break
			} else if target < min {
				start = mid + 1
			} else {
				end = mid - 1
			}
		}
	}
	fmt.Fprintln(w, ans)
}