[Solution] Rain solution codeforces – You are the owner of a harvesting field which can be modeled as an infinite line, whose positions are identified by integers.

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

Table of Contents

[Solution] Rain solution codeforces

It will rain for the next 𝑛n days. On the 𝑖i-th day, the rain will be centered at position 𝑥𝑖xi and it will have intensity 𝑝𝑖pi. Due to these rains, some rainfall will accumulate; let 𝑎𝑗aj be the amount of rainfall accumulated at integer position 𝑗j. Initially 𝑎𝑗aj is 00, and it will increase by max(0,𝑝𝑖|𝑥𝑖𝑗|)max(0,pi−|xi−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 𝑎𝑗>𝑚aj>m.

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

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡1041≤t≤104). The description of the test cases follows.

The first line of each test case contains two integers 𝑛n and 𝑚m (1𝑛21051≤n≤2⋅1051𝑚1091≤m≤109) — the number of rainy days and the maximal accumulated rainfall with no flood occurring.

Then 𝑛n lines follow. The 𝑖i-th of these lines contains two integers 𝑥𝑖xi and 𝑝𝑖pi (1𝑥𝑖,𝑝𝑖1091≤xi,pi≤109) — the position and intensity of the 𝑖i-th day’s rain.

The sum of 𝑛n over all test cases does not exceed 21052⋅105.

[Solution] Rain solution codeforces

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.

Example
input

Copy
4
3 6
1 5
5 5
3 4
2 3
1 3
5 2
2 5
1 6
10 6
6 12
4 5
1 6
12 5
5 5
9 7
8 3
output

Copy
001
11
00
100110

[Solution] Rain solution codeforces

In the first test case, if we do not use the spell, the accumulated rainfall distribution will be like this:

If we erase the third day’s rain, the flood is avoided and the accumulated rainfall distribution looks like this:

In the second test case, since initially the flood will not happen, we can erase any day’s rain.

In the third test case, there is no way to avoid the flood.

For Solution

Click Here

Leave a Comment