← 返回题目列表

AtCoder · past17_j

J. 咖啡馆

中文机器翻译题面 查看原题

问题陈述

N 顾客参观了一家咖啡馆:顾客 1,客户 2, \ldots和客户 N.
对于 i = 1, 2, \ldots, N,客户 i 在咖啡馆呆了好久 A_i 到时间 B_i (包括时间 A_i 和时间 B_i).
除这些客户外没有其他客户 N 参观了咖啡馆。

对于每个 Q 次 t_1, t_2, \ldots, t_Q, 找出当时留在咖啡馆的顾客数量。

约束

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 \leq A_i \lt B_i \leq 10^9
  • 1 \leq t_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N
Q
t_1
t_2
\vdots
t_Q

输出

打印 Q 行。 对于 i = 1, 2, \ldots, Q, i- 第行应包含当时留在咖啡馆的顾客数量 t_i.


示例输入 1

4
2 4
4 5
3 6
4 5
7
1
2
3
4
5
6
7

示例输出 1

0
1
2
4
3
1
0
  • 时间 1,咖啡馆里没有人。
  • 时间 2,咖啡馆里有一位顾客:顾客 1.
  • 时间 3,咖啡馆里有两个顾客:顾客 1 和 3.
  • 时间 4,咖啡馆里有四位顾客:顾客 1, 2, 3,和 4.
  • 时间 5,咖啡馆里有三名顾客:顾客 2, 3,和 4.
  • 时间 6,咖啡馆里有一位顾客:顾客 3.
  • 时间 7,咖啡馆里没有人。

示例输入 2

1
1 1000000000
2
1000000000
1

示例输出 2

1
1