Submission #62280999

---

Source Code Expand

package main

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

func main() {
	solve(os.Stdin, os.Stdout)
}

func solve(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()

	type pair struct{ x, y int }
	n, w := readTwoNums(in)
	pos := make([]pair, n)
	nums := make([][]int, w+1)
	for i := range pos {
		pos[i].x, pos[i].y = readTwoNums(in)
		nums[pos[i].x] = append(nums[pos[i].x], pos[i].y)
	}

	mxcnt := n
	for i := 1; i <= w; i++ {
		sort.Ints(nums[i])
		mxcnt = min(mxcnt, len(nums[i]))
	}
	times := make([]int, mxcnt)
	for j := 1; j <= w; j++ {
		for i := range times {
			times[i] = max(times[i], nums[j][i])
		}
	}

	t := make([]int, n)
	for i := range pos {
		idx := sort.SearchInts(nums[pos[i].x], pos[i].y)
		if idx < mxcnt {
			t[i] = times[idx]
		} else {
			t[i] = -1
		}
	}

	for q := readNum(in); q > 0; q-- {
		v, a := readTwoNums(in)
		if t[a-1] == -1 || v < t[a-1] {
			fmt.Fprintln(out, "Yes")
		} else {
			fmt.Fprintln(out, "No")
		}
	}
}

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 readString(reader *bufio.Reader) string {
	s, _ := reader.ReadString('\n')
	for i := 0; i < len(s); i++ {
		if s[i] == '\n' || s[i] == '\r' {
			return s[:i]
		}
	}
	return s
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

Submission Info

Judge Result