Domino Principle (Codeforces 56E)
Tags: Others, binary search

Vasya is interested in arranging dominoes. He is fed up with common dominoes and he uses the dominoes of different heights. He put n dominoes on the table along one axis, going from left to right. Every domino stands perpendicular to that axis so that the axis passes through the center of its base. The i-th domino has the coordinate xi and the height hi. Now Vasya wants to learn for every domino, how many dominoes will fall if he pushes it to the right. Help him do that. Consider that a domino falls if it is touched strictly above the base. In other words, the fall of the domino with the initial coordinate x and height h leads to the fall of all dominoes on the segment [x + 1, x + h - 1].

Input: The first line contains integer n (1 ≤ n ≤ 105) which is the number of dominoes. Then follow n lines containing two integers xi and hi ( - 108 ≤ xi ≤ 108, 2 ≤ hi ≤ 108) each, which are the coordinate and height of every domino. No two dominoes stand on one point.

Output: Print n space-separated numbers zi — the number of dominoes that will fall if Vasya pushes the i-th domino to the right (including the domino itself).


Sample Inputs:
4
16 5
20 5
10 10
18 2

4
0 10
1 5
9 10
15 10

Sample Outputs:
3 1 4 1

4 1 2 1

Solution (Python):
n = int(input())
dominoes = []
for i in range(n):
    (x, h) = [int(x) for x in input().split()]
    dominoes.append((x, h, i))
dominoes.sort(key=lambda x: x[0])
fall_count = [1 for _ in range(n)]
indexed_fall_count = [1 for _ in range(n)]
for i in range(n - 2, -1, -1):
    current_domino_fall_count = 1
    j = i + 1
    while j < n and dominoes[i][0] + dominoes[i][1] > dominoes[j][0] + dominoes[j][1]:
        current_domino_fall_count += 1
        j += 1
    if j < n:
        if dominoes[i][0] + dominoes[i][1] > dominoes[j][0]:
            current_domino_fall_count += fall_count[j]
    fall_count[i] = current_domino_fall_count
    indexed_fall_count[dominoes[i][2]] = current_domino_fall_count
print(' '.join(map(str, indexed_fall_count)))

Solution (Python):
import bisect
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def update(i, x, tree):
    i += l1
    tree[i] = x
    i //= 2
    while i:
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
        i //= 2
    return

def get_max(s, t, tree):
    s += l1
    t += l1
    ans = -inf
    while s <= t:
        if s % 2 == 0:
            s //= 2
        else:
            ans = max(ans, tree[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = max(ans, tree[t])
            t = (t - 1) // 2
    return ans
n = int(input())
d = dict()
for i in range(n):
    (x, h) = map(int, input().split())
    d[x] = (i, h)
u = list(d.keys())
u.sort()
inf = pow(10, 9) + 1
l1 = pow(2, n.bit_length())
l2 = 2 * l1
ma = [-inf] * l2
for i in range(n):
    ma[i + l1] = i + 1
for i in range(l1 - 1, 0, -1):
    ma[i] = max(ma[2 * i], ma[2 * i + 1])
ans = [0] * n
for i in range(n - 1, -1, -1):
    x = u[i]
    (j, h) = d[x]
    r = bisect.bisect_left(u, x + h) - 1
    l = i
    m = get_max(l, r, ma)
    ans[j] = m - i
    update(i, m, ma)
sys.stdout.write(' '.join(map(str, ans)))

Solution (Python):
from bisect import bisect_left
import sys
readline = sys.stdin.readline

class Segment_Tree:

    def __init__(self, N, f, e, lst=None):
        self.f = f
        self.e = e
        self.N = N
        if lst == None:
            self.segment_tree = [self.e] * 2 * self.N
        else:
            assert len(lst) <= self.N
            self.segment_tree = [self.e] * self.N + [x for x in lst] + [self.e] * (N - len(lst))
            for i in range(self.N - 1, 0, -1):
                self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def __getitem__(self, i):
        if type(i) == int:
            if -self.N <= i < 0:
                return self.segment_tree[i + self.N * 2]
            elif 0 <= i < self.N:
                return self.segment_tree[i + self.N]
            else:
                raise IndexError('list index out of range')
        else:
            (a, b, c) = (i.start, i.stop, i.step)
            if a == None:
                a = self.N
            else:
                a += self.N
            if b == None:
                b = self.N * 2
            else:
                b += self.N
            return self.segment_tree[slice(a, b, c)]

    def __setitem__(self, i, x):
        if -self.N <= i < 0:
            i += self.N * 2
        elif 0 <= i < self.N:
            i += self.N
        else:
            raise IndexError('list index out of range')
        self.segment_tree[i] = x
        while i > 1:
            i >>= 1
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Build(self, lst):
        for (i, x) in enumerate(lst, self.N):
            self.segment_tree[i] = x
        for i in range(self.N - 1, 0, -1):
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Fold(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        vL = self.e
        vR = self.e
        while L < R:
            if L & 1:
                vL = self.f(vL, self.segment_tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.segment_tree[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def Fold_Index(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        if L == R:
            return None
        x = self.Fold(L - self.N, R - self.N)
        while L < R:
            if L & 1:
                if self.segment_tree[L] == x:
                    i = L
                    break
                L += 1
            if R & 1:
                R -= 1
                if self.segment_tree[R] == x:
                    i = R
                    break
            L >>= 1
            R >>= 1
        while i < self.N:
            if self.segment_tree[i] == self.segment_tree[i << 1]:
                i <<= 1
            else:
                i <<= 1
                i |= 1
        i -= self.N
        return i

    def Bisect_Right(self, l=None, f=None):
        if l == self.N:
            return self.N
        if l == None:
            l = 0
        if f(self.Fold(l, self.N)):
            return self.N
        l += self.N
        v = self.e
        while True:
            while l % 2 == 0:
                l >>= 1
            vv = self.f(v, self.segment_tree[l])
            if f(vv):
                v = vv
                l += 1
                if 2 * self.N == l << self.N.bit_length() - l.bit_length() + 1:
                    return self.N
            else:
                while l < self.N:
                    l <<= 1
                    vv = self.f(v, self.segment_tree[l])
                    if f(vv):
                        v = vv
                        l += 1
                return l - self.N

    def Bisect_Left(self, r=None, f=None):
        if r == 0:
            return 0
        if r == None:
            r = self.N
        if f(self.Fold(0, r)):
            return 0
        r += self.N
        v = self.e
        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            vv = self.f(self.segment_tree[r], v)
            if f(vv):
                v = vv
                if 2 * self.N == r << self.N.bit_length() - r.bit_length() + 1:
                    return 0
            else:
                while r < self.N:
                    r = 2 * r + 1
                    vv = self.f(self.segment_tree[r], v)
                    if f(vv):
                        v = vv
                        r -= 1
                return r + 1 - self.N

    def __str__(self):
        return '[' + ', '.join(map(str, self.segment_tree[self.N:])) + ']'

def Compress(lst):
    decomp = sorted(list(set(lst)))
    comp = {x: i for (i, x) in enumerate(decomp)}
    return (comp, decomp)
N = int(readline())
XH = []
X = []
for i in range(N):
    (x, h) = map(int, readline().split())
    XH.append((x, h, i))
    X.append(x)
XH.sort()
(comp, decomp) = Compress(X)
inf = 1 << 30
dp = Segment_Tree(N, max, -inf, [i + 1 for i in range(N)])
for i in range(N - 1, -1, -1):
    (x, h, _) = XH[i]
    dp[i] = dp.Fold(i, bisect_left(decomp, x + h))
ans_lst = [None] * N
for i in range(N):
    (_, _, j) = XH[i]
    ans_lst[j] = dp[i] - i
print(*ans_lst)