[Solution] GBus count Kick Start Session Solution - Kick Start 2022

There exist some cities that are built along a straight road. The cities are numbered 1,2,3,…$1,2,3,\dots$ from left to right.

There are N$N$ GBuses that operate along this road. For each GBus, the range of cities that it serves is provided: the i$i$-th gBus serves the cities with numbers between Ai${\mathbf{A}}_{\mathbf{i}}$ and Bi${\mathbf{B}}_{\mathbf{i}}$, inclusive.

We are interested in a particular subset of P$P$ cities. For each of those cities, we need to find out how many GBuses serve that particular city.

Input

The first line of the input gives the number of test cases, T$T$. Then, T$T$ test cases follow; each case is separated from the next by one blank line. (Notice that this is unusual for Kickstart data sets.)

In each test case:

• The first line contains one integer N$N$: the number of GBuses.
• The second line contains 2N$N$ integers representing the ranges of cities that the buses serve, in the form A1${\mathbf{A}}_{\mathbf{1}}$ B1${\mathbf{B}}_{\mathbf{1}}$ A2${\mathbf{A}}_{\mathbf{2}}$ B2${\mathbf{B}}_{\mathbf{2}}$ A3${\mathbf{A}}_{\mathbf{3}}$ B3${\mathbf{B}}_{\mathbf{3}}$ ... AN${\mathbf{A}}_{\mathbf{N}}$ BN${\mathbf{B}}_{\mathbf{N}}$. That is, the first GBus serves the cities numbered from A1${\mathbf{A}}_{\mathbf{1}}$ to B1${\mathbf{B}}_{\mathbf{1}}$ (inclusive), the second GBus serves the cities numbered from A2${\mathbf{A}}_{\mathbf{2}}$ to B2${\mathbf{B}}_{\mathbf{2}}$ (inclusive), and so on.
• The third line contains one integer P$P$: the number of cities we are interested in, as described above. (Note that this is not necessarily the same as the total number of cities in the problem, which is not given.)

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

• Finally, there are P$P$ more lines; the i$i$-th of these contains the number Ci${\mathbf{C}}_{\mathbf{i}}$ of a city we are interested in.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the number of the test case (starting from 1), and y$y$ is a list of P$P$ integers, in which the i$i$-th integer is the number of GBuses that serve city Ci${\mathbf{C}}_{\mathbf{i}}$.

Limits

Memory limit: 1 GB.
1≤T≤10$1\le \mathbf{T}\le 10$.

Test Set 1

Time limit: 60 seconds.
1≤N≤50$1\le \mathbf{N}\le 50$.
1≤Ai≤500$1\le {\mathbf{A}}_{\mathbf{i}}\le 500$, for all i$i$.
1≤Bi≤500$1\le {\mathbf{B}}_{\mathbf{i}}\le 500$, for all i$i$.
1≤Ci≤500$1\le {\mathbf{C}}_{\mathbf{i}}\le 500$, for all i$i$.
1≤P≤50$1\le \mathbf{P}\le 50$.

Test Set 2

Time limit: 120 seconds.
1≤N≤500$1\le \mathbf{N}\le 500$.
1≤Ai≤5000$1\le {\mathbf{A}}_{\mathbf{i}}\le 5000$, for all i$i$.
1≤Bi≤5000$1\le {\mathbf{B}}_{\mathbf{i}}\le 5000$, for all i$i$.
1≤Ci≤5000$1\le {\mathbf{C}}_{\mathbf{i}}\le 5000$, for all i$i$.
1≤P≤500$1\le \mathbf{P}\le 500$.