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: Time Limit Exceeded

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 998244353

def ddprint(x):
  if DBG:
    print(x)


class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = max( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = max( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        l = x+s.n-1
        r = y+s.n-1
        res = s.unit
        while l<r:
            if not l%2:
                res = s.oper(res,s.ary[l])
                l += 1
            if not r%2:
                r -= 1
                res = s.oper(res,s.ary[r])
            l >>= 1
            r >>= 1
        return res


    def query2(s,x,y):
        return s.querycore(x,y,0,0,s.n)

    # x,y: from query  k: suffix at focus l,r: range for k
    # right ends (y,r) not included

    def querycore(s,x,y,k,l,r):
        if r<=x or y<=l:
            return s.unit
        if x<=l and r<=y:
            return s.ary[k]
        vl = s.querycore(x,y,2*k+1,l,(l+r)//2)
        vr = s.querycore(x,y,2*k+2,(l+r)//2,r)
        return max(vl, vr)

# # # #
import bisect
n = inn()
xd = []
for i in range(n):
    xx,dd = inm()
    xd.append((xx,dd))
xd.sort()
x = [xd[i][0] for i in range(n)]

#ddprint(xd)
#ddprint(x)

r = [i for i in range(n)]
sgt = Segtree(n,0,lambda x,y: max(x,y))
sgt.setary(r)
f = [0]*(n+1)
f[n] = 1
f[n-1] = 2
for i in range(n-2,-1,-1):
    xx,dd = xd[i]
    j = bisect.bisect_left(x,xx+dd)
    k = sgt.query(i,j)
    sgt.set(i,k)
    f[i] = (f[i+1] + f[k+1])%R
    #ddprint(f"i {i} x {xx} d {dd} j {j}")

#ddprint(f)
print(f[0])

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(input())
XD=[]
for _ in range(n):
    x,d=map(int,input().split())
    XD.append([x,d])
XD.sort()
X=[]
D=[]
for i in range(n):
    X.append(XD[i][0])
    D.append(XD[i][1])
l=[]
for i in range(n):
    l.append(bisect.bisect_left(X,X[i]+D[i])-1)
l_=[0]*n
for i in range(n):
    l[n-i-1]=max([l[j] for j in range(n-i-1,l[n-i-1]+1)])
dp=[0]*(n+1)
dp[n]=1
for i in range(n):
    dp[n-i-1]=(dp[n-i]+dp[l[n-i-1]+1])%998244353
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc158/tasks/abc158_f

このロボットを選ぶと、どのロボットが取り除かれる、がわかったとする
左から選ぶ・選ばないを選択していく
選んだ時、次に選択可能になるのは取り除かれる一番右のロボット+1番目
選ばなければそこが変わるので重複はあり得ない。左からdpすれば終わり～


あとはどのロボットを選ぶと、どこまでのロボットが取り除かれるかを計算する
メモ型再帰で実装できそう。0個の場合はそれで終わり。そうでなければ・・・あれ
→むりやん

別の方法…→右から決めていくのはそうで、区間最大値を取ればよい
→セグ木のRMQ

"""

#一転更新区間取得のセグ木とRMQである(最大取得したいなら負で突っ込めばおｋ？)
#query区間左,右は実際に求めたい区間(半開区間なので右は+1しておくこと)
#注目ノード番号は0でOK
#担当範囲左,担当範囲右　は、それぞれ　0 , (len(セグ木)+1)//2 にしておくこと

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    i = 0
    ret = []
    while 2 ** (i-1) < n:

        for j in range(2 ** i):
            ret.append(first)

        i += 1

    return ret

def RMQ_update_point(num,point,tree): #葉のindex(0-origin)がpointの要素をnumにする/treeはセグ木

    i = (len(tree) - 1) // 2 + point
    tree[i] = num
    while i > 0:
        i = (i - 1) // 2
        tree[i] = min(tree[i * 2 + 2] , tree[i * 2 + 1])

    return

def RMQ_query(a,b,k,l,r,tree): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        return float("inf")
    
    if a <= l and r <= b: #区間が完全に含まれる場合自分
        return tree[k]

    c1 = RMQ_query(a,b,2*k+1,l,(l+r)//2,tree)
    c2 = RMQ_query(a,b,2*k+2,(l+r)//2,r,tree)   

    return min(c1,c2)



N = int(input())

XD = []
Xlis = []

for i in range(N):

    X,D = map(int,input().split())
    XD.append([X,D])
    Xlis.append(X)

XD.sort()
XD.reverse()
Xlis.sort()

tree = make_ST(N,0)
lis = []

#print (Xlis)

import bisect
for i in range(N):

    nx,nd = XD[i]
    ind = bisect.bisect_left(Xlis,nx+nd)

    nans = RMQ_query(N-i-1,ind,0,0,(len(tree)+1)//2,tree)
    nans *= -1
    RMQ_update_point(-1 * max(nans,ind),N-i-1,tree)
    lis.append(max(nans,ind))

lis.reverse()
#print (lis)

ans = 0
dp = [0] * (N+1)
dp[0] = 1

mod = 998244353
for i in range(N):

    dp[i+1] += dp[i]
    dp[lis[i]] += dp[i]

    dp[i+1] %= mod
    dp[lis[i]] %= mod

print (dp[-1])

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc158/tasks/abc158_f

このロボットを選ぶと、どのロボットが取り除かれる、がわかったとする
左から選ぶ・選ばないを選択していく
選んだ時、次に選択可能になるのは取り除かれる一番右のロボット+1番目
選ばなければそこが変わるので重複はあり得ない。左からdpすれば終わり～


あとはどのロボットを選ぶと、どこまでのロボットが取り除かれるかを計算する
メモ型再帰で実装できそう。0個の場合はそれで終わり。そうでなければ・・・あれ
→むりやん

別の方法…→右から決めていくのはそうで、区間最大値を取ればよい
→セグ木のRMQ

"""

#一転更新区間取得のセグ木とRMQである(最大取得したいなら負で突っ込めばおｋ？)
#query区間左,右は実際に求めたい区間(半開区間なので右は+1しておくこと)
#注目ノード番号は0でOK
#担当範囲左,担当範囲右　は、それぞれ　0 , (len(セグ木)+1)//2 にしておくこと

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    i = 0
    ret = []
    while 2 ** (i-1) < n:

        for j in range(2 ** i):
            ret.append(first)

        i += 1

    return ret

def RMQ_update_point(num,point,tree): #葉のindex(0-origin)がpointの要素をnumにする/treeはセグ木

    i = (len(tree) - 1) // 2 + point
    tree[i] = num
    while i > 0:
        i = (i - 1) // 2
        tree[i] = min(tree[i * 2 + 2] , tree[i * 2 + 1])

    return

def RMQ_query(a,b,k,l,r,tree): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        return float("inf")
    
    if a <= l and r <= b: #区間が完全に含まれる場合自分
        return tree[k]

    c1 = RMQ_query(a,b,2*k+1,l,(l+r)//2,tree)
    c2 = RMQ_query(a,b,2*k+2,(l+r)//2,r,tree)   

    return min(c1,c2)



N = int(input())

XD = []
Xlis = []

for i in range(N):

    X,D = map(int,input().split())
    XD.append([X,D])
    Xlis.append(X)

XD.sort()
XD.reverse()
Xlis.sort()

tree = make_ST(N,0)
lis = []

#print (Xlis)

import bisect
for i in range(N):

    nx,nd = XD[i]
    ind = bisect.bisect_left(Xlis,nx+nd)

    nans = RMQ_query(N-i-1,ind,0,0,(len(tree)+1)//2,tree)
    nans *= -1
    RMQ_update_point(-1 * max(nans,ind),N-i-1,tree)
    lis.append(max(nans,ind))

lis.reverse()
#print (lis)

ans = 0
dp = [0] * (N+1)
dp[0] = 1

mod = 998244353
for i in range(N):

    dp[i+1] += dp[i]
    dp[lis[i]] += dp[i]

    dp[i] %= mod
    dp[lis[i]] %= mod

print (dp[-1])

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 998244353

def ddprint(x):
  if DBG:
    print(x)


class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = max( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = max( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        return s.querycore(x,y,0,0,s.n)

    # x,y: from query  k: suffix at focus l,r: range for k
    # right ends (y,r) not included

    def querycore(s,x,y,k,l,r):
        if r<=x or y<=l:
            return s.unit
        if x<=l and r<=y:
            return s.ary[k]
        vl = s.querycore(x,y,2*k+1,l,(l+r)//2)
        vr = s.querycore(x,y,2*k+2,(l+r)//2,r)
        return max(vl, vr)

# # # #
import bisect
n = inn()
xd = []
for i in range(n):
    xx,dd = inm()
    xd.append((xx,dd))
xd.sort()
x = [xd[i][0] for i in range(n)]

#ddprint(xd)
#ddprint(x)

r = [i for i in range(n)]
sgt = Segtree(n,0,lambda x,y: max(x,y))
sgt.setary(r)
f = [0]*(n+1)
f[n] = 1
f[n-1] = 2
for i in range(n-2,-1,-1):
    xx,dd = xd[i]
    j = bisect.bisect_left(x,xx+dd)
    k = sgt.query(i,j)
    sgt.set(i,k)
    f[i] = (f[i+1] + f[k+1])%R
    #ddprint(f"i {i} x {xx} d {dd} j {j}")

#ddprint(f)
print(f[0])

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 998244353

def ddprint(x):
  if DBG:
    print(x)


class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = max( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = max( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        return s.querycore(x,y,0,0,s.n)

    # x,y: from query  k: suffix at focus l,r: range for k
    # right ends (y,r) not included

    def querycore(s,x,y,k,l,r):
        if r<=x or y<=l:
            return s.unit
        if x<=l and r<=y:
            return s.ary[k]
        vl = s.querycore(x,y,2*k+1,l,(l+r)//2)
        vr = s.querycore(x,y,2*k+2,(l+r)//2,r)
        return max(vl, vr)

# # # #
import bisect
n = inn()
xd = []
for i in range(n):
    xx,dd = inm()
    xd.append((xx,dd))
xd.sort()
x = [xd[i][0] for i in range(n)]

ddprint(xd)
ddprint(x)

r = [i for i in range(n)]
sgt = Segtree(n,0,lambda x,y: max(x,y))
sgt.setary(r)
f = [0]*(n+1)
f[n] = 1
f[n-1] = 2
for i in range(n-2,-1,-1):
    xx,dd = xd[i]
    j = bisect.bisect_left(x,xx+dd)
    k = sgt.query(i,j)
    sgt.set(i,k)
    f[i] = (f[i+1] + f[k+1])%R
    #ddprint(f"i {i} x {xx} d {dd} j {j}")

ddprint(f)
print(f[0])

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 998244353

def ddprint(x):
  if DBG:
    print(x)


class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        return s.querycore(x,y,0,0,s.n)

    # x,y: from query  k: suffix at focus l,r: range for k
    # right ends (y,r) not included

    def querycore(s,x,y,k,l,r):
        if r<=x or y<=l:
            return s.unit
        if x<=l and r<=y:
            return s.ary[k]
        vl = s.querycore(x,y,2*k+1,l,(l+r)//2)
        vr = s.querycore(x,y,2*k+2,(l+r)//2,r)
        return s.oper(vl, vr)

# # # #
import bisect
n = inn()
xd = []
for i in range(n):
    xx,dd = inm()
    xd.append((xx,dd))
xd.sort()
x = [xd[i][0] for i in range(n)]

ddprint(xd)
ddprint(x)

r = [i for i in range(n)]
sgt = Segtree(n,0,lambda x,y: max(x,y))
sgt.setary(r)
f = [0]*(n+1)
f[n] = 1
f[n-1] = 2
for i in range(n-2,-1,-1):
    xx,dd = xd[i]
    j = bisect.bisect_left(x,xx+dd)
    k = sgt.query(i,j)
    sgt.set(i,k)
    f[i] = (f[i+1] + f[k+1])%R
    #ddprint(f"i {i} x {xx} d {dd} j {j}")

ddprint(f)
print(f[0])

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 998244353

def ddprint(x):
  if DBG:
    print(x)


class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        return s.querycore(x,y,0,0,s.n)

    # x,y: from query  k: suffix at focus l,r: range for k
    # right ends (y,r) not included

    def querycore(s,x,y,k,l,r):
        if r<=x or y<=l:
            return s.unit
        if x<=l and r<=y:
            return s.ary[k]
        vl = s.querycore(x,y,2*k+1,l,(l+r)//2)
        vr = s.querycore(x,y,2*k+2,(l+r)//2,r)
        return s.oper(vl, vr)

# # # #
import bisect
n = inn()
xd = []
for i in range(n):
    xx,dd = inm()
    xd.append((xx,dd))
xd.sort()
x = [xd[i][0] for i in range(n)]

ddprint(xd)
ddprint(x)

r = [i for i in range(n)]
sgt = Segtree(n,0,lambda x,y: max(x,y))
sgt.setary(r)
for i in range(n-2,-1,-1):
    xx,dd = xd[i]
    j = bisect.bisect_left(x,xx+dd)
    k = sgt.query(i,j)
    sgt.set(i,k)
    #ddprint(f"i {i} x {xx} d {dd} j {j}")

for i in range(n):
    ddprint(sgt.get(i))
    ddprint(sgt.query(i,i+1))

f = [0]*(n+1)
f[n] = 1
f[n-1] = 2
for i in range(n-2,-1,-1):
    xx,dd = xd[i]
    j = bisect.bisect_left(x,xx+dd)
    k = sgt.query(i,j)
    f[i] = (f[i+1] + f[k+1])%R
    #ddprint(f"i {i} x {xx} d {dd} j {j} k {k} fi {f[i]}")

ddprint(f)
print(f[0])

Submission status: Time Limit Exceeded

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

class SegmentTree(object):
 
    def __init__(self, init_array, seg_func=min, seg_func_null=10 ** 9 + 7):
 
        self.seg_func = seg_func
        self.seg_func_null = seg_func_null
        self.n = 1
        while self.n < len(init_array):
            self.n *= 2
        self.dat = [0] * (2 * self.n - 1)
        for i in range(len(init_array)):
            self.dat[self.n - 1 + i] = init_array[i]
        for i in range(self.n - 2, -1, -1):
            self.dat[i] = self.seg_func(self.dat[2 * i + 1], self.dat[2 * i + 2])
 
    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.seg_func(self.dat[k * 2 + 1], self.dat[k * 2 + 2])
 
    def query(self, p, q):
        # [p, q)
        if q <= p:
            return self.seg_func_null
 
        p += self.n - 1
        q += self.n - 2
        res = self.seg_func_null
 
        while q - p > 1:
            if p & 1 == 0:
                res = self.seg_func(res, self.dat[p])
            if q & 1 == 1:
                res = self.seg_func(res, self.dat[q])
                q -= 1
            p = p // 2
            q = (q-1) // 2
        if p == q:
            res = self.seg_func(res, self.dat[p])
        else:
            res = self.seg_func(self.seg_func(res, self.dat[p]), self.dat[q])
 
        return res
 
N = int(input())
X = [0]*N
D = [0]*N
XD = [None]*N
for i in range(N):
    X, D = (int(i) for i in input().split())
    XD[i] = (X, D)
XD.sort()

import bisect
seg = SegmentTree(list(range(N)), max, -1)
L = list(range(N))

for i in range(N)[::-1]:
    x, d = XD[i]
    b = bisect.bisect_left(XD, (x+d-0.5, d))-1
    m = seg.query(i,b+1)
    seg.update(i,m)
    L[i] = m

ans = [0]*N
res = 1
for i in range(N)[::-1]:
    if L[i] == i:
        ans[i] = res
        res *= 2
    else:
        ans[i] = ans[L[i]]
        res += ans[i]
    res %= 998244353
print(res)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree(object):
 
    def __init__(self, init_array, seg_func=min, seg_func_null=10 ** 9 + 7):
 
        self.seg_func = seg_func
        self.seg_func_null = seg_func_null
        self.n = 1
        while self.n < len(init_array):
            self.n *= 2
        self.dat = [0] * (2 * self.n - 1)
        for i in range(len(init_array)):
            self.dat[self.n - 1 + i] = init_array[i]
        for i in range(self.n - 2, -1, -1):
            self.dat[i] = self.seg_func(self.dat[2 * i + 1], self.dat[2 * i + 2])
 
    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.seg_func(self.dat[k * 2 + 1], self.dat[k * 2 + 2])
 
    def query(self, p, q):
        # [p, q)
        if q <= p:
            return self.seg_func_null
 
        p += self.n - 1
        q += self.n - 2
        res = self.seg_func_null
 
        while q - p > 1:
            if p & 1 == 0:
                res = self.seg_func(res, self.dat[p])
            if q & 1 == 1:
                res = self.seg_func(res, self.dat[q])
                q -= 1
            p = p // 2
            q = (q-1) // 2
        if p == q:
            res = self.seg_func(res, self.dat[p])
        else:
            res = self.seg_func(self.seg_func(res, self.dat[p]), self.dat[q])
 
        return res
 
N = int(input())
X = [0]*N
D = [0]*N
XD = [None]*N
for i in range(N):
    X[i], D[i] = (int(i) for i in input().split())
    XD[i] = (X[i], D[i])
XD.sort()
import bisect

seg = SegmentTree(list(range(N)), max, -1)
L = list(range(N))

for i in range(N)[::-1]:
    x, d = XD[i]
    b = bisect.bisect_left(XD, (x+d-0.5, d))-1
    m = seg.query(i,b+1)
    seg.update(i,m)
    L[i] = m

ans = [0]*N
res = 1
for i in range(N)[::-1]:
    if L[i] == i:
        ans[i] = res
        res *= 2
    else:
        ans[i] = ans[L[i]]
        res += ans[i]
    res %= 998244353
print(res)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left


LARGE = 998244353


class SegmentTree(object):

    def __init__(self, init_array, seg_func=min, seg_func_null=10 ** 9 + 7):

        self.seg_func = seg_func
        self.seg_func_null = seg_func_null
        self.n = 1
        while self.n < len(init_array):
            self.n *= 2
        self.dat = [0] * (2 * self.n - 1)
        for i in range(len(init_array)):
            self.dat[self.n - 1 + i] = init_array[i]
        for i in range(self.n - 2, -1, -1):
            self.dat[i] = self.seg_func(self.dat[2 * i + 1], self.dat[2 * i + 2])

    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.seg_func(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, p, q):
        # [p, q)
        if q <= p:
            return self.seg_func_null

        p += self.n - 1
        q += self.n - 2
        res = self.seg_func_null

        while q - p > 1:
            if p & 1 == 0:
                res = self.seg_func(res, self.dat[p])
            if q & 1 == 1:
                res = self.seg_func(res, self.dat[q])
                q -= 1
            p = p // 2
            q = (q-1) // 2
        if p == q:
            res = self.seg_func(res, self.dat[p])
        else:
            res = self.seg_func(self.seg_func(res, self.dat[p]), self.dat[q])

        return res


def solve(n, x_list, d_list):
    reach_right = [0] * n
    reach_right[-1] = n - 1
    # from right
    seg = SegmentTree(list(range(n)), max, -1)
    for i in range(n - 2, -1, -1):
        j = bisect_left(x_list, x_list[i] + d_list[i])
        k = seg.query(i, j)
        seg.update(i, k)
        reach_right[i] = k
    # dp
    dp = [[0] * 2 for _ in range(n)]
    dp[n - 1][0] = 1
    dp[n - 1][1] = 1
    for i in range(n - 2, -1, -1):
        dp[i][0] = (dp[i + 1][0] + dp[i + 1][1]) % LARGE
        j = reach_right[i] + 1
        if j <= n - 1:
            dp[i][1] = (dp[j][0] + dp[j][1]) % LARGE
        else:
            dp[i][1] = 1

    return (dp[0][0] + dp[0][1]) % LARGE


def main():
    n = int(input())
    xd_list = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])
    x_list = [xd[0] for xd in xd_list]
    d_list = [xd[1] for xd in xd_list]
    res = solve(n, x_list, d_list)
    print(res)


def test():
    assert solve(2, [1, 3], [5, 3]) == 3
    assert solve(3, [-1, 3, 6], [10, 3, 5]) == 5
    assert solve(4, [-10, -4, 4, 7], [3, 3, 3, 10]) == 16


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())

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

    robo.sort()

    def on(p, l):
        h = N - 1
        while l <= h:
            m = l + (h - l) // 2
            rp = robo[m][0]
            if rp < p:
                l += 1
            elif rp > p:
                h -= 1
            else:
                return m - 1
        return h

    for i in range(N - 1, -1, -1):
        n = on(robo[i][1], i)
        j = i + 1
        while j <= n:
            n = max(n, robo[j][1])
            j += 1
        robo[i][1] = n

    dp = [0] * (N + 1)
    dp[N] = 1
    for i in range(N - 1, -1, -1):
        n = robo[i][1]
        dp[i] = (dp[i+1] + dp[n+1]) % 998244353

    print(dp[0])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())

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

    robo.sort()

    def on(p, l):
        h = N - 1
        while l <= h:
            m = l + (h - l) // 2
            rp = robo[m][0]
            if rp < p:
                l += 1
            elif rp > p:
                h -= 1
            else:
                return m - 1
        return h

    for i in range(N - 1, -1, -1):
        n = on(robo[i][1], i)
        j = i + 1
        while j <= n:
            n = max(n, robo[j][1])
            j += 1
        robo[i][1] = n

    def search(i, memo):
        if i >= N:
            return 1
        if memo[i] != 0:
            return memo[i]

        n = robo[i][1]

        cnt = search(i + 1, memo)
        if n == i:
            cnt = (cnt * 2) % 998244353
        else:
            cnt = (cnt + search(n + 1, memo)) % 998244353

        memo[i] = cnt
        return cnt

    memo = [0] * N
    print(search(0, memo))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())

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

    robo.sort()

    def on(p):
        l = 0
        h = N - 1
        while l <= h:
            m = l + (h - l) // 2
            rp = robo[m][0]
            if rp < p:
                l += 1
            elif rp > p:
                h -= 1
            else:
                return m - 1
        return h

    for i in range(N - 1, -1, -1):
        n = on(robo[i][1])
        j = i + 1
        while j <= n:
            n = max(n, robo[j][1])
            j += 1
        robo[i][1] = n

    def search(i, memo):
        if i >= N:
            return 1
        if memo[i] != 0:
            return memo[i]

        n = robo[i][1]

        cnt = search(i + 1, memo)
        if n == i:
            cnt = (cnt * 2) % 998244353
        else:
            cnt = (cnt + search(n + 1, memo)) % 998244353

        memo[i] = cnt
        return cnt

    memo = [0] * N
    print(search(0, memo))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())

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

    robo.sort()

    def on(p):
        l = 0
        h = N - 1
        while l <= h:
            m = l + (h - l) // 2
            rp = robo[m][0]
            if rp < p:
                l += 1
            elif rp > p:
                h -= 1
            else:
                return m - 1
        return h

    def search(i, memo):
        if i >= N:
            return 1
        if memo[i] != 0:
            return memo[i]

        n = on(robo[i][1])
        j = i + 1
        while j <= n:
            n = max(n, on(robo[j][1]))
            j += 1

        cnt = search(i + 1, memo)
        if n == i:
            cnt = (cnt * 2) % 998244353
        else:
            cnt = (cnt + search(n + 1, memo)) % 998244353

        memo[i] = cnt
        return cnt

    memo = [0] * N

    print(search(0, memo))


main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
from itertools import accumulate
from functools import reduce
from sys import setrecursionlimit

setrecursionlimit(10000000)

MOD = 998244353

def solve(robots):
    N = len(robots)
    robots.sort()

    parent = [None]*(N+1)

    stack = [(float('inf'),0)]
    for i,(x,d) in enumerate(robots,start=1):
        d += x
        while stack[-1][0] <= x:
            stack.pop()
        parent[i] = stack[-1][1]
        while stack[-1][0] <= d:
            stack.pop()
        stack.append((d,i))

    adj = [list() for _ in range(N+1)]
    for i,p in enumerate(parent[1:],start=1):
        adj[p].append(i)

    rec = lambda i: reduce(lambda a,b:a*b%MOD, (rec(j)+1 for j in adj[i]), 1)

    return rec(0)

if __name__ == '__main__':
    N = int(input())
    robots = [tuple(map(int,input().split())) for _ in range(N)]
    print(solve(robots))