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:
import sys
sys.setrecursionlimit(10**6)
from operator import itemgetter
import bisect
def main():
    input = sys.stdin.readline
    N = int(input())
    XD = [tuple(map(int, input().split())) for _ in range(N)]
    MOD = 998244353

    XD.sort(key=itemgetter(0))
    X = [xd[0] for xd in XD]

    E = [[] for _ in range(N)]
    j = 0
    for i in range(N):
        x, d = XD[i]
        j = bisect.bisect_left(X, x+d, i)
        for k in range(i+1, j):
            E[i].append(k)

    used = [False] * N
    def f(i):
        result = Mint(1, MOD)
        used[i] = True
        for to in E[i]:
            if used[to]: continue
            result *= f(to)
        return result + 1

    ans = Mint(1, MOD)
    for i in range(N):
        if used[i]: continue
        ans *= f(i)
    print(ans)


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

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

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

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

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


C = [i for i in range(n)]

#####segfunc######
#def segfunc(x,y):
#    return 

def segfunc(a,b):
  return max(a, b)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(C)
for i in range(n):
  x, d = XD[n-1-i]
  t = bisect.bisect_left(X, x+d)
  update(n-1-i, max(t, 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 = query(n-1-i, m)
  dp[n-1-i] = dp[n-i] + dp[t]
  dp[n-1-i] %= MOD
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num =2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [self.ide_ele]*2*self.num
        self.segfunc = segfunc
        
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1] = init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = segfunc(self.seg[2*i+1], self.seg[2*i+2]) 
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res
    
### 使い方 ##
N = int(input())


A = [-1]*N
INF = 10**15
ide_ele = -1
SEG = SegTree(A,ide_ele,max)


LIST = []
XX = []
mod = 998244353

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

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

GOTO = [i for i in range(1,N+1)]
for i in range(N):
	SEG.update(i,i+1)
#print(LIST)
import bisect
for i in range(N-1):
    j = N-2-i
    Xj = LIST[j][0]
    Dj = LIST[j][1]
    Nj = bisect.bisect_right(XX, Xj+Dj-1)
    #print(Xj,Dj,j+1,Nj)
    NEXT = SEG.query(j+1,Nj)
    if NEXT != -1:
        GOTO[j] = NEXT
        SEG.update(j,NEXT)
    
S = [-1]*(N+1)
S[N] = 1

#print(LIST)
#print(GOTO)
for i in range(N):
    j = N-1-i
    S[j] = S[j+1] + S[GOTO[j]]
    S[j] %= mod

print(S[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
from operator import itemgetter


class SegTreeMax:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    def initialize(self, arr):
        for i, v in enumerate(arr, start=self.offset):
            self.tree[i] = v
        for i in range(self.offset - 1, 0, -1):
            j = i << 1
            self.tree[i] = max(self.tree[j], self.tree[j + 1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y >= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_max(self, a, b):
        """
        [a, b)の最大値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = max(result, self.tree[r - 1])
            if l & 1:
                result = max(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


n, *xd = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
xd = sorted(zip(xd[0::2], xd[1::2]))
xxx = list(map(itemgetter(0), xd))
ans = [0] * (n + 1)
skip = list(range(1, n + 1))
ans[n] = 1
sgt = SegTreeMax(n + 1, 0)
sgt.initialize(list(range(1, n + 2)))
for i in range(n - 1, -1, -1):
    x, d = xd[i]
    r = x + d
    j = bisect_left(xxx, r)
    k = sgt.get_max(i, j)
    ans[i] = (ans[i + 1] + ans[k]) % MOD
    sgt.update(i, k)
print(ans[0])

Submission status: Time Limit Exceeded

Solution code:

class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        #for i in range(self.sz):
        #    self.node[i+self.n-1] = L[i]

        #for i in range(self.n-2,-1,-1):
        #    self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            print('ERROR: the indice are wrong.')
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        #left
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        #right
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res
    
import sys
from operator import itemgetter
sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

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

    ST = SegmentTree([0]*N,max,0)

    M = [list(map(int,input().split())) for i in range(N)]

    M.sort(key=itemgetter(0))

    def bisect(l,v):
        r = N-1
        if M[r][0] < v:
            return r
        while r-l>1:
            if M[(r+l)//2][0]<v:
                l = (r+l)//2
            else:
                r = (r+l)//2
        return l


    for i in range(N):
        j = N-i-1
        index = bisect(j,M[j][0]+M[j][1])
        if N-index-1 < i:
            ST.substitute(j,ST.get(j,index))
        else:
            ST.substitute(j,j)
            

    DP = [0]*(N+1)
    DP[0] = 1
    mod = 998244353
    #print(M)
    for i in range(N):
        #print(DP)
        index = ST.get_one(N-i-1)
        j = N-1-index
        DP[i+1] = DP[j]+DP[i]

    print(DP[N]%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    XD.sort(key=itemgetter(0))
    X = [xd[0] for xd in XD]
    D = [xd[1] for xd in XD]

    E = [[] for _ in range(N)]
    for i in range(N):
        x, d = X[i], D[i]
        j = bisect.bisect_left(X, x+d)
        for k in range(i+1, j):
            E[i].append(k)

    used = [False] * N
    def f(i):
        result = Mint(1, MOD)
        used[i] = True
        for to in E[i]:
            if used[to]: continue
            result *= f(to)
        return result + 1

    ans = Mint(1, MOD)
    for i in range(N):
        if used[i]: continue
        t = f(i)
        ans *= t
    print(ans)


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

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

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

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

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        #for i in range(self.sz):
        #    self.node[i+self.n-1] = L[i]

        #for i in range(self.n-2,-1,-1):
        #    self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            print('ERROR: the indice are wrong.')
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        #left
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        #right
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res
    
import sys
from operator import itemgetter
sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

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

    ST = SegmentTree([0]*N,max,0)

    M = [list(map(int,input().split())) for i in range(N)]

    M.sort(key=itemgetter(0))

    def bisect(l,v):
        r = N-1
        if M[r][0] < v:
            return r
        while r-l>1:
            if M[(r+l)//2][0]<v:
                l = (r+l)//2
            else:
                r = (r+l)//2
        return l


    for i in range(N):
        j = N-i-1
        index = bisect(j,M[j][0]+M[j][1])
        if N-index-1 < i:
            ST.substitute(j,ST.get(j,index))
        else:
            ST.substitute(j,j)
            

    DP = [0]*(N+1)
    DP[0] = 1
    mod = 998244353
    #print(M)
    for i in range(N):
        #print(DP)
        index = ST.get_one(N-i-1)
        j = N-1-index
        DP[i+1] = DP[j]+DP[i]
        DP[i+1] %= mod

    print(DP[N])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        #for i in range(self.sz):
        #    self.node[i+self.n-1] = L[i]

        #for i in range(self.n-2,-1,-1):
        #    self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            print('ERROR: the indice are wrong.')
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        #left
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        #right
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res
    
import sys
from operator import itemgetter
sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

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

    ST = SegmentTree([0]*N,max,0)

    M = [list(map(int,input().split())) for i in range(N)]

    M.sort(key=itemgetter(0))

    def bisect(l,v):
        r = N-1
        if M[r][0] < v:
            return r
        while r-l>1:
            if M[(r+l)//2][0]<v:
                l = (r+l)//2
            else:
                r = (r+l)//2
        return l


    for i in range(N):
        j = N-i-1
        index = bisect(j,M[j][0]+M[j][1])
        if N-index-1 < i:
            ST.substitute(j,ST.get(j,index))
        else:
            ST.substitute(j,j)
            

    DP = [1]
    mod = 998244353
    #print(M)
    for i in range(N):
        #print(DP)
        index = ST.get_one(N-i-1)
        j = N-1-index
        DP.append((DP[j]+DP[i])%mod)

    print(DP[N])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        #for i in range(self.sz):
        #    self.node[i+self.n-1] = L[i]

        #for i in range(self.n-2,-1,-1):
        #    self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            print('ERROR: the indice are wrong.')
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        #left
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        #right
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res
    
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

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

    ST = SegmentTree([0]*N,max,0)

    M = [list(map(int,input().split())) for i in range(N)]

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

    def bisect(l,v):
        r = N-1
        if M[r][0] < v:
            return r
        while r-l>1:
            if M[(r+l)//2][0]<v:
                l = (r+l)//2
            else:
                r = (r+l)//2
        return l


    for i in range(N):
        j = N-i-1
        index = bisect(j,M[j][0]+M[j][1])
        if N-index-1 < i:
            ST.substitute(j,ST.get(j,index))
        else:
            ST.substitute(j,j)
            

    DP = [1]
    mod = 998244353
    #print(M)
    for i in range(N):
        #print(DP)
        index = ST.get_one(N-i-1)
        j = N-1-index
        DP.append((DP[j]+DP[i])%mod)

    print(DP[N])
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            print('ERROR: the indice are wrong.')
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        #left
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        #right
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res
    

N = int(input())

ST = SegmentTree(range(N),max,0)

M = [list(map(int,input().split())) for i in range(N)]

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

def bisect(l,v):
    r = N-1
    if M[r][0] < v:
        return r
    while r-l>1:
        if M[(r+l)//2][0]<v:
            l = (r+l)//2
        else:
            r = (r+l)//2
    return l


for i in range(N):
    j = N-i-1
    index = bisect(j,M[j][0]+M[j][1])
    if N-index-1 < i:
        ST.substitute(j,ST.get(j,index))
        

DP = [1]
mod = 998244353
#print(M)
for i in range(N):
    #print(DP)
    index = ST.get_one(N-i-1)
    j = N-1-index
    DP.append((DP[j]+DP[i])%mod)

print(DP[N])