[Solution] Rain Codeforces Solution | Solution Codeforces

D. Rain

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are the owner of a harvesting field which can be modeled as an infinite line, whose positions are identified by integers.

It will rain for the next 𝑛$n$ days. On the 𝑖$i$-th day, the rain will be centered at position 𝑥𝑖$x_i$ and it will have intensity 𝑝𝑖$p_i$. Due to these rains, some rainfall will accumulate; let 𝑎𝑗$a_j$ be the amount of rainfall accumulated at integer position 𝑗$j$. Initially 𝑎𝑗$a_j$ is 0$0$, and it will increase by max(0,𝑝𝑖−|𝑥𝑖−𝑗|)$max(0,p_i-|x_i-j|)$ after the 𝑖$i$-th day's rain.

A flood will hit your field if, at any moment, there is a position 𝑗$j$ with accumulated rainfall 𝑎𝑗>𝑚$a_j>m$.

You can use a magical spell to erase exactly one day's rain, i.e., setting 𝑝𝑖=0$p_i=0$. For each 𝑖$i$ from 1$1$ to 𝑛$n$, check whether in case of erasing the 𝑖$i$-th day's rain there is no flood.

Input

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Each test contains multiple test cases. The first line contains the number of test cases 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$). The description of the test cases follows.

The first line of each test case contains two integers 𝑛$n$ and 𝑚$m$ (1≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$, 1≤𝑚≤109$1\le m\le {10}^9$) — the number of rainy days and the maximal accumulated rainfall with no flood occurring.

Perfect Permutation Codeforces Solution

Party Codeforces Solution

Color the Picture Codeforces Solution

Rain Codeforces Solution

XOR Triangle Codeforces Solution

Then 𝑛$n$ lines follow. The 𝑖$i$-th of these lines contains two integers 𝑥𝑖$x_i$ and 𝑝𝑖$p_i$ (1≤𝑥𝑖,𝑝𝑖≤109$1\le x_i,p_i\le {10}^9$) — the position and intensity of the 𝑖$i$-th day's rain.

The sum of 𝑛$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, output a binary string 𝑠$s$ length of 𝑛$n$. The 𝑖$i$-th character of 𝑠$s$ is 1 if after erasing the 𝑖$i$-th day's rain there is no flood, while it is 0, if after erasing the 𝑖$i$-th day's rain the flood still happens.