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: Wrong Answer

Solution code:
import sys
from bisect import bisect, bisect_left

def solve():
    input = sys.stdin.readline
    N = int(input())
    R = [[int(i) for i in input().split()] for _ in range(N)]
    R.sort()
    mod = 998244353
    X = [R[i][0] for i in range(N)]
    D = [R[i][1] for i in range(N)]
    Connect = [0] * N
    for i in range(N):
        k = bisect_left(X, X[i] + D[i])
        Connect[i] = k - i - 1
    DP = [0] * N
    DP[N - 1] = 2
    for i in reversed(range(N-1)):
        right = i + Connect[i]
        if right < N - 1: #i番目を動かす
            DP[i] += DP[right + 1]
        else: DP[i] += 1
        DP[i] += DP[i+1] #i番目を動かさない
        DP[i] %= mod
        
    print(DP[0])
    #print(Connect)
    #print(X)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
xd=[list(map(int,input().split())) for _ in range(n)]
xd.sort(key=lambda x:x[0])
aryx=[x for x,d in xd]
mod=998244353
dp=[1]*(n+1)
#dp[n-1]=2
r=list(range(n))
r[n-1]=n-1
from bisect import bisect_left
for i in range(n):
    x,d=xd[n-1-i]
    tmp=bisect_left(aryx,x+d)
    ri=max(r[n-1-i:tmp])
    r[n-1-i]=ri
    dp[n-1-i]=dp[n-1-i+1]+dp[ri+1]
    dp[n-1-i]%=mod
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
from operator import itemgetter
class SegmentTree(object):
    # 検証: https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8434117
    # 参考: https://atcoder.jp/contests/abc014/submissions/3935971
    __slots__ = ["elem_size", "tree", "default", "op", "real_size"]

    def __init__(self, a, default, op):
        self.default = default
        self.op = op
        if hasattr(a, "__iter__"):
            self.real_size = len(a)
            self.elem_size = elem_size = 1 << (self.real_size-1).bit_length()
            self.tree = tree = [default] * (elem_size * 2)
            tree[elem_size:elem_size + self.real_size] = a
            for i in range(elem_size - 1, 0, -1):
                tree[i] = op(tree[i << 1], tree[(i << 1) + 1])
        elif isinstance(a, int):
            self.real_size = a
            self.elem_size = elem_size = 1 << (self.real_size-1).bit_length()
            self.tree = [default] * (elem_size * 2)

    def get_value(self, x: int, y: int) -> int:  # 半開区間
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1
        return result

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        op, tree = self.op, self.tree
        tree[k] = value
        while k > 1:
            k >>= 1
            tree[k] = op(tree[k << 1], tree[(k << 1) + 1])

    def get_one_value(self, i):
        return self.tree[i+self.elem_size]

    def debug(self):
        print(self.tree[self.elem_size:self.elem_size+self.real_size])

def main():
    mod = 998244353
    N = int(sys.stdin.buffer.readline())
    m = map(int, sys.stdin.buffer.read().split())
    XD = list(zip(m, m))
    XD.sort(key=itemgetter(0))
    X, D = zip(*XD)
    seg = SegmentTree(list(range(N)), 0, lambda a,b: a if a>b else b)
    for i, (x, d) in zip(range(N-1,-1,-1), XD[::-1]):
        r = bisect_left(X, x+d, lo=i)
        seg.set_value(i, seg.get_value(i, r))
    D2 = seg.tree[seg.elem_size:seg.elem_size+seg.real_size]
    Q = [0] * N
    ans = 1
    cnt = 1
    for i, d in enumerate(D2):
        ans += cnt
        Q[d] += cnt
        cnt = (cnt + Q[i]) % mod
    print(ans % mod)

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

LI = lambda: list(map(int, input().split()))

N = int(input())
XD = [LI() for _ in range(N)]

MOD = 998244353


class BIT:

    def __init__(self, n):
        self.n = n
        self.dat = [i - 1 for i in range(self.n + 1)]

    def change(self, i, x):
        i += 1
        while i <= self.n:
            self.dat[i] = max(self.dat[i], x)
            i += i & -i

    def max_num(self, i):
        if i == 0:
            return -1
        return max(self.dat[i], self.max_num(i - (i & -i)))


def main():
    XD.sort()
    x = [None] * N
    d = [None] * N
    for i in range(N):
        x[i], d[i] = XD[i]
    
    bit = BIT(N)
    w = [None] * N
    for i in range(N - 1, -1, -1):
        v = x[i] + d[i]
        j = bit.max_num(bisect.bisect_left(x, v))
        w[i] = j - i
        bit.change(i, j)
    
    dp = [None] * (N + 1)
    dp[-1] = 1
    for i in range(N - 1, -1, -1):
        dp[i] = (dp[i + 1] + dp[i + w[i] + 1]) % MOD
    
    ans = dp[0]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys


sys.setrecursionlimit(10**6)


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(next_r_to - 1, r, -1):
            ret = max(ret, search_next_robot(next_r))
        next_robot_list[r] = ret
        return ret

    for n in range(N - 1, - 1, - 1):
        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: Time Limit Exceeded

Solution code:
import bisect
import sys


sys.setrecursionlimit(10**6)


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

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

MOD = 998244353

def init(G, robots, fs, p):
    q = p+1
    while q < len(robots) and robots[q][0] < robots[p][0] + robots[p][1]:
        if fs[q]:
            G[p].append(q)
            fs[q] = False
            init(G, robots, fs, q)
        q += 1

def calc(G, p, fs):
    fs[p] = False
    if len(G[p]) == 0:
        return 2
    tmp = 1
    for v in G[p]:
        tmp *= calc(G, v, fs)
        tmp %= MOD
    tmp += 1
    return tmp

def main():
    n = int(input())
    robots = [list(map(int, input().split())) for _ in range(n)]
    G = [[] for _ in range(n)]
    robots.sort(key=lambda x: x[0])
    fs = [True]*n
    for i in range(n):
        if fs[i]:
            fs[i] = False
            init(G, robots, fs, i)
    fs = [True]*n
    ans = 1
    for i in range(n):
        if fs[i]:
            ans *= calc(G, i, fs)
            ans %= MOD
    print(ans % MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

    print(dp[0])


solve()

Submission status: Time Limit Exceeded

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

XD=[tuple(map(int,input().split()))for i in range(n)]
XD.sort()
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)
P=[0]*n
t=0
for x,d in XD[::-1]:
    idx=n-1-t
    t+=1
    p=X[idx]
    p=query_max(idx,p)
    update_max(idx,p)
    P[idx]=p
for i in range(n-1,-1,-1):
    combs[i]=(combs[P[i]+1]+combs[i+1])%mod
print(combs[0])

Submission status: Time Limit Exceeded

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

XD=[tuple(map(int,input().split()))for i in range(n)]
XD.sort()
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 XD[::-1]:
    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: Time Limit Exceeded

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


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

import bisect

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

Submission status: Time Limit Exceeded

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

from array import *
ide_ele_max = 0
num_max =2**(segSize-1).bit_length()
seg_max=[ide_ele_max]*2*num_max
seg_max=array("i",seg_max)
mod=998244353


XD=[tuple(map(int,input().split()))for i in range(n)]
XD.sort()
X=[x for x,d in XD]
X.append(XD[-1][0])
X=array("i",X)

import bisect

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

Submission status: Time Limit Exceeded

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

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

import bisect

init_max(list(range(segSize)))
update_max(n,n)
combs=[1]*(n+2)
t=0
for x,d in XD[-2::-1]:
    idx=n-1-t
    t+=1
    p=bisect.bisect_right(XD,(x+d-1,10**9+1))
    p=query_max(idx,p)
    update_max(idx,p)
    combs[idx]=(combs[p+1]+combs[idx+1])%mod
print(combs[0])

Submission status: Time Limit Exceeded

Solution code:
import bisect

MOD = 998244353
n = int(input())
A = []

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

A.sort()

k = 1  # number of leafs
while k < n:
    k *= 2

D = [-1] * (2*k-1)


# ask k-the node which corresponds to [left,right)
# "What is the value of [a,b)?"
def query(k, a, b, left, right):
    if b <= left or right <= a:
        return -1
    elif a <= left and right <= b:
        return D[k]
    else:
        c1 = query(2*k+1, a, b, left, (left+right)//2)
        c2 = query(2*k+2, a, b, (left+right)//2, right)
        return max(c1, c2)


def change(k, x):
    D[k] = x
    i = (k-1)//2
    while i >= 0:
        D[i] = max(D[2*i+1], D[2*i+2])
        i = (i-1)//2


# initialize
for i in range(n-1, -1, -1):
    ter = A[i][0] + A[i][1]
    left = i
    right = bisect.bisect_left(A, [ter, 0])
    d = query(0, left, right, 0, k)
    if d == -1:
        change(k-1+i, i)
    else:
        change(k-1+i, d)

for i in range(k-2, -1, -1):
    D[i] = max(D[2*i+1], D[2*i+2])

DP = [0] * n
DP_plus = [0] * n

DP[n-1] = 2
DP_plus[n-1] = 1


for i in range(n-2, -1, -1):
    in_tree = k-1+i
    if D[in_tree] == i:  # affect no other robots
        DP_plus[i] = DP[i+1]
        DP[i] = (2 * DP_plus[i]) % MOD
    else:
        DP_plus[i] = DP_plus[D[in_tree]]
        DP[i] = DP_plus[i] + DP[i+1] % MOD

print(DP[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        # A : array of monoid (M, dot, unit)
        # (S, compose, identity) : sub monoid of End(M)
        # compose : (f, g) -> fg (f, g in S)
        # act : (f, x) -> f(x) (f in S, x in M)
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

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

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

    # A[i] <- f(A[i]) for all i in [l, r)
    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        # propagation isn't necessary if S is commutative
        self._descend(l)
        self._descend(r - 1)
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._ascend(l0)
        self._ascend(r0 - 1)

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

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

    # range update, range sum
    A = [0] * n
    A[-1] = 1

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

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

    tree = LazySegmentTree(A, add, 0, compose, INF, act)
    for i in range(n - 2, -1, -1):

        tree.range_act(i, i + 1, (tree.sum(i + 1, n) + 1) % MOD) # pointwise update
        x, d = XD[i]
        if XD[-1][0] < x + d:
            j = n
        elif XD[0][0] >= x + d:
            j = 0
        else:
            l, r = 0, n - 1
            while r - l > 1:
                m = (l + r) // 2
                if XD[m][0] < x + d:
                    l = m
                else:
                    r = m
            j = r
        tree.range_act(i + 1, j, 0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        # A : array of monoid (M, dot, unit)
        # (S, compose, identity) : sub monoid of End(M)
        # compose : (f, g) -> fg (f, g in S)
        # act : (f, x) -> f(x) (f in S, x in M)
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

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

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

    # A[i] <- f(A[i]) for all i in [l, r)
    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        # propagation isn't necessary if S is commutative
        self._descend(l)
        self._descend(r - 1)
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._ascend(l0)
        self._ascend(r0 - 1)

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

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

    # range update, range sum
    A = [0] * n
    A[-1] = 1

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

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

    tree = LazySegmentTree(A, add, 0, compose, INF, act)
    for i in range(n - 2, -1, -1):

        tree.range_act(i, i + 1, (tree.sum(i + 1, n) + 1) % MOD) # pointwise update
        x, d = XD[i]
        if X[-1] < x + d:
            j = n
        elif X[0] >= x + d:
            j = 0
        else:
            l, r = 0, n - 1
            while r - l > 1:
                m = (l + r) // 2
                if X[m] < x + d:
                    l = m
                else:
                    r = m
            j = r
        tree.range_act(i + 1, j, 0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        # A : array of monoid (M, dot, unit)
        # (S, compose, identity) : sub monoid of End(M)
        # compose : (f, g) -> fg (f, g in S)
        # act : (f, x) -> f(x) (f in S, x in M)
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

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

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

    # A[i] <- f(A[i]) for all i in [l, r)
    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        # propagation isn't necessary if S is commutative
        self._descend(l)
        self._descend(r - 1)
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._ascend(l0)
        self._ascend(r0 - 1)

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

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

    # range update, range sum
    A = [(0, 1) for _ in range(n)]
    A[n - 1] = (1, 1)
    dot = lambda a0, a1: (a0[0] + a1[0], a0[1] + a1[1])
    def compose(f, g):
        if f is None:
            return g
        if g is None:
            return f
        return f

    def act(f, a):
        if f is None:
            return a
        x, y = a
        return (f * y, y)

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

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