Rain (Codeforces 1710B)
Tags: Greedy, geometry

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$$$, and it will increase by $$$\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 $$$p_i=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: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq m \leq 10^9$$$) — 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 $$$x_i$$$ and $$$p_i$$$ ($$$1 \leq x_i,p_i \leq 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 \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.

Note: 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.

Sample Inputs:
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

Sample Outputs:
001
11
00
100110

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]

def solve():
    (n, m) = map(int, input().split())
    task = []
    xp = []
    for i in range(n):
        (x, p) = map(int, input().split())
        task.append((x - p, 1))
        task.append((x, -2))
        task.append((x + p, 1))
        xp.append((x, p))
    inf = 10 ** 12
    task.sort(key=lambda x: x[0])
    mxL = -inf
    mxR = -inf
    now = 0
    dx = 0
    last = -inf
    for (x, y) in task:
        now = now + dx * (x - last)
        dx += y
        last = x
        if now > m:
            mxL = max(mxL, now - m - x)
            mxR = max(mxR, now - m + x)
    ans = []
    for (x, p) in xp:
        if p - x >= mxL and p + x >= mxR:
            ans.append('1')
        else:
            ans.append('0')
    print(''.join(ans))
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
m9 = 10 ** 9 + 7
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
e18 = 10 ** 18 + 10
CHECK_OFFLINE_TEST = True
if CHECK_OFFLINE_TEST:
    import getpass
    OFFLINE_TEST = getpass.getuser() == 'htong'

def log(*args):
    if CHECK_OFFLINE_TEST and OFFLINE_TEST:
        print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
    if OFFLINE_TEST:
        log('----- solving ------')
        log(*args)
        log('----- ------- ------')
    return solve_(*args)

def read_matrix(rows):
    return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
    return [input().strip() for _ in range(rows)]

def minus_one(arr):
    return [x - 1 for x in arr]

def minus_one_matrix(mrr):
    return [[x - 1 for x in row] for row in mrr]

def solve_(n, m, mrr):
    diffs = []
    for (x, p) in mrr:
        diffs.append((x - p, 1))
        diffs.append((x, -2))
        diffs.append((x + p, 1))
    diffs.sort()
    minval = diffs[0][0] - 1
    diffs = [(x - minval, y) for (x, y) in diffs]
    arr = [(0, 0)]
    grad = 0
    for (cur_x, d) in diffs:
        (prev_x, prev_y) = arr[-1]
        dist = cur_x - prev_x
        incr = dist * grad
        cur_y = prev_y + incr
        grad += d
        arr.append((cur_x, cur_y))
    arr = [(x, y - m) for (x, y) in arr if y > m]
    if not arr:
        return '1' * len(mrr)
    prr = [x - y for (x, y) in arr]
    qrr = [x + y for (x, y) in arr]
    minprr = min(prr)
    maxqrr = max(qrr)
    req_height = (maxqrr - minprr) / 2
    req_midpt = (maxqrr + minprr) / 2
    res = ''
    for (x, p) in mrr:
        x -= minval
        if x + p >= maxqrr and x - p <= minprr:
            res += '1'
        else:
            res += '0'
    return res
for case_num in range(int(input())):
    (n, m) = list(map(int, input().split()))
    mrr = read_matrix(n)
    res = solve(n, m, mrr)
    print(res)

Solution (Python):
import math
import collections
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    d = collections.defaultdict(int)
    rains = []
    for _ in range(n):
        (x, p) = map(int, input().split())
        rains.append((x, p))
        d[x - p] += 1
        d[x] -= 2
        d[x + p] += 1
    centres = sorted(d)
    for (x, y) in zip(centres, centres[1:]):
        d[y] += d[x]
    (l, r) = (math.inf, -math.inf)
    p = 0
    for (x, y) in zip(centres, centres[1:]):
        p += d[x] * (y - x)
        if p > m:
            l = min(l, y - (p - m))
            r = max(r, y + (p - m))
    print(*(int(x - p <= l and x + p >= r) for (x, p) in rains), sep='')