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):
import sys
sys.setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from collections import Counter
class HeapSet:
    def __init__(self):
        self.minQue = []
        self.maxQue = []
        self.counter = Counter()

    def insert(self, x):
        heappush(self.minQue, x)
        
        self.counter[x] += 1

    def erase(self, x):
        self.counter[x] -= 1

    def max(self):
        while self.maxQue and self.counter[-self.maxQue[0]] == 0:
            heappop(self.maxQue)
        return -self.maxQue[0] if self.maxQue else None

    def min(self):
        while self.minQue and self.counter[self.minQue[0]] == 0:
            heappop(self.minQue)
        return self.minQue[0] if self.minQue else None

MOD = 998244353
def resolve():
    def dfs(v):
        res = 1
        for to in to_edge[v]:
            res *= dfs(to)
            res %= MOD
        return res +1

    N = int(input())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    AB.sort()
    st = HeapSet()
    to_edge = [[] for _ in range(N)]
    
    for i in range(N-1, -1, -1):
        x = AB[i][0] 
        d = AB[i][1] 

        while st.min() and st.min()[0] < x + d:
            to_edge[i].append(st.min()[1])
            st.erase(st.min())
        st.insert((x,i)) 

    ans = 1
    for (x, v) in st.minQue:
        ans *= dfs(v)
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
from bisect import bisect_left

class SegTree:
    def __init__(self, raw_data):
        n = len(raw_data)
        self.size = 1 << (n.bit_length()) 
        self.data = [0] * (2*self.size)
        self.build(raw_data)

    def build(self, raw_data):
        for i, x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1, 0, -1):
            x = self.data[2*i]
            y = self.data[2*i+1]
            self.data[i] = x if x > y else y 
    
    def update(self, i, x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[2*i]
            y = self.data[2*i+1]
            self.data[i] = x if x > y else y 
            i >>= 1
    
    def get_data(self, i):
        return self.data[i+self.size]
    
    
    def get_max(self, L, R):
        L += self.size
        R += self.size + 1
        x = 0
        while L < R:
            if L & 1:
                y = self.data[L]
                if x < y: x = y
                L += 1
            if R & 1:
                R -= 1
                y = self.data[R]
                if x < y: x = y
            L >>= 1
            R >>= 1
        return x

N = int(input())
robots = sorted([tuple(map(int, input().split())) for _ in range(N)])
X, D = zip(*robots)
mod = 998244353

affects = [0] + [bisect_left(X, x+d) for x, d in robots]
seg = SegTree(affects)

S = [0] * len(affects)
for n in range(N, 0, -1):
    affect = affects[n]
    x = seg.get_max(n, affect)
    S[n] = x
    seg.update(n, x)

dp = [0] * (N+1)
dp[0] = 1
dp_cum = [1] * (N+1)
for n, r in enumerate(S[1:], 1):
    dp[r] += dp_cum[n-1]
    dp[r] %= mod
    dp_cum[n] = dp_cum[n-1] + dp[n]
    dp_cum[n] %= mod
print(dp_cum[-1])

Solution (Python):
MOD=998244353
import bisect
N=int(input())

xdlist=[]
for _ in range(N):
  x,d=map(int,input().split())
  xdlist.append((x,d-0.5))
xdlist.sort()


class SegTree:
  
  def __init__(self, init_val, segfunc, ide_ele):
    
    
    
    
    
    
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  
  def update(self, k, x):
    
    
    
    k += self.num
    self.tree[k] = x
    while k > 1:
      self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
      k >>= 1

  
  def query(self, l, r):
    
    
    
    res = self.ide_ele
    l += self.num
    r += self.num
    while l < r:
      if l & 1:
        res = self.segfunc(res, self.tree[l])
        l += 1
      if r & 1:
        res = self.segfunc(res, self.tree[r - 1])
      l >>= 1
      r >>= 1
    return res
  
def segfunc(x,y):
  return max(x,y) 
ide_ele=-float("inf") 
seg=SegTree([-float("inf")]*N, segfunc, ide_ele)

for i in reversed(range(N)):
  x,d=xdlist[i]
  right=x+d
  pos=bisect.bisect(xdlist,((x+d,float("inf"))))
  
  
  if pos==i+1:
    seg.update(i,i)
  else:
    max_pos=seg.query(i+1,pos)
    seg.update(i,max_pos)
    
dp=[2]*N
for i in reversed(range(N-1)):
  dp[i]=dp[i+1]
  right=seg.query(i,i+1)
  if right<N-1:
    dp[i]+=dp[right+1]
  else:
    dp[i]+=1
  dp[i]%=MOD
  

print(dp[0])

Solution (Python):
import sys
from bisect import bisect
def input():
	return sys.stdin.buffer.readline()[:-1]

MOD = 998244353
n = int(input())
r = []
for _ in range(n):
	x, d = map(int, input().split())
	r.append((-x, -x-d))
r.sort()

INF = 10**30

class Rmin():
	def __init__(self, size):
		
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

leftmost = Rmin(n)

wait = [r[0][0]]
dp = [[0 for _ in range(2)] for _ in range(n)]
dp[0] = [1, 1]
leftmost.Update(0, 0)

for i in range(1, n):
	dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % MOD	
	if r[i][1] < wait[-1]:
		b = bisect(wait, r[i][1])
		mi = leftmost.Get(b, i)
		dp[i][0] = dp[mi][0]
		leftmost.Update(i, mi)
	else:
		dp[i][0] = dp[i][1]
		leftmost.Update(i, i)
	wait.append(r[i][0])

print((dp[n-1][0] + dp[n-1][1]) % MOD)

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    mod = 998244353
    
    N = int(input())
    robot = [tuple(map(int, input().split())) for _ in range(N)]
    robot.sort()

    stack = []
    dp = [1] * (N+1)
    for i in reversed(range(N)):
        x, d = robot[i]
        while stack and robot[stack[-1]][0] < x + d:
            stack.pop()
        if stack:
            dp[i] = dp[i+1] + dp[stack[-1]]
        else:
            dp[i] = dp[i+1] + 1
        dp[i] %= mod
        stack.append(i)
    
    print(dp[0])

main()

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

mod = 998244353
N = int(input())
XD = [tuple(map(int, input().split())) for _ in range(N)]
XD.sort(key=lambda x : x[0])
children = [[] for _ in range(N)]
stack = []
for i, (x, d) in list(enumerate(XD))[::-1]:
    while stack and stack[-1][0] < x + d:
        y, j = stack.pop()
        children[i].append(j)
    stack.append((x, i))
val = [0] * N
for i in range(N)[::-1]:
    res = 1
    for j in children[i]:
        res = res * val[j] % mod
    val[i] = res + 1
ans = 1
for x, i in stack:
    ans = ans * val[i] % mod
print(ans)

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

mod = 998244353
N = int(input())
XD = [tuple(map(int, input().split())) for _ in range(N)]
XD.sort(key=lambda x : x[0])
children = [[] for _ in range(N)]
pq = []
for i, (x, d) in list(enumerate(XD))[::-1]:
    while pq and pq[0][0] < x + d:
        y, j = heappop(pq)
        children[i].append(j)
    heappush(pq, (x, i))
val = [0] * N
for i in range(N)[::-1]:
    res = 1
    for j in children[i]:
        res = res * val[j] % mod
    val[i] = res + 1
ans = 1
while pq:
    x, i = heappop(pq)
    ans = ans * val[i] % mod
print(ans)

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

mod = 998244353

class BITree:
    def __init__(self,n):
        self.s = [-10**9-1]*(n+1)
        self.n = n
    def change(self,idx,val):
        
        while idx < self.n+1:
            self.s[idx] = max(self.s[idx],val)
            idx += idx&(-idx)
        return
    def get(self,idx):
        
        res = -10**9-1
        while idx > 0:
            res = max(res,self.s[idx])
            idx -= idx&(-idx)
        return res


n = int(input())
ans = 1
XD = []
X = []
for i in range(n):
    x,d = map(int,input().split())
    XD.append((x,d))
    X.append(x)
XD.sort()
X.sort()
dp = [0]*(n+1)
dp[-1] = 1


BIT = BITree(n)
for i in range(n-1,-1,-1):
    x,d = XD[i]
    will = max(x+d,BIT.get(bisect.bisect_left(X, x+d)))
    BIT.change(i+1,will)
    
    dp[i] = dp[i+1] + dp[bisect.bisect_left(X, will)]
    dp[i] %= mod
print(dp[0])

Solution (Python):

import sys
from bisect import bisect_left
MOD = 998244353  

import math


class SegmentTree(object):
    

    def __init__(self, N):
        """サイズNの配列を元にしたセグメント木
        """
        
        self.idelem = -10**9
        
        self.func = max

        self.N0 = 1
        while self.N0 < N:
            self.N0 <<= 1
        self.tree = [self.idelem]*(2*self.N0)

    def update(self, k, x):
        """k番目の値をxに更新
        """
        k += self.N0-1
        self.tree[k] = x
        while k > 1:
            k = (k-1)//2
            self.tree[k] = self.func(self.tree[2*k+1], self.tree[2*k+2])

    def query(self, l, r):
        """区間[l, r)の最小値
        """
        l += self.N0-1
        r += self.N0-1
        s = self.idelem
        while l < r:
            if r % 2 == 0:
                r -= 1
                s = self.func(s, self.tree[r])

            if l % 2 == 0:
                s = self.func(s, self.tree[l])
                l += 1
            l //= 2
            r //= 2
        return s


def solve(N: int, X: "List[int]", D: "List[int]"):
    
    
    reachable = [0]*N

    
    X, D = zip(*sorted(zip(X, D)))
    

    
    for i, (x, d) in enumerate(zip(X, D)):
        reachable[i] = bisect_left(X, x+d)

    
    seg = SegmentTree(N)

    
    for v in reversed(range(N)):
        if v == N-1:
            seg.update(v, reachable[v])
            continue
        
        
        a = seg.query(v, reachable[v])
        if a > 0:
            seg.update(v, a)
        else:
            seg.update(v, v+1)

    true_reachable = [seg.query(v, v+1) for v in range(N)]

    

    dp = [0]*(N+1)
    dp[N] = 1
    for v in reversed(range(N)):
        dp[v] = dp[v+1]+dp[true_reachable[v]]
        dp[v] %= MOD
    print(dp[0])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    X = [int()] * (N)  
    D = [int()] * (N)  
    for i in range(N):
        X[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, X, D)


if __name__ == '__main__':
    main()

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

def solve():
    MOD = 998244353

    N = int(input())
    XDs = [tuple(map(int, input().split())) for _ in range(N)] + [(10**12, 0)]

    XDs.sort()
    Xs = [X for X, D in XDs]

    stack = [N]
    dp = [0] * (N+1)
    dp[-1] = 1
    for i in reversed(range(N)):
        X, D = XDs[i]
        while Xs[stack[-1]] < X+D:
            stack.pop()
        dp[i] = dp[stack[-1]] + dp[i+1]
        dp[i] %= MOD
        stack.append(i)

    print(dp[0])


solve()

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

def solve():
    MOD = 998244353
    INF = float('inf')

    N = int(input())
    XDs = [tuple(map(int, input().split())) for _ in range(N)] + [(10**12, 0)]

    XDs.sort()
    Xs = [X for X, D in XDs]

    def max2(x, y): return x if x >= y else y
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [-INF] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[i] = max2(data[i], data[iB])
    def setValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] = max2(data[iB], A)
            iB += iB & -iB
    def getMax(iA):
        iB = iA + 1
        ans = -INF
        while iB > 0:
            ans = max2(ans, data[iB])
            iB -= iB & -iB
        return ans

    data, numPow2 = makeBIT(N+1)
    setInit(list(range(N)))

    dp = [0] * (N+1)
    dp[-1] = 1
    for i in reversed(range(N)):
        X, D = XDs[i]
        j = bisect_left(Xs, X+D) - 1
        pos = getMax(j)
        setValue(i, pos)
        dp[i] = dp[pos+1] + dp[i+1]
        dp[i] %= MOD

    print(dp[0])


solve()

Solution (Python):
def main():
    from collections import deque
    from operator import itemgetter
    import sys
    input = sys.stdin.readline

    MOD = 998244353

    N = int(input())

    xds = []
    xs = []
    for _ in range(N):
        x, d = map(int, input().split())
        xds.append((x, d))
        xs.append(x)

    xds.sort(key=itemgetter(0), reverse=True)
    xs.sort()

    ps = [-1] * (N + 1)
    cands = deque()  
    for j, (x, d) in enumerate(xds):
        j = N - 1 - j
        while cands:
            cx, ci = cands[0]
            if x + d <= cx:
                
                break
            elif x <= cx < x + d:
                
                ps[ci] = j
                cands.popleft()
        cands.appendleft((x, j))

    ret = 1
    ctr = [1] * N
    for j, (x, d) in enumerate(xds):
        j = N - 1 - j
        par = ps[j]
        ctr[j] += 1  
        if ~par:
            ctr[par] = ctr[par] * ctr[j] % MOD
        else:
            ret = ret * ctr[j] % MOD  

    print(ret)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import bisect
con = 998244353; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	def __init__(self, N):
		self.N0 = 2 ** (N - 1).bit_length()
		self.data = [0] * (2 * self.N0)

	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = max(self.data[2 * k + 1], self.data[2 * k + 2])

	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = 0
		while L < R:
			if R & 1:
				R -= 1
				m = max(m, self.data[R - 1])
			if L & 1:
				m = max(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m


def main():
	N = int(input())
	XD = [None] * N
	for i in range(N):
		X, D = getlist()
		XD[i] = [X, D]
	XD.sort()
	Xl = [XD[i][0] for i in range(N)]
	Xl.append(INF)

	Seg = SegmentTree(N)
	IND = [None] * N
	for i in range(N):
		ind = bisect.bisect_left(Xl, XD[i][0] + XD[i][1]) - 1
		Seg.update(i, ind)
		IND[i] = ind

	
	DP = [[0] for i in range(N + 1)]
	DP[N] = 1
	
	

	for i in range(N - 1, -1, -1):
		ind = Seg.query(i, IND[i])
		Seg.update(i, ind)
		DP[i] = DP[i + 1] + DP[ind + 1]
		DP[i] %= con

	ans = DP[0]
	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n=int(readline())
segSize=n+1
def init_max(init_max_val):
    for i in range(segSize):
        seg_max[i+num_max-1]=init_max_val[i]
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res
ide_ele_max = 0
num_max =2**(segSize-1).bit_length()
seg_max=[ide_ele_max]*2*num_max
mod=998244353

m = map(int,read().split())
XD = sorted(zip(m,m))
X=[x for x,d in XD]

from bisect import bisect_right
X=[bisect_right(X,x+d-1)for x,d in XD]

init_max(list(range(segSize)))
update_max(n,n)
combs=[1]*(n+1)
t=0
for x,d in reversed(XD):
    idx=n-1-t
    t+=1
    p=X[idx]
    p=query_max(idx,p)
    update_max(idx,p)
    combs[idx]=(combs[p+1]+combs[idx+1])%mod
print(combs[0])

Solution (Python):
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = 998244353 ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [tuple(map(int,input().split())) for i in range(n)]
XD.append((-10**10,inf))
XD.sort()

now = 0
def dfs(node):
  global now
  pro = 1
  while now < n :
    if XD[now+1][0] < XD[node][0] + XD[node][1]:
      now += 1
      pro *= dfs(now)
      pro %= mod
    else:break
  return pro + 1
ans = dfs(0)
print((ans-1)%mod)

Solution (Python):
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left
class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        
        
        
        
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

    def _ascend(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _descend(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    
    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        
        
        
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._ascend(l0)
        self._ascend(r0 - 1)

    
    def sum(self, l, r):
        l += self._n
        r += self._n
        
        
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n = int(input())
    XD = [tuple(map(int, input().split())) for _ in range(n)]
    XD.sort()
    X = [a[0] for a in XD]

    
    A = [0] * n
    A[-1] = 1

    def compose(f, g):
        return f if f != INF else g

    def act(f, x):
        return f if f != INF else x

    tree = LazySegmentTree(A, add, 0, compose, INF, act)
    for i in range(n - 2, -1, -1):
        x = tree.sum(i + 1, n)
        tree.range_act(i, i + 1, (x + 1) % MOD) 
        x, d = XD[i]
        j = bisect_left(X, x + d)
        tree.range_act(i + 1, j, 0)

    print((tree.sum(0, n) + 1) % MOD)
resolve()

Solution (Python):
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.buffer.readline().rstrip()
from bisect import bisect_left
class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        
        
        
        
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

    def _ascend(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _descend(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    
    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        
        
        
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._ascend(l0)
        self._ascend(r0 - 1)

    
    def sum(self, l, r):
        l += self._n
        r += self._n
        
        
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n = int(input())
    XD = [tuple(map(int, input().split())) for _ in range(n)]
    XD.sort()
    X = [a[0] for a in XD]

    
    A = [0] * n
    A[-1] = 1

    def compose(f, g):
        return f if f != INF else g

    def act(f, x):
        return f if f != INF else x

    tree = LazySegmentTree(A, add, 0, compose, INF, act)
    for i in range(n - 2, -1, -1):
        x = tree.sum(i + 1, n)
        tree.range_act(i, i + 1, (x + 1) % MOD) 
        x, d = XD[i]
        j = bisect_left(X, x + d)
        tree.range_act(i + 1, j, 0)

    print((tree.sum(0, n) + 1) % MOD)
resolve()

Solution (Python):
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.buffer.readline().rstrip()
class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        
        
        
        
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

    def _ascend(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _descend(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    
    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        
        
        
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._ascend(l0)
        self._ascend(r0 - 1)

    
    def sum(self, l, r):
        l += self._n
        r += self._n
        
        
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n = int(input())
    XD = [tuple(map(int, input().split())) for _ in range(n)]
    XD.sort()
    X = [a[0] for a in XD]

    
    A = [0] * n
    A[-1] = 1

    def compose(f, g):
        return f if f != INF else g

    def act(f, x):
        return f if f != INF else x

    tree = LazySegmentTree(A, add, 0, compose, INF, act)
    for i in range(n - 2, -1, -1):
        x = tree.sum(i + 1, n)
        tree.range_act(i, i + 1, (x + 1) % MOD) 
        x, d = XD[i]
        if X[-1] < x + d:
            j = n
        elif X[0] >= x + d:
            j = 0
        else:
            l, r = 0, n - 1
            while r - l > 1:
                m = (l + r) // 2
                if X[m] < x + d:
                    l = m
                else:
                    r = m
            j = r
        tree.range_act(i + 1, j, 0)

    print((tree.sum(0, n) + 1) % MOD)
resolve()

Solution (Python):
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = 998244353 ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [tuple(map(int,input().split())) for i in range(n)]
XD.append((-10**10,inf))
XD.sort()

now = 0
visited1 = [] 
def dfs(node):
  visited1.append(node)

  global now
  pro = 1
  while now < n :
    if XD[now+1][0] < XD[node][0] + XD[node][1]:
      now += 1
      pro *= dfs(now)
      pro %= mod
    else:break
  return pro + 1
ans = dfs(0)
print((ans-1)%mod)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [tuple(map(int,input().split())) for i in range(n)]
XD.append((-10**10,inf))
XD.sort()

def dfs(node):
  res = 1
  i = node + 1
  while i < n+1:
    if XD[i][0] < XD[node][0] + XD[node][1]:
      pro,i = dfs(i)
      res *= pro
      res %= mod
    else: break

  return res + 1 , i
print((dfs(0)[0]-1)%mod)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [(-10**10,inf)]
for i in range(n):
  x,d = map(int,input().split())
  XD.append((x,d))
XD.sort()

def dfs(node):
  res = 1
  i = node + 1
  while i < n+1:
    if XD[i][0] < XD[node][0] + XD[node][1]:
      pro,i = dfs(i)
      res *= pro
      res %= mod
    else: break

  return res + 1 , i
print((dfs(0)[0]-1)%mod)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [(-10**10,inf)]
for i in range(n):
  x,d = map(int,input().split())
  XD.append((x,d))
XD.sort()
visited = [0] * (n+1)
def dfs(node):
  visited[node] = 1
  res = 1
  i = node + 1
  while i < n+1:
    if XD[i][0] < XD[node][0] + XD[node][1]:
      if visited[i]:continue
      pro,i = dfs(i)
      res *= pro
      res %= mod
    else: break
  
  return res + 1 , i
print((dfs(0)[0]-1)%mod)