No.2687 Heavy Rain in Places
Problem Statement
There are $N+M$ rain clouds on a one-dimensional number line, numbered $1, 2, ..., N+M$. The first $N$ of them are ordinary rain clouds, and the following $M$ are rare rain clouds.
It is known that at time $0$, the position of the $i$-th rain cloud is represented by the closed interval $[L_{i}, R_{i}]$.
Ordinary rain clouds move at speed $1$ from the negative direction toward the positive direction. That is, at time $t$, the rain cloud occupies the closed interval $[L_{i} + t, R_{i} + t]$.
Rare rain clouds move at speed $1$ from the positive direction toward the negative direction. That is, at time $t$, the rain cloud occupies the closed interval $[L_{i} - t, R_{i} - t]$.
Now, on this one-dimensional number line, there are $K$ houses located at points $P_{1}, P_{2}, ..., P_{K}$ (where $P_{1} < P_{2} < ... < P_{K}$).
You are a member of the Association for Intertropical Convergence zone, and your job is,
for each of these $K$ points, to determine whether there exists a time ( including the case where the time is negative ) at which the point is covered by $2$ or more rain clouds.
Input
$N\ M$
$L_{1}\ R_{1}$
$L_{2}\ R_{2}$
︙
$L_{N}\ R_{N}$
$L_{N+1}\ R_{N+1}$
$L_{N+2}\ R_{N+2}$
︙
$L_{N+M}\ R_{N+M}$
$K$
$P_{1}\ P_{2}\ ...\ P_{K}$
Constraints
- All input values are integers
- $1\leq N \leq 10^5$
- $1\leq M \leq 10^3$
- $-10^9 \leq L_{i} \leq R_{i} \leq 10^9$ $(1\leq i\leq N+M)$
- $1\leq K \leq 10^3$
- $-10^9 \leq P_{i}\leq 10^9$ $(1\leq i\leq K)$
- $P_{i} \lt P_{i+1}$ $(1\leq i\leq K-1)$
Output
For each $i = 1, 2, ..., K$, let $E_{i} = 1$ if there exists a time at which point $P_{i}$ is covered by $2$ rain clouds, and $E_{i} = 0$ otherwise, and output them in the following space-separated format.
$E_{1}\ E_{2}\ ...\ E_{K}$
Print a newline at the end.
Sample
Sample 1
Input
2 1 -7 -4 0 1 3 5 11 -5 -4 -3 -2 -1 0 1 2 3 4 5
Output
0 0 0 1 1 1 0 1 1 0 0
For example, at time $2$, rain cloud $1$ is located at $[-5, -2]$, rain cloud $2$ at $[2, 3]$, and rain cloud $3$ at $[1, 3]$, so $2$ rain clouds overlap at positions $2, 3$.
On the other hand, it can be proved that for position $-5$ and position $1$, there is no time at which $2$ or more rain clouds overlap.
Sample 2
Input
2 1 1 6 3 8 1 2 4 3 14 159 2653
Output
1 1 1 1
Sample 3
Input
1 1 0 1 -1 0 2 0 1
Output
1 0
When the left end of one rain cloud and the right end of another rain cloud touch at exactly one point, that point of contact is also considered to be covered by $2$ rain clouds.
Sample 4
Input
4 2 -10 -9 -24 -22 7 8 -15 -12 -3 2 20 21 10 -16 -8 -4 -2 -1 0 1 2 4 8
Output
0 1 1 1 1 0 0 1 1 0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
kyawa
tute7627
SPD_9X2
だれ
arad