Problem:
 Score : 600 points    Problem Statement There are N robots numbered 1 to N placed on a number line. Robot i is placed at coordinate X_i . When activated, it will travel the distance of D_i in the positive direction, and then it will be removed from the number line. All the robots move at the same speed, and their sizes are ignorable.  Takahashi, who is a mischievous boy, can do the following operation any number of times (possibly zero) as long as there is a robot remaining on the number line.   Choose a robot and activate it. This operation cannot be done when there is a robot moving.   While Robot i is moving, if it touches another robot j that is remaining in the range [X_i, X_i + D_i) on the number line, Robot j also gets activated and starts moving. This process is repeated recursively.  How many possible sets of robots remaining on the number line are there after Takahashi does the operation some number of times? Compute this count modulo 998244353 , since it can be enormous.      Constraints  1 \leq N \leq 2 \times 10^5  -10^9 \leq X_i \leq 10^9  1 \leq D_i \leq 10^9  X_i \neq X_j (i \neq j)  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  X_1  D_1  :  X_N  D_N       Output Print the number of possible sets of robots remaining on the number line, modulo 998244353 .        Sample Input 1 2
1 5
3 3      Sample Output 1 3  There are three possible sets of robots remaining on the number line: \{1, 2\} , \{1\} , and \{\} .  These can be achieved as follows:    If Takahashi activates nothing, the robots \{1, 2\} will remain.    If Takahashi activates Robot 1 , it will activate Robot 2 while moving, after which there will be no robots on the number line. This state can also be reached by activating Robot 2 and then Robot 1 .    If Takahashi activates Robot 2 and finishes doing the operation, the robot \{1\} will remain.         Sample Input 2 3
6 5
-1 10
3 3      Sample Output 2 5  There are five possible sets of robots remaining on the number line: \{1, 2, 3\} , \{1, 2\} , \{2\} , \{2, 3\} , and \{\} .       Sample Input 3 4
7 10
-10 3
4 3
-4 3      Sample Output 3 16  None of the robots influences others.       Sample Input 4 20
-8 1
26 4
0 5
9 1
19 4
22 20
28 27
11 8
-3 20
-25 17
10 4
-18 27
24 28
-11 19
2 27
-2 18
-1 12
-24 29
31 29
29 7      Sample Output 4 110  Remember to print the count modulo 998244353 .

Solution (Python):
from collections import deque


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
MOD = 998244353

info = [(10**10, 10 ** 10)] + sorted(info, reverse=True)
dp = [0] * (n + 1)
dp[0] = 1

q = deque([])
for i in range(n):
    if sum(info[i + 1]) <= info[i][0]:
        
        dp[i + 1] = 2 * dp[i]
        dp[i + 1] %= MOD
        q.append((i, info[i]))
    else:
        
        if sum(info[i + 1]) <= q[-1][1][0]:
            dp[i + 1] = dp[i] + dp[q[-1][0]]
            dp[i + 1] %= MOD
        else:
            while q:
                q.pop()
                if sum(info[i + 1]) <= q[-1][1][0]:
                    dp[i + 1] = dp[i] + dp[q[-1][0]]
                    dp[i + 1] %= MOD
                    break
print(dp[-1] % MOD)

Solution (Python):
import sys
from bisect import bisect_left

MOD = 998244353
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, values, merge_func=min, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        self.merge = merge_func
        while self.size < n:
            self.size *= 2
        
        
        self.tree = [self.default] * self.size * 2
        self.range = [None] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size):
            self.range[self.size + i] = (i, i+1)
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])
            self.range[i] = (self.range[i*2][0], self.range[i*2+1][1])

    def get(self, index):
        return self.tree[self.size + index]

    def update(self, index, value):
        index += self.size
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.merge(
                self.tree[index*2], self.tree[index*2+1])

    
    def query(self, a, b):
        q = [1]
        ret = self.default
        while len(q):
            k = q.pop()
            l, r = self.range[k]
            if r <= a or b <= l:
                continue
            if a <= l and r <= b:
                ret = self.merge(ret, self.tree[k])
            else:
                q.append(k*2)
                q.append(k*2+1)
        return ret


def main():
    N = int(input())
    robo = [None] * N
    for i in range(N):
        robo[i] = tuple(map(int, input().split()))
    robo.sort()
    pos = [x[0] for x in robo]
    dst = [x[0] + x[1] for x in robo]
    rmq = SegmentTree(dst, max, -float("inf"))
    for i in range(N-1)[::-1]:
        dst[i] = rmq.query(i, bisect_left(pos, dst[i]))
        rmq.update(i, dst[i])

    dp = [0] * (N+1)
    dp[0] = 1
    for i in range(N):
        x, d = robo[N-1-i]
        to = N - bisect_left(pos, dst[N-1-i])
        dp[i+1] = (dp[i] + dp[to]) % MOD
    print(dp[N])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from operator import itemgetter
import bisect
def main():
    input = sys.stdin.readline
    N = int(input())
    XD = [tuple(map(int, input().split())) for _ in range(N)]
    MOD = 998244353

    XD.sort(key=itemgetter(0))
    X = [xd[0] for xd in XD]
    segtree = SegmentTree(N+1)
    for i in range(N-1,-1,-1):
        x, d = XD[i]
        j = bisect.bisect_left(X, x+d, i)
        end = max(j-1, segtree.query(i, j))
        segtree.update(i, end)

    dp = [None] * (N+1)
    dp[N] = Mint(1, MOD)
    for i in range(N-1,-1,-1):
        dp[i] = dp[i+1] + dp[segtree.get(i) + 1]
    print(dp[0])

class Mint:
    def __init__(self, value=0, mod=10**9+7):
        self.value = ((value % mod) + mod) % mod
        self.mod = mod

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, self.mod
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        return (u + self.mod) % self.mod

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.val
    def __neg__(self): return Mint(-self.value, self.mod)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % self.mod
        return self
    def __add__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other) + self.mod) % self.mod
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % self.mod
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other, self.mod)
        self *= other.inverse
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj //= self
        return new_obj

class SegmentTree:
    def __init__(self, n=None, f=max, identity_factory=int, initial_values=None):
        assert(n or initial_values)
        size = n if n else len(initial_values)
        d = [identity_factory() for _ in range(2 * size + 1)]
        self.__n, self.__d, self.__f, self.__e = size, d, f, identity_factory
        if initial_values:
            for i, v in enumerate(initial_values): d[size + i] = v
            for i in range(size - 1, 0, -1): d[i] = f(d[i<<1], d[i<<1|1])

    def get(self, index):
        return self.__d[index + self.__n]

    def update(self, index, value):
        i, d, f = index + self.__n, self.__d, self.__f
        if d[i] == value: return
        d[i] = value
        while i:
            i = i >> 1
            d[i] = f(d[i<<1], d[i<<1|1])

    def add(self, index, value):
        self.update(index, self.__f(self.__d[index + self.__n], value))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__e()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__d, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l+1
            if r & 1: ans, r = f(d[r-1], ans), r-1
            l, r = l >> 1, r >> 1
        return ans

    def bisect_left(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        i, n, f, d, v = 1, self.__n, self.__f, self.__d, self.__e()
        while i < n:
            if func(f(v, d[i<<1])): v, i = f(v, d[i<<1]), i<<1|1
            else: i = i<<1
        return i - n

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from operator import itemgetter
import bisect
def main():
    input = sys.stdin.readline
    N = int(input())
    XD = [tuple(map(int, input().split())) for _ in range(N)]
    MOD = 998244353

    XD.sort(key=itemgetter(0))
    X = [xd[0] for xd in XD]
    segtree = SegmentTree(N+1)
    for i in range(N-1,-1,-1):
        x, d = XD[i]
        j = bisect.bisect_left(X, x+d, i)
        end = max(j-1, segtree.query(i, j))
        segtree.update(i, end)

    dp = [Mint(0, MOD) for _ in range(N+1)]
    dp[N] = Mint(1, MOD)
    for i in range(N-1,-1,-1):
        dp[i] += dp[i+1]
        dp[i] += dp[segtree.get(i) + 1]
    print(dp[0])

class Mint:
    def __init__(self, value=0, mod=10**9+7):
        self.value = ((value % mod) + mod) % mod
        self.mod = mod

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, self.mod
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        return (u + self.mod) % self.mod

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.val
    def __neg__(self): return Mint(-self.value, self.mod)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % self.mod
        return self
    def __add__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other) + self.mod) % self.mod
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % self.mod
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other, self.mod)
        self *= other.inverse
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj //= self
        return new_obj

class SegmentTree:
    def __init__(self, n=None, f=max, identity_factory=int, initial_values=None):
        assert(n or initial_values)
        size = n if n else len(initial_values)
        d = [identity_factory() for _ in range(2 * size + 1)]
        self.__n, self.__d, self.__f, self.__e = size, d, f, identity_factory
        if initial_values:
            for i, v in enumerate(initial_values): d[size + i] = v
            for i in range(size - 1, 0, -1): d[i] = f(d[i<<1], d[i<<1|1])

    def get(self, index):
        return self.__d[index + self.__n]

    def update(self, index, value):
        i, d, f = index + self.__n, self.__d, self.__f
        if d[i] == value: return
        d[i] = value
        while i:
            i = i >> 1
            d[i] = f(d[i<<1], d[i<<1|1])

    def add(self, index, value):
        self.update(index, self.__f(self.__d[index + self.__n], value))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__e()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__d, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l+1
            if r & 1: ans, r = f(d[r-1], ans), r-1
            l, r = l >> 1, r >> 1
        return ans

    def bisect_left(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        i, n, f, d, v = 1, self.__n, self.__f, self.__d, self.__e()
        while i < n:
            if func(f(v, d[i<<1])): v, i = f(v, d[i<<1]), i<<1|1
            else: i = i<<1
        return i - n

if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

MOD = 998244353

n = int(input())
robot = []
pos = []

for i in range(n):
    x, d = map(int, input().split())
    robot.append([x, x+d])
    pos.append(x)

robot = sorted(robot, key=lambda y: y[0])
pos = sorted(pos)


def init(init_val):
    for i in range(n):
        MI[i+num-1] = init_val[i]
        MA[i+num-1] = init_val[i]
    for i in range(num-2, -1, -1):
        MI[i] = min(MI[2*i+1], MI[2*i+2])
        MA[i] = max(MA[2*i+1], MA[2*i+2])


def update(k, x):
    k += num-1
    MI[k] = x
    MA[k] = x
    while k+1:
        k = (k-1)//2
        MI[k] = min(MI[k*2+1], MI[k*2+2])
        MA[k] = max(MA[k*2+1], MA[k*2+2])


def rangemax(p, q):
    if q <= p:
        return -1
    p += num-1
    q += num-2
    res = -1
    while q-p > 1:
        if p & 1 == 0:
            res = max(res, MA[p])
        if q & 1 == 1:
            res = max(res, MA[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res, MA[p])
    else:
        res = max(max(res, MA[p]), MA[q])
    return res



num = 2**(n-1).bit_length()
MI = [1 << 100]*2*num
MA = [-1]*2*num

r = []
for x, d in robot:
    r.append(bisect_left(pos, d))

init(r)

s = [0]*n

for x in range(n-1, -1, -1):
    right_max = rangemax(x, r[x])
    s[x] = right_max
    update(x, right_max)

dp = [0]*(n+1)
dp[-1] = 1

for i in range(n-1, -1, -1):
    dp[i] = dp[i+1]+dp[s[i]]
    dp[i] %= MOD

print(dp[0])

Solution (Python):
from bisect import bisect_left
MOD = 998244353

n = int(input())
robot = []
pos = []

for i in range(n):
    x, d = map(int, input().split())
    robot.append([x, x+d])
    pos.append(x)

robot = sorted(robot, key=lambda y: y[0])
pos = sorted(pos)


def init(init_val):
    for i in range(n):
        MI[i+num-1] = init_val[i]
        MA[i+num-1] = init_val[i]
    for i in range(num-2, -1, -1):
        MI[i] = min(MI[2*i+1], MI[2*i+2])
        MA[i] = max(MA[2*i+1], MA[2*i+2])


def update(k, x):
    k += num-1
    MI[k] = x
    MA[k] = x
    while k+1:
        k = (k-1)//2
        MI[k] = min(MI[k*2+1], MI[k*2+2])
        MA[k] = max(MA[k*2+1], MA[k*2+2])


def rangemin(p, q):
    if q <= p:
        return 1 << 100
    p += num-1
    q += num-2
    res = 1 << 100
    while q-p > 1:
        if p & 1 == 0:
            res = min(res, MI[p])
        if q & 1 == 1:
            res = min(res, MI[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res, MI[p])
    else:
        res = min(min(res, MI[p]), MI[q])
    return res


def rangemax(p, q):
    if q <= p:
        return -1
    p += num-1
    q += num-2
    res = -1
    while q-p > 1:
        if p & 1 == 0:
            res = max(res, MA[p])
        if q & 1 == 1:
            res = max(res, MA[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res, MA[p])
    else:
        res = max(max(res, MA[p]), MA[q])
    return res



num = 2**(n-1).bit_length()
MI = [1 << 100]*2*num
MA = [-1]*2*num

r = []
for x, d in robot:
    r.append(bisect_left(pos, d))

init(r)

s = [0]*n

for x in range(n-1, -1, -1):
    right_max = rangemax(x, r[x])
    s[x] = right_max
    update(x, right_max)

dp = [0]*(n+1)
dp[-1] = 1

for i in range(n-1, -1, -1):
    dp[i] = dp[i+1]+dp[s[i]]
    dp[i] %= MOD

print(dp[0])

Solution (Python):
MOD = 998244353
import bisect
import sys
input = sys.stdin.buffer.readline
N = int(input())

XR = []
for i in range(N):
    X,D = map(int,input().split())
    XR.append((X,X+D))

XR.sort()
X, R = map(list,zip(*XR))


inds = [bisect.bisect_left(X,r)-1 for r in R]

l = 2**((N-1).bit_length())
data = [0] * l + inds + [0] * (l-N)
for i in range(l-1,0,-1):
    data[i] = max(data[2*i],data[2*i+1])

def set(i,val):
    i += l
    data[i] = val
    i //= 2
    while i > 0:
        data[i] = max(data[2*i], data[2*i+1])
        i //= 2
def get(i,j):
    i += l
    j += l
    s = data[i]
    while j-i > 0:
        if i & 1:
            s = max(s,data[i])
            i += 1
        if j & 1:
            s = max(s,data[j-1])
            j -= 1
        i//=2
        j//=2
    return s

for i in range(N-1,-1,-1):
    set(i,get(i,inds[i]+1))



dp = [0]*(N+1)
dp[N] = 1
for i in range(N-1,-1,-1):
    dp[i] = (dp[i+1] + dp[data[l+i]+1]) % MOD

print(dp[0])

Solution (Python):
import sys
import bisect
from collections import deque
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N = int(readline())
MOD = 998244353

XD = [[int(x) for x in readline().split()] for _ in range(N)]
XD.sort()


NXT = deque()
E = [[] for _ in range(N)]

for i in range(N - 1, -1, -1):
    x, d = XD[i]

    while NXT:
        j, nx = NXT.pop()

        if nx < x + d:
            E[i].append(j)
        else:
            NXT.append((j, nx))
            break

    NXT.append((i, x))


def dfs(i):
    rtn = 1
    for v in E[i]:
        rtn *= dfs(v)
        rtn %= MOD
    return rtn + 1


ans = 1
for i, x in NXT:
    ans *= dfs(i)
    ans %= MOD

print(ans % MOD)

Solution (Python):

import sys
input = sys.stdin.readline
MOD = 998244353

n = int(input())
xd = []

places = [(10**12, 0)]
for _ in range(n):
    x, d = [int(item) for item in input().split()]
    xd.append((x, d))

xd.sort(reverse=True)
dp = [0] * (n + 1)
dp[0] = 1
for i, (x, d) in enumerate(xd):
    frm = x
    too = x + d 
    too_idx = i
    while too > places[-1][0]:
        _, too_idx = places.pop()
    places.append((frm, too_idx))
    dp[i + 1] = dp[i] + dp[too_idx]
    dp[i + 1] %= MOD

print(dp[-1])

Solution (Python):

import sys
input = sys.stdin.readline
import bisect
MOD = 998244353

n = int(input())
xd = []
places = [(10**12, 0)]
for _ in range(n):
    x, d = [int(item) for item in input().split()]
    xd.append((x, d))

xd.sort(reverse=True)
affect = [0] * (n + 1)
dp = [0] * (n + 1)
dp[0] = 1
for i, (x, d) in enumerate(xd):
    frm = x
    too = x + d 
    too_idx = i
    while too > places[-1][0]:
        _, too_idx = places.pop()
    places.append((frm, too_idx))
    dp[i + 1] = dp[i] + dp[too_idx]
    dp[i + 1] %= MOD

print(dp[-1])

Solution (Python):
n = int(input())
x = [list(map(int,input().split())) for i in range(n)] + [[11**9]]
x.sort(lambda x:x[0])
a = x[:-2]
y = a + [n]
a += [2,1]
for i in range(n-2,-1,-1):
  y[i] = i+1
  while x[y[i]][0] < sum(x[i]):
    y[i] = y[y[i]]
  a[i] = (a[i+1]+a[y[i]]) % 998244353
print(a[0])

Solution (Python):
n = int(input())
x = [list(map(int,input().split())) for i in range(n)] + [[10**10,]]
x.sort(key=lambda x:x[0])
a = [0]*(n-1)
y = a + [n]
a += [2,1]
for i in range(n-2,-1,-1):
  y[i] = i+1
  while x[y[i]][0] < sum(x[i]):
    y[i] = y[y[i]]
  a[i] = (a[i+1]+a[y[i]]) % 998244353
print(a[0])

Solution (Python):
n = int(input())
x = [list(map(int,input().split())) for i in range(n)]
x.sort(key=lambda x:x[0])
x.append([2*10**9+1,0])
y = [0]*(n-1) + [n-1]
a = [0]*(n-1) + [2]
for i in range(n-2,-1,-1):
  j = i+1
  while x[j][0] < sum(x[i]):
    j = y[j] + 1
  y[i] = j - 1
for i in range(n-2,-1,-1):
  a[i] = a[y[i]+1] if y[i]+1 < n else 1
  a[i] = (a[i]+a[i+1]) % 998244353
print(a[0])

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

class SegTree:
    def __init__(self, a):
        self.padding = -float('inf')
        self.n = len(a)
        self.N = 2 ** (self.n - 1).bit_length()
        self.data = [self.padding]*(self.N - 1) + a + [self.padding]*(self.N - self.n)
        for i in range(2 * self.N - 2, 0, -2):
            self.data[(i - 1) // 2] = max(self.data[i], self.data[i - 1])
    
    def __len__(self):
        return self.n
    
    def __getitem__(self, key):
        return self.data[self.N - 1 + key]

    def __setitem__(self, i, value):
        self._update(i, value)
    
    def _update(self, i, x):
        idx = self.N - 1 + i
        self.data[idx] = x
        while idx != 0:
            idx = (idx - 1) // 2
            self.data[idx] = max(self.data[2 * idx + 1], self.data[2 * idx + 2])
    
    def max(self, i, j):
        
        if i == j: 
            return self.data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j 
            result = self.padding
            while idx1 + 1 < idx2:
                if idx1 % 2 == 0: 
                    result = max(result, self.data[idx1])
                if idx2 % 2 == 1: 
                    result = max(result, self.data[idx2])
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                result = max(result, self.data[idx1])
            else: 
                result = max(result, self.data[idx1], self.data[idx2])
            
            return result

n = int(input())
x_d = []
for _ in range(n):
    x_d.append(tuple(map(int, input().split())))
x_d.sort(key=lambda t: t[0])
x = [t[0] for t in x_d]
xplusd = [t[0] + t[1] for t in x_d]
shortright = [bisect_left(x, xpdi) for xpdi in xplusd]
right = SegTree([t for t in shortright])
for i in range(n - 1, -1, -1):
    right[i] = right.max(i, right[i])
dp = [None] * n
dp.append(1)
for i in range(n - 1, -1, -1):
    dp[i] = (dp[i + 1] + dp[right[i]]) % 998244353
print(dp[0])

Solution (Python):
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
mod = 998244353
rs = []
xs = []
for _ in range(N):
  x, d = map(int, input().split())
  rs.append((x, d))
  xs.append(x)
rs.sort()
xs.sort()

class SegTree:
  def segfunc(self, x, y):
    return max(x, y) 
  def __init__(self, n, ide_ele, init_val):
    
    self.ide_ele = ide_ele
    
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res

seg = SegTree(N, 0, [0] * N)

for i in range(N - 1, -1, -1):
  j = bl(xs, rs[i][0] + rs[i][1])
  if j >= N: j -= 1
  else: j -= ((rs[i][0] + rs[i][1]) <= xs[j])
  seg.update(i, max(0, j, seg.query(i, j + 1)))
  

dp = [0] * (N + 1)
dp[0] = 1
for i in range(N):
  j = seg.query(i, i + 1)
  dp[i + 1] += dp[i]
  dp[i + 1] %= mod
  dp[j + 1] += dp[i]
  dp[j + 1] %= mod
  
print(dp[-1])

Solution (Python):


import sys
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

class SegTree:
    """
    セグメント木
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        
        if A:
            
            for i in range(n):
                self.tree[n2+i] = A[i]
            
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

N = INT()
XD = []
for _ in range(N):
    x, d = MAP()
    XD.append((x, d))

XD.sort()
X, _ = zip(*XD)
X = list(X)
X += [INF]

st = SegTree(N+1, max, -INF)
st.update(N, N)
for i in range(N-1, -1, -1):
    x, d = XD[i]
    j = bisect_left(X, x+d)
    mx = st.query(i, j)
    st.update(i, max(i, mx))


dp = [0] * (N+1)
dp[N] = 1
for i in range(N-1, -1, -1):
    
    dp[i] += dp[i+1]
    
    dp[i] += dp[st.get(i)+1]
    dp[i] %= MOD
ans = dp[0]
print(ans)

Solution (Python):
class SegTree:
    def __init__(self, init_val, ide_ele, seg_func):
        self.segfunc = seg_func
        n = len(init_val)
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

def bsearch(mn, mx, func):
    
    idx = (mx + mn)//2
    while mx-mn>1:
        if func(idx):
            idx, mx = (idx + mn)//2, idx
            continue
        idx, mn = (idx + mx)//2, idx
    return idx

import sys;input=sys.stdin.readline
mod = 998244353
N=int(input())
X = []
Y = []
for _ in range(N):
    x, d = map(int, input().split())
    X.append((x,d))
X.sort()
C = [0] * N
for i in range(N):
    x, d = X[i]
    k = bsearch(-1, N, lambda j: X[j][0] >= x+d)
    C[i] = k

st = SegTree(C, -1, max)
dp = [1]*(N+1)
for i in range(N-1, -1, -1):
    y=st.query(i, C[i]+1)
    st.update(i, y)
    dp[i] = (dp[i+1]+dp[y+1]) % mod
print(dp[0])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

MOD = 998244353
N = int(input())
robo = list(list(map(int,input().split()))for i in range(N))
robo.sort()
child = [[]for i in range(N+1)]
stack = [] 

for i in range(N):
    x,d = robo[i]
    while stack and stack[-1][0] <= x:
        stack.pop()
    if stack:
        child[stack[-1][1]].append(i+1)
    else:
        child[0].append(i+1)
    stack.append([x+d,i+1])

def func(x):
    hoge = 1
    for i in child[x]:
        hoge *= func(i)
        hoge %= MOD
    return (hoge + 1) % MOD

print(func(0)-1)