問題一覧 > 通常問題

No.2687 Heavy Rain in Places

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 39
作問者 : kyawa / テスター : 👑 tute7627 SPD_9X2 👑 rin204 だれ arad
お気に入りにしたユーザー ProblemId : 10428 / 自分の提出
問題文最終更新日: 2024-03-20 18:28:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 422 (第1回 競技プログラミング講習会作問企画コンテスト) (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。