链接: https://cses.fi/problemset/task/1664

板块: Range Queries

时限: 1.00 s ｜ 内存: 512 MB

题目描述

在电影节上，将放映 $n$ 部电影。你知道每部电影的开始和结束时间。

你的任务是处理 $q$ 个如下形式的查询：如果你在特定时间到达并离开电影节，你最多能看多少部电影？

如果第一部电影在第二部电影开始之前或正好开始时结束，你就可以连续观看这两部电影。你可以在到达时正好开始看第一部电影，并在最后一部电影结束时正好离开。

输入

第一行输入包含两个整数 $n$ 和 $q$：分别表示电影数量和查询数量。

接下来有 $n$ 行描述电影。每行包含两个整数 $a$ 和 $b$：一部电影的开始和结束时间。

最后有 $q$ 行描述查询。每行包含两个整数 $a$ 和 $b$：你的到达和离开时间。

输出

对每个查询输出能看的最大电影数量。

数据范围

$1 \le n,q \le 2 \cdot 10^5$ $1 \le a < b \le 10^6$

样例输入

4 3
2 5
6 10
4 7
9 10
5 9
2 10
7 10

样例输出

0
2
1