GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Friday 29 July 2022

[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 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 0, and it will increase by max(0,pi|xij|) 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 pi=0. For each i from 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 (1t104). The description of the test cases follows.

The first line of each test case contains two integers n and m (1n21051m109) — 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 (1xi,pi109) — the position and intensity of the i-th day's rain.

The sum of n over all test cases does not exceed 2105.

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.


No comments:

Post a Comment