E - Summer Vacation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 3 点

問題文

あなたは今日から夏休みです。夏休みは N 日間からなります。
M 個のイベントがあります。i 個目のイベントは A_i 日目の朝にはじまって B_i 日目の夜に終わります。
Q 個のクエリに答えてください。クエリでは L, R が与えられるので、次の問いに答えてください。

あなたは L 日目から R 日目の間にできるだけたくさんのイベントに参加することにしました。
ただし、イベントは途中参加や途中抜けが出来ません。よって期間が被っている複数のイベントに参加したり、L 日目より前や R 日目より後を期間に含むイベントに参加することはできません。
参加するイベントを上手く選んだ時、最大で何個のイベントに参加できますか？

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq B_i \leq N
  • 1 \leq L \leq R \leq N
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M Q
A_1 B_1
A_2 B_2
\vdots
A_M B_M
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下の形式で与えられる。

L R

出力

Q 行出力せよ。i 行目には i 番目のクエリへの答えを出力せよ。

入力例 1

5 3 3
1 3
4 5
2 2
1 5
1 1
3 5

出力例 1

2
0
1

例えば 1 番目のクエリでは、1 番目のイベントと 2 番目のイベントに参加することが出来てこれが最大です。

入力例 2

9 13 8
4 6
1 5
8 9
5 6
1 7
4 9
4 6
2 8
5 6
5 8
2 6
3 7
1 3
5 7
5 7
5 7
3 4
1 8
2 6
6 8
8 9

出力例 2

1
1
1
0
2
1
0
1

Score : 3 points

Problem Statement

Your summer vacation starts today and lasts for N days.
There are M events. The i-th event starts on the morning of day A_i and ends on the evening of day B_i.

You are given Q queries. In each query, you are given two integers L and R, and you need to answer the following:

You decide to attend as many events as possible during the period from day L to day R.
However, you cannot join or leave an event in the middle. Therefore, you cannot attend multiple events whose time periods overlap, and you also cannot attend any event that starts before day L or ends after day R.
If you choose the events optimally, what is the maximum number of events you can attend?

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq B_i \leq N
  • 1 \leq L \leq R \leq N
  • All input values are integers

Input

The input is given from standard input in the following format:

N M Q
A_1 B_1
A_2 B_2
\vdots
A_M B_M
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

L R

Output

Print Q lines. For the i-th line, output the answer to the i-th query.

Sample Input 1

5 3 3
1 3
4 5
2 2
1 5
1 1
3 5

Sample Output 1

2
0
1

For example, in the first query, you can attend the 1st and 2nd events, and this is the maximum.

Sample Input 2

9 13 8
4 6
1 5
8 9
5 6
1 7
4 9
4 6
2 8
5 6
5 8
2 6
3 7
1 3
5 7
5 7
5 7
3 4
1 8
2 6
6 8
8 9

Sample Output 2

1
1
1
0
2
1
0
1