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.



Sample input:
2
1 5
3 3


Sample output:
3

Submission status: Accepted

Solution code:
def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.readline

    class SegTree():
        def __init__(self, N):
            # N:  処理する区間の長さ
            self.N0 = 2 ** (N - 1).bit_length()
            self.INF = 2100000000
            self.seg_min = [-self.INF] * (2 * self.N0)

        def update(self, index, value):
            index += self.N0 - 1
            self.seg_min[index] = value
            while index > 0:
                index = (index - 1) >> 1
                L = self.seg_min[index * 2 + 1]
                R = self.seg_min[index * 2 + 2]
                if L > R:
                    self.seg_min[index] = L
                else:
                    self.seg_min[index] = R
                # self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

        def query(self, first, last):
            first += self.N0 - 1
            last += self.N0 - 1
            ret = -self.INF
            while first <= last:
                if not first & 1:
                    ret_new = self.seg_min[first]
                    if ret_new > ret:
                        ret = ret_new
                    # ret = min(ret, self.seg_min[first])
                if last & 1:
                    ret_new = self.seg_min[last]
                    if ret_new > ret:
                        ret = ret_new
                    # ret = min(ret, self.seg_min[last])
                first = first >> 1
                last = (last >> 1) - 1
            return ret

    mod = 998244353
    N = int(input())
    info = []
    X = []
    for _ in range(N):
        x, d = map(int, input().split())
        info.append((x, x+d))
        X.append(x)
    info.sort(key=lambda p: p[0])
    X.sort()
    segtree = SegTree(N+1)
    for i in range(N):
        segtree.update(i+1, info[i][1])

    dp = [0] * (N+1)
    dp[-1] = 1
    for i in range(N-1, -1, -1):
        l, r = info[i]
        j = bisect_left(X, r)
        rmax = segtree.query(i+1, j)
        #print(i+1, j, rmax)
        segtree.update(i+1, rmax)
        j2 = bisect_left(X, rmax)
        dp[i] = (dp[i+1] + dp[j2])%mod
    print(dp[0])
    #print(dp)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 998244353
N = int(input())
X = []
for _ in range(N):
    x, d = map(int, input().split())
    X.append((x, x + d))

X = sorted(X, key = lambda x: x[0])
L = [(0, -(10**9+1), 10**9+1)]
P = [-1] * (N+1)
for i, (x, y) in enumerate(X):
    while L[-1][2] <= y:
        if L[-1][2] > x and P[i+1] < 0:
            P[i+1] = L[-1][0]
        L.pop()
    if P[i+1] < 0:
        P[i+1] = L[-1][0]
    L.append((i+1, x, y))

C = [[] for _ in range(N+1)]
for i, p in enumerate(P):
    if p >= 0:
        C[p].append(i)

Y = [1] * (N+1)
for i in range(N+1)[::-1]:
    s = 1
    for j in C[i]:
        s = s * (Y[j] + 1) % mod
    Y[i] = s

print(Y[0])

Submission status: Accepted

Solution code:
law = 998244353
n = int(input())
robots = [tuple(map(int, input().split())) for _ in range(n)]

robots.sort(reverse = True)

ntrig = [-1] * n
dp = [0] * n
dp[0] = 2
for i, (x, d) in enumerate(robots):
    if i == 0:
        continue
    next = i-1
    while x + d > robots[next][0]:
        next = ntrig[next]
        if next == -1:
            break
    ntrig[i] = next
    if next == -1:
        dp[i] = dp[i-1] + 1
    else:
        dp[i] = dp[i-1] + dp[next]
    dp[i] %= law

print(dp[n-1])

Submission status: Accepted

Solution code:
n = int(input())
a = sorted((tuple(map(int, input().split())) for i in range(n)))
a.append((10 ** 18, 1))
mo = 998244353
dp = [0] * (n + 1)
dp[n] = 1
f = list(range(n))
fr = list(range(n))
bd = [x + d for x, d in a]
def getF(u):
    if f[f[u]] != f[u]:
        f[u] = getF(f[u])
        return f[u]
    return f[u]
def uniF(u, v):
    u = getF(u)
    v = getF(v)
    if u == v:
        return
    f[u] = v
    fr[v] = max(fr[v], fr[u])
    bd[v] = max(bd[v], bd[u])
for i in range(n - 1, -1, -1):
    cur = i
    while fr[getF(cur)] + 1 < n and a[fr[getF(cur)] + 1][0] < bd[getF(cur)]:
        uniF(cur, fr[getF(cur)] + 1)
    dp[i] = (dp[i + 1] + dp[fr[getF(cur)] + 1]) % mo
print(dp[0])

Submission status: Accepted

Solution code:
import sys,bisect
input = sys.stdin.readline

n = int(input())
dg = 10**10
mod = 998244353
xd = []

for i in range(n):
    x,d = map(int,input().split())
    xd.append((x+10**9)*dg + d)

xd.sort()

dp = [0]*(n+1)
ma = list(range(n+1))

def init_max(init_max_val):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    #built
    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 = -1

#num_max:n以上の最小の2のべき乗
num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max

init_max(ma)

dp[n] = 1


for i in range(n-1,-1,-1):
    x,d = xd[i]//dg,xd[i]%dg
    k = bisect.bisect_left(xd,(x+d)*dg)
    
    ma[i] = query_max(i,k)
    update_max(i,ma[i])
    
    dp[i] = (dp[i+1]+dp[ma[i]+1])%mod

print(dp[0]%mod)

Submission status: Accepted

Solution code:
class segment_tree:
    def __init__(self, N, operator_M, e_M):
        self.op_M = operator_M
        self.e_M = e_M
        
        self.N0 = 1<<(N-1).bit_length()
        self.dat = [self.e_M]*(2*self.N0)
    
    # 長さNの配列 initial で初期化
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])

    # a_k の値を x に更新
    def update(self,k,x):
        k += self.N0
        self.dat[k] = x
        k //= 2
        while k:
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
            k //= 2

    # 区間[L,R]をopでまとめる
    def query(self,L,R):
        L += self.N0; R += self.N0 + 1 
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.dat[R],sr)
            if L & 1:
                sl = self.op_M(sl,self.dat[L])
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)

    def get(self, k): #k番目の値を取得。query[k,k]と同じ
        return self.dat[k+self.N0]


# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

n = int(input())
xd = [[int(i) for i in readline().split()] for _ in range(n)]
xd.sort(key=lambda x: x[0])

xx = [xdi[0] for xdi in xd]
from bisect import bisect_left

a = [bisect_left(xx,x+d)-1 for x,d in xd]
seg = segment_tree(n, max, 0)
seg.build(a)

b = list(range(n))
for i in range(n-2,-1,-1):
    if i+1 <= a[i]:
        b[i] = seg.query(i+1,a[i])   
        seg.update(i,b[i])

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

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

#print(a)
#print(b)
#print(dp)
print(dp[0])

Submission status: Accepted

Solution code:
import bisect
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
co = []
for i in range(n):
    co.append(na())
    co[-1][1] += co[-1][0]
co.sort(key=lambda x: x[0])


class Segtreermq:
    def __init__(self, n):
        self.H = 1
        while self.H < n:
            self.H *= 2
        self.M = self.H * 2
        self.vals = [999999999999] * self.M

    def update(self, pos, v):
        self.vals[self.H+pos] = v
        x = self.H+pos>>1
        while x >= 1:
            self.vals[x] = min(self.vals[2*x], self.vals[2*x+1])
            x>>=1

    def min(self, l, r):
        ret = 999999999999999
        if l >= r:
            return ret
        while l != 0:
            f = l&-l
            if l+f > r:
                break
            v = self.vals[(self.H+l)//f]
            if v < ret:
                ret = v
            l += f

        while l < r:
            f = r & -r
            v = self.vals[(self.H+r)//f-1]
            if v < ret:
                ret = v
            r -= f
        return ret

xs = [_[0] for _ in co]

st = Segtreermq(n)
for i in range(n-1,-1,-1):
    ind = bisect.bisect_left(xs, co[i][1])
    reach = max(co[i][1], -st.min(i, ind))
    st.update(i, -reach)
    co[i][1] = reach

mod = 998244353
stack = []
dp = [0] * n
for i in range(n-1,-1,-1):
    val = 1
    while len(stack) > 0 and co[stack[-1]][1] <= co[i][1]:
        val = val * dp[stack[-1]] % mod
        stack.pop(-1)
    dp[i] = (val + 1) % mod
    stack.append(i)

ans = 1
for s in stack:
    ans = ans * dp[s] % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from bisect import bisect_left

MOD = 998244353

N = int(readline())
m = map(int,read().split())
XD = sorted(zip(m,m))
X, D = zip(*XD)

class MaxSegTree():
    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):
        # raw_data は 0-indexed
        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[i+i]; y = self.data[i+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[i+i]; y = self.data[i+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,R] に対する値を返す
        L += self.size
        R += self.size + 1
        # [L,R) に変更
        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

R = [0] + [bisect_left(X, x + d) for x,d in XD]
seg = MaxSegTree(R)

S = [0] * len(R)
for n in range(N,0,-1):
    r = R[n]
    x = seg.get_max(n, r)
    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])

Submission status: Runtime Error

Solution code:
import bisect


def main():
    MOD = 998244353
    N = int(input())
    robot_list = [list(map(int, input().split())) for _ in range(N)]
    robot_list.sort()  # x座標の昇順でソート
    X = [robot[0] for robot in robot_list]
    D = [robot[1] for robot in robot_list]
    next_robot_list = [-1] * N

    def search_next_robot(r):
        if next_robot_list[r] >= 0:
            return next_robot_list[r]
        if r == N - 1:
            next_robot_list[r] = N
            return N
        if X[r] + D[r] <= X[r + 1]:
            next_robot_list[r] = r + 1
            return r + 1
        next_r_to = bisect.bisect_left(X, X[r] + D[r])
        ret = next_r_to
        for next_r in range(r + 1, next_r_to):
            ret = max(ret, search_next_robot(next_r))
        next_robot_list[r] = ret
        return ret

    for n in range(N):
        search_next_robot(n)

    cnt = [0] * (N + 1)
    cnt[0] = 1
    for n in range(N):
        cnt[n + 1] += cnt[n]
        cnt[n + 1] %= MOD
        cnt[next_robot_list[n]] += cnt[n]
        cnt[next_robot_list[n]] %= MOD
    print(cnt[N])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
dis = [0]*(10**30)
for i in range(N):
  x,d=map(int,input().split())
  dis[x:x+d+1] += 1

print(d)

Submission status: Runtime Error

Solution code:
from functools import reduce
import heapq, sys


input = sys.stdin.readline
N = int(input())
XD = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0], reverse=True)
P = 998244353


class Node:
    def __init__(self, ch):
        self.ch = ch

    def cal(self):
        if len(self.ch) == 0:
            return 2
        return reduce(lambda a, b: (a * b) % P, [ch.cal() for ch in self.ch]) + 1


hq = []  # (x, Node)
heapq.heapify(hq)
for x, d in XD:
    ch = []
    while len(hq) != 0 and hq[0][0] < x+d:
        ch.append(heapq.heappop(hq)[1])
    heapq.heappush(hq, (x, Node(ch)))

ans = reduce(lambda a, b: (a * b) % P, [node.cal() for x, node in hq])
print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce
import heapq, sys


input = sys.stdin.readline
N = int(input())
XD = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0], reverse=True)
P = 998244353


class Node:
    def __init__(self, ch):
        self.ch = ch

    def cal(self):
        if len(self.ch) == 0:
            return 2
        return reduce(lambda a, b: (a * b) % P, [ch.cal() for ch in self.ch]) + 1


hq = []  # (x, Node)
heapq.heapify(hq)
for x, d in XD:
    ch = []
    while len(hq) != 0 and hq[0][0] <= x+d:
        ch.append(heapq.heappop(hq)[1])
    heapq.heappush(hq, (x, Node(ch)))

ans = reduce(lambda a, b: (a * b) % P, [node.cal() for x, node in hq])
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import bisect
MOD = 998244353
n = int(input())
XD = sorted([list(map(int, input().split())) for _ in range(n)])
X, D = zip(*XD)


C = list(range(n))

class RmaxQ:
    def __init__(self, original):
        self.n = len(original)
        self.INF = -float("inf")
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = max(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            i >>= 1
            self.seg[i] = max(self.seg[2*i], self.seg[2*i+1])
                
    def query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = max(res, self.seg[r-1])
            if l & 1:
                res = max(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res
    
seg = RmaxQ(C)
for i in range(n):
  x, d = XD[n-1-i]
  t = bisect.bisect_left(X, x+d
  seg.update(n-1-i, max(t, seg.query(n-1-i, t)))

dp = [0]*(n+1)
l = [0]*n
l[-1] = n
dp[-1] = 1
for i in range(n):
  x, d = XD[n-1-i]
  m = bisect.bisect_left(X, x+d)
  t = seg.query(n-1-i, m)
  dp[n-1-i] = dp[n-i] + dp[t]
  dp[n-1-i] %= MOD
print(dp[0])

Submission status: Runtime Error

Solution code:

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)
        #heappush(self.maxQue, -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)]
    # treeを作成
    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()

Submission status: Runtime Error

Solution code:
n=int(input())
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

import sys
read = sys.stdin.buffer.read
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])

Submission status: Runtime Error

Solution code:
 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)

Submission status: Runtime Error

Solution code:
import bisect
MOD = 998244353
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )


n = int(input())
ls = list()
for i in range(n):
    x,d = map(int, input().split())
    ls.append((x,x+d))

ls.sort()

g = [list() for _ in range(n)]
INF = 1001001001
last = -1
def dfs_g(u):
    global last
    to = ls[u][1]
    idx = bisect.bisect_left(ls, (to,-INF))
    v = u+1
    while v < idx:
        if last >= v:
            continue
        g[u].append(v)
        last = v
        dfs_g(v)
        v = last
        v += 1

root = list()
while last < n-1:
    last+=1
    root.append(last)
    dfs_g(last)
    
def dfs_dp(u,p=-1):
    if len(g[u]) == 0:
        return mint(2)
    res = mint(1)
    for v in g[u]:
        if v == p:
            continue
        res *= dfs_dp(v,u)
    res += mint(1)
    return res

ans = mint(1)

for r in root:
    ans *= dfs_dp(r)

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

n = int(input())
X = sorted([list(map(int,input().split())) for i in range(n)])
mod = 998244353
e = [[] for i in range(n)]

def dfs(x):
    count = 1

    for i in e[x]:
        count *= dfs(i)
        count %= mod
    return count+1

q = deque([])

for i in range(n-1,-1,-1):
    a,b = X[i]
    while q and q[0][0] < a+b:
        e[i].append(q[0][1]) 
        q.popleft()
    q.appendleft([a,i])

ans = 1
for i,j in q:
    ans *= dfs(j)
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(200010)

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

@lru_cache(maxsize=200010)
def arr(i,k):
  global n,xd
  if i==n:return n
  if k<=xd[i][0]:return i
  return arr(i+1,max(k,xd[i][0]+xd[i][1]))

dp=[0]*(n+1)
dp[0]=1
for i in range(n):
  dp[i+1]=(dp[i]+dp[i+1])%mod
  dp[arr(i+1,xd[i][0]+xd[i][1])]=(dp[i]+dp[arr(i+1,xd[i][0]+xd[i][1])])%mod
  
print(dp[n])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=200010)
def arr(i,k):
  global n,xd
  if i==n:return n
  if k<=xd[i][0]:return i
  return arr(i+1,max(k,xd[i][0]+xd[i][1]))

dp=[0]*(n+1)
dp[0]=1
for i in range(n):
  dp[i+1]=(dp[i]+dp[i+1])%mod
  dp[arr(i+1,xd[i][0]+xd[i][1])]=(dp[i]+dp[arr(i+1,xd[i][0]+xd[i][1])])%mod
  
print(dp[n])

Submission status: Runtime Error

Solution code:
from operator import itemgetter

def main():
    n = int(input())
    xd = [map(int, input().split()) for _ in range(n)]
    mod = 998244353
    INF = 10 ** 10

    xx = [(x, x + d, i) for i, (x, d) in enumerate(xd, 1)]
    xx.sort()
    c = [[] for _ in range(n + 1)]
    stack = [(INF, 0)]
    for l, r, i in xx:
        while stack[-1][0] <= l:
            stack.pop()

        ip = stack[-1][1]
        c[ip].append(i)
        stack.append((r, i))

    order = map(itemgetter(2), xx)

    dp = [1] * (n + 1)
    for u in order[::-1]:
        for v in c[u]:
            dp[u] *= dp[v]
            dp[u] %= mod

        dp[u] += 1
        dp[u] %= mod

    ans = dp[0] - 1
    ans %= mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
! cp answer/F/in/03.txt tmp_in

import numpy as np

M = 998244353

n = int(input())
xs = [0] * n
ds = [0] * n
for i in range(n):
    x, d = (int(c) for c in input().split())
    ds[i] = d
    xs[i] = x
xs = np.array(xs)
ds = np.array(ds)

import sys
sys.setrecursionlimit(max(1000,n))

index = xs.argsort()
xs = xs[index]
ds = ds[index]

def _sub(i):
    # 深さ優先探索しながらi番目以下の組み合わせと、次に調べるべき番号を返す
    if i==n-1:
        return 2, n
    res = 1
    ind = i+1
    while True:
        if (xs[i]+ds[i] <= xs[ind]):
            break
        o, ind = _sub(ind)
        res *= o
        res %= M
        if ind>=n:
            break
    return res+1, ind
out = []
done = 0
while True:
    o, done = _sub(done)
    out.append(o)
    if done>=n:
        break
result = 1
for o in out:
    result *= o
    result %= M
print(result)

Submission status: Runtime Error

Solution code:

import numpy as np

M = 998244353

n = int(input())
xs = [0] * n
ds = [0] * n
for i in range(n):
    x, d = (int(c) for c in input().split())
    ds[i] = d
    xs[i] = x
xs = np.array(xs)
ds = np.array(ds)

import sys
sys.setrecursionlimit(n)

index = xs.argsort()
xs = xs[index]
ds = ds[index]

def _sub(i):
    # 深さ優先探索しながらi番目以下の組み合わせと、次に調べるべき番号を返す
    if i==n-1:
        return 2, n
    res = 1
    ind = i+1
    while True:
        if (xs[i]+ds[i] <= xs[ind]):
            break
        o, ind = _sub(ind)
        res *= o
        res %= M
        if ind>=n:
            break
    return res+1, ind
out = []
done = 0
while True:
    o, done = _sub(done)
    out.append(o)
    if done>=n:
        break
result = 1
for o in out:
    result *= o
    result %= M
print(result)

Submission status: Runtime Error

Solution code:
import numpy as np

M = 998244353

n = int(input())
xs = [0] * n
ds = [0] * n
for i in range(n):
    x, d = (int(c) for c in input().split())
    ds[i] = d
    xs[i] = x
xs = np.array(xs)
ds = np.array(ds)

index = xs.argsort()
xs = xs[index]
ds = ds[index]

def _sub(i):
    # 深さ優先探索しながらi番目以下の組み合わせと、次に調べるべき番号を返す
    if i==n-1:
        return 2, n
    res = 1
    ind = i+1
    while True:
        if (xs[i]+ds[i] <= xs[ind]):
            break
        o, ind = _sub(ind)
        res *= o
        res %= M
        if ind>=n:
            break
    return res+1, ind
out = []
done = 0
while True:
    o, done = _sub(done)
    out.append(o)
    if done>=n:
        break
result = 1
for o in out:
    result *= o
    result %= M
print(result)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 200100;

int N;
pair <int, int> p[MAXN];
ll nreach[MAXN], dp[MAXN];

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) cin >> p[i].first >> p[i].second;
    sort (p, p + N);
    for (int i = N - 1; i >= 0; i--) {
        int xend = p[i].first + p[i].second;
        int cloc = i + 1;

        while (cloc < N && p[cloc].first < xend)
            cloc = nreach[cloc];
        nreach[i] = cloc;
    }
    dp[0] = 1;
    for (int i = 0; i < N; i++) {
        dp[i] %= 998244353;
        dp[i+1] += dp[i], dp[nreach[i]] += dp[i];
    }
    cout << dp[N] % 998244353 << "\n";
}

Submission status: Runtime Error

Solution code:
class Solution:

    def solve(self, N: int, XD):

        m = 998244353

        XD.sort(key=lambda x: x[0])

        to = [[] for _ in range(N)]

        li = []

        for i in range(N-1, -1, -1):
            x, d = XD[i]
            while len(li) > 0 and li[0][0] < x + d:
                to[i].append(li[0][1])
                li.remove(li[0])

            li.insert(0, (x, i))

        ans = 1

        def dfs(v: int):
            res = 1
            for u in to[v]:
                res *= dfs(u)

            return (res + 1) % m

        for r in li:
            v = r[1]
            ans *= dfs(v)
            ans %= m

        return ans


if __name__ == '__main__':

    # standard input
    N = int(input())
    XD = []
    for _ in range(N):
        XD.append(tuple(map(int, input().split())))

    # solve
    solution = Solution()
    answer = solution.solve(N, XD)
    print(answer)