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:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
import sys
sys.setrecursionlimit(10**6)
mod=998244353
n=i1() 
d=[]
for i in range(n):
  d.append(i2())
d=sorted(d)
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
r=[]

for i in range(n):
 r.append(bisect.bisect_left(dx,dx[i]+dd[i]))
class tt():
 def __init__(self):
  self.dt=[0 for i in range(n)]
 def ddd(self,i):
  x=r[i]-1
  for k in range(i+1,r[i]):
      if self.dt[k]==0:
         x=max(x,self.ddd(k))
      else:
         x=max(x,self.dt[k])
  self.dt[i]=x
  return x
ss=tt()
for i in range(n):
  if ss.dt[i]==0:
    ss.ddd(i)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=(dp[i+1]+dp[ss.dt[i]+1])%mod
  
  
print(dp[0]%mod)

Submission status: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
import sys
sys.setrecursionlimit(10**6)
mod=998244353
n=i1() 
d=[]
for i in range(n):
  d.append(i2())
d=sorted(d)
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
r=[]

for i in range(n):
 r.append(bisect.bisect_left(dx,dx[i]+dd[i]))
class tt():
 def __init__(self):
  self.dt=[0 for i in range(n)]
 def ddd(self,i):
  x=r[i]-1
  for k in range(i+1,r[i]):
      if self.dt[k]==0:
         x=max(x,self.ddd(k))
      else:
         x=max(x,self.dt[k])
  self.dt[i]=x
  return x
ss=tt()
for i in range(n):
  if ss.dt[i]==0:
    ss.ddd(i)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[ss.dt[i]+1]
  dp[i]%=mod
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
mod=998244353
n=int(input())
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)//2
    if t[i*2+1]>t[i*2+2]:t[i]=t[i*2+1]
    else:t[i]=t[i*2+2]
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         if L<t[a]:L = t[a]
      if b&1==0:
         b-=1
         if R<t[b]:R = t[b]
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append([int(i) for i in input().split()])
d=sorted(d)
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 j=bisect.bisect_left(dx,dx[i]+dd[i])
 tt=qr(i,j)
 if j-1>tt:ud(i,j-1)
 else:ud(i,tt)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import bisect
mod=998244353
n=int(input())
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=max(t[i*2+1],t[i*2+2]) 
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         L = max(L, t[a])
      if b&1==0:
         b-=1
         R = max(t[b], R)
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append([int(i) for i in input().split()])
d=sorted(d)
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 j=bisect.bisect_left(dx,dx[i]+dd[i])
 tt=qr(i,j)
 ud(i,max(j-1,tt))
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
class SegmentTreeMax():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=max(ret,self.tree[r])
      r=(r-1)//2
      ret=max(ret,self.tree[l])
      l=(l+1)//2
    return ret

mod=998244353
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda x:x[0])
st=SegmentTreeMax(n,0)
ranges=[]
for i in range(n):
  x=arr[i][0]+arr[i][1]
  l=-1
  r=n
  while r-l!=1:
    mid=(l+r)//2
    if arr[mid][0]>=x:
      r=mid
    else:
      l=mid
  ranges.append(l)
  st.update(i,r)
for i in range(n-1,-1,-1):
  ranges[i]=st.query(i,ranges[i])
  st.update(i,ranges[i])
dp=[0]*(n+1)
dp[-1]=1
for i in range(n-1,-1,-1):
  j=ranges[i]
  dp[i]=dp[i+1]+dp[j]
  dp[i]%=mod
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect, bisect_left

class SquareDiv(): #区間の最大値を求める
    def __init__(self, N, V):
        k = 1
        while k ** 2 < N: k += 1
        self.array = [V] * k
        self.size = k
        self.indivisual = [V] * N

    def update(self, i, v): #i番目をvに更新する
        self.indivisual[i] = v
        self.array[i // self.size] = max(self.array[i // self.size], v)

    def search(self, left, right): #[left, right]の最大値を求める
        lk, rk = left // self.size, right // self.size
        if lk == rk:
            maxN = 0
            for i in range(left, right + 1): maxN = max(maxN, self.indivisual[i])
            return maxN
        else:
            maxN = self.search(left, (lk + 1) * self.size - 1)
            for k in range(lk + 1, rk): maxN = max(maxN, self.array[k])
            maxN = max(maxN, self.search(rk * self.size, right))
            return maxN

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)]
    Connect = SquareDiv(N, 0)
    DP = dict()
    DP[N] = 1
    for i in reversed(range(N)):
        right = max(i, Connect.search(i, bisect_left(X, sum(R[i])) - 1))
        Connect.update(i, right)
        DP[i] = (DP[right + 1] + DP[i + 1]) % mod
    print(DP[0])
    

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect, bisect_left

class RMQ(): #range minimum query
    def __init__(self, N, V): #create segment tree with initial value V
        self.size = 1
        while self.size < N:
            self.size <<= 1
        self.tree = [V] * (2 * self.size - 1)
    
    def update(self, i, a): #update cell i by value a
        now = self.size - 1 + i 
        self.tree[now] = a
        while now > 0:
            now = (now - 1) // 2
            self.tree[now] = max(self.tree[2 * now + 1], self.tree[2 * now + 2])

    def search(self, lower, higher, lbound, hbound, pos): #search minimum value of [lower, higher) init: lbound = 0, hbound = self.size, pos = 0
        if higher <= lbound or hbound <= lower: return 0
        if lower <= lbound and hbound <= higher: return self.tree[pos]
        else:
            left = self.search(lower, higher, lbound, (lbound + hbound) // 2, 2 * pos + 1)
            right = self.search(lower, higher, (lbound + hbound) // 2, hbound, 2 * pos + 2)
            return max(left, right)

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)]
    Connect = RMQ(N, 0)
    DP = [1] * (N + 1)
    for i in reversed(range(N)):
        right = max(i, Connect.search(i, bisect_left(X, sum(R[i])), 0, Connect.size, 0))
        Connect.update(i, right)
        DP[i] = (DP[right + 1] + DP[i + 1]) % mod
    print(DP[0])
    

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect, bisect_left

class LST(): #遅延セグ木
    def __init__(self, N, V): #create segment tree with initial value V
        self.size = 1
        while self.size < N: self.size <<= 1
        self.tree = [V] * (2 * self.size - 1)
        self.changed = [0] * (2 * self.size - 1) 

    def eval(self, i, left, right): #遅延評価, [left, right)
        t = self.changed[i]
        if t > 0:
            self.tree[i] = t
            if right - left > 1:
                self.changed[2 * i + 1] = t 
                self.changed[2 * i + 2] = t
            self.changed[i] = -1
    
    def update(self, v, lower, higher, lbound, hbound, pos): #update cell i by value a, pos = 0  
        self.eval(pos, lbound, hbound)    
        if higher <= lbound or hbound <= lower: return
        if lower <= lbound and hbound <= higher: 
            self.tree[pos] = v
            if hbound - lbound > 1: self.changed[2 * pos + 1] = self.changed[2 * pos + 2] = v
        else:
            self.update(v, lower, higher, lbound, (lbound + hbound) // 2, 2 * pos + 1)
            self.update(v, lower, higher, (lbound + hbound) // 2, hbound, 2 * pos + 2)
            self.tree[pos] = max(self.tree[2 * pos + 1], self.tree[2 * pos + 2])

    def search(self, lower, higher, lbound, hbound, pos): #search minimum value of [lower, higher) init: lbound = 0, hbound = self.size, pos = 0
        if higher <= lbound or hbound <= lower: return 0

        self.eval(pos, lbound, hbound)
        if lower <= lbound and hbound <= higher: return self.tree[pos]
        else:
            left = self.search(lower, higher, lbound, (lbound + hbound) // 2, 2 * pos + 1)
            right = self.search(lower, higher, (lbound + hbound) // 2, hbound, 2 * pos + 2)
            return max(left, right)

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 = LST(N, 0)
    DP = [1] * (N + 1)
    for i in reversed(range(N)):
        right = max(i, Connect.search(i, bisect_left(X, X[i] + D[i]), 0, Connect.size, 0))
        Connect.update(right, i, i+1, 0, Connect.size, 0)
        DP[i] = (DP[right + 1] + DP[i + 1]) % mod
    print(DP[0])

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#reference Segment-Tree code from:https://ikatakos.com/pot/programming_algorithm/data_structure/segment_tree

def bisect(pos):
  l=-1
  r=n
  while r-l!=1:
    mid=(l+r)//2
    if arr[mid][0]>=pos:
      r=mid
    else:
      l=mid
  return r

mod=998244353
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda x:x[0])
poss=[]
for i in range(n):
  poss.append(bisect(arr[i][0]+arr[i][1]))
poss.append(n)

offset=2**((n-1).bit_length())
st=[0]*(2*offset)

def update(pos,x):
  pos+=offset
  st[pos]=x
  while pos>1:
    y=st[pos^1]
    if x<=y:
      break
    pos>>=1
    st[pos]=x

def get_max(l,r):
  ret=0
  l+=offset
  r+=offset
  while l<r:
    if r&1:
      ret=max(ret,st[r-1])
    if l&1:
      ret=max(ret,st[l])
      l+=1
    l>>=1
    r>>=1
  return ret

for i in range(n):
  update(i,poss[i])
for i in range(n-1,-1,-1):
  poss[i]=get_max(i,poss[i])
  update(i,poss[i])

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N = int(input())
XD = [[int(i) for i in input().split()] for _ in range(N)]

mod = 998244353

XD.sort()

class SegTree:
  def __init__(self, n, v, f) :
    i = 1
    while i < n : 
      i <<= 1
    self.n = i
    self.v = v
    self.f = f
    self.tree = [v] * (i << 1)

  def update(self, i, x) :
    i += self.n - 1
    self.tree[i] = x
    while i > 0 :
      i = (i - 1) // 2
      self.tree[i] = self.f(self.tree[i * 2 + 1], self.tree[i * 2 + 2])

  # [l, r)
  def query(self, l, r) :
    l = l + self.n
    r = r + self.n
    s = self.v
    while l < r :
      if r & 1 :
        r -= 1
        s = self.f(s, self.tree[r - 1])
      if l & 1 :
        s = self.f(s, self.tree[l - 1])
        l += 1
      l >>= 1
      r >>= 1
    return s

INF = 1 << 60
ST = SegTree(N, -INF, max)

xs = [x for x, _ in XD]
for i in range(N - 1, -1, -1) :
  x, d = XD[i]
  j = bisect_left(xs, x + d)
  ST.update(i, max(i, ST.query(i, j)))

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

for i in range(N) :
  dp[i] += dp[i - 1]
  dp[i] %= mod
  j = ST.query(i, i + 1)
  dp[j] += dp[i - 1]
  dp[j] %= mod

print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from heapq import heappush, heappop

N = int(input())
XD = [[int(i) for i in input().split()] for _ in range(N)]

mod = 998244353

XD.sort()

class SegTree:
  def __init__(self, n, v, f) :
    i = 1
    while i < n : 
      i <<= 1
    self.n = i
    self.v = v
    self.f = f
    self.tree = [v] * (i << 1)

  def update(self, i, x) :
    i += self.n - 1
    self.tree[i] = x
    while i > 0 :
      i = (i - 1) // 2
      self.tree[i] = self.f(self.tree[i * 2 + 1], self.tree[i * 2 + 2])

  # [l, r)
  def query(self, l, r) :
    l = l + self.n
    r = r + self.n
    s = self.v
    while l < r :
      if r & 1 :
        r -= 1
        s = self.f(s, self.tree[r - 1])
      if l & 1 :
        s = self.f(s, self.tree[l - 1])
        l += 1
      l >>= 1
      r >>= 1
    return s

INF = 1 << 60
ST = SegTree(N, -INF, max)

xs = [x for x, _ in XD]
dest = [0] * N
for i in range(N - 1, -1, -1) :
  x, d = XD[i]
  j = bisect_left(xs, x + d) - 1
  if i == j :
    dest[i] = x + d
  else :
    dest[i] = ST.query(i, j + 1)
  ST.update(i, dest[i])

ret = 1
q = []
for i, (x, d) in enumerate(XD) :
  while q and q[0][0] <= x :
    ret += heappop(q)[1]
    ret %= mod
  heappush(q, (dest[i], ret))

while q :
  ret += heappop(q)[1]
  ret %= mod

print(ret % mod)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 1:
            i = i // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[1]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res

def main():
    n = I()
    xd = sorted([LI() for _ in range(n)])
    xa = [x for x,_ in xd] + [inf]
    r = [0] * n + [1]
    def f(a,b):
        if a > b:
            return a
        return b
    seg = Seg(n+1,0,f)
    for i in range(n-1,-1,-1):
        x,d = xd[i]
        xi = bisect.bisect_left(xa, x+d)
        qi = seg.query(i,xi)
        if qi > xi:
            xi = qi
        seg.update(i,xi)
        r[i] = (r[i+1] + r[xi]) % mod2

    return r[0]


print(main())

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
from bisect import bisect_left

#普通のセグ木
'''
org: 配列[list]
func: 関数 (min,max,sumなど)
unit: 初期値
'''
class SegmentTree:
    def __init__(self, orig, func, unit):
        _len = len(orig)
        self.func = func
        self.size = 1 << (_len - 1).bit_length()
        self.tree = [unit] * self.size + orig + [unit] * (self.size - _len)
        self.unit = unit

        for i in range(self.size - 1, 0, -1):
            self.tree[i] = func(self.tree[i * 2], self.tree[i * 2 + 1])

    def update(self, i, v):
        i += self.size
        self.tree[i] = v
        while i:
            i //= 2
            self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])
    # l <= x <r
    def find(self, l, r):
        l += self.size
        r += self.size
        ret = self.unit
        while l < r:
            if l & 1:
                ret = self.func(ret, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.func(ret, self.tree[r])
            l //= 2
            r //= 2
        return ret

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
xlis = []
dubl = []
for i in range(n):
    x,d = mi()
    xlis.append(x)
    dubl.append((x,d))
xlis.sort()
dubl.sort()
seg = SegmentTree([0]*n,max,0)
acum = [0] * n
ans = [0] *n
ans[n-1] = 2
mod = 998244353
for i in reversed(range(n)):
    xd = bisect_left(xlis,xlis[i]+dubl[i][1]) -1
    ima = max(seg.find(i,xd+1),xd)
    acum[i] = ima 
    seg.update(i,ima)

for i in reversed(range(n-1)):
    if acum[i] == n-1:
        ans[i] = (ans[i+1] +1) % mod
    else:
        ans[i] = (ans[i+1] + ans[acum[i] +1]) % mod
print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left

MOD = 998244353
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, values, merge_func=min, default=float("inf")):
        n = len(values)
        self.size = 1
        self.height = 1
        self.default = default
        self.merge = merge_func
        while self.size < n:
            self.size *= 2
            self.height += 1
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [self.default] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])

    def get(self, index):
        return self.tree[self.size + index]

    def update(self, index, value):
        index += self.size
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.merge(
                self.tree[index*2], self.tree[index*2+1])

    # query segmentation value of [a, b)
    def query(self, a, b):
        stack = [None] * self.height * 2
        idx = 0
        stack[idx] = (1, 0, self.size)
        ret = self.default
        while idx >= 0:
            k, l, r = stack[idx]
            idx -= 1
            if r <= a or b <= l:
                continue
            if a <= l and r <= b:
                ret = self.merge(ret, self.tree[k])
            else:
                stack[idx+1] = (k*2, l, (l+r)//2)
                stack[idx+2] = (k*2+1, (l+r)//2, r)
                idx += 2
        return ret


def main():
    N = int(input())
    robo = [None] * N
    for i in range(N):
        robo[i] = tuple(map(int, input().split()))
    robo.sort()
    pos = [x[0] for x in robo]
    dst = [x[0] + x[1] for x in robo]
    rmq = SegmentTree(dst, max, -float("inf"))
    for i in range(N-1)[::-1]:
        dst[i] = rmq.query(i, bisect_left(pos, dst[i]))
        rmq.update(i, dst[i])

    dp = [0] * (N+1)
    dp[0] = 1
    for i in range(N):
        x, d = robo[N-1-i]
        to = N - bisect_left(pos, dst[N-1-i])
        dp[i+1] = (dp[i] + dp[to]) % MOD
    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left

MOD = 998244353
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, values, merge_func=min, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        self.merge = merge_func
        while self.size < n:
            self.size *= 2
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [self.default] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])

    def get(self, index):
        return self.tree[self.size + index]

    def update(self, index, value):
        index += self.size
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.merge(
                self.tree[index*2], self.tree[index*2+1])

    # query segmentation value of [a, b)
    def query(self, a, b):
        q = [(1, 0, self.size)]
        ret = self.default
        while len(q):
            k, l, r = q.pop()
            if r <= a or b <= l:
                continue
            if a <= l and r <= b:
                ret = self.merge(ret, self.tree[k])
            else:
                q.append((k*2, l, (l+r)//2))
                q.append((k*2+1, (l+r)//2, r))
        return ret


def main():
    N = int(input())
    robo = [None] * N
    for i in range(N):
        robo[i] = tuple(map(int, input().split()))
    robo.sort()
    pos = [x[0] for x in robo]
    dst = [x[0] + x[1] for x in robo]
    rmq = SegmentTree(dst, max, -float("inf"))
    for i in range(N-1)[::-1]:
        dst[i] = rmq.query(i, bisect_left(pos, dst[i]))
        rmq.update(i, dst[i])

    dp = [0] * (N+1)
    dp[0] = 1
    for i in range(N):
        x, d = robo[N-1-i]
        to = N - bisect_left(pos, dst[N-1-i])
        dp[i+1] = (dp[i] + dp[to]) % MOD
    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect, bisect_left

class RMQ(): #range minimum query
    def __init__(self, N, V): #create segment tree with initial value V
        d, k = 1, 0
        while d < N:
            d <<= 1
            k += 1
        self.tree = [V] * (2 * d - 1)
        self.size = d
    
    def update(self, i, a): #update cell i by value a
        now = self.size - 1 + i 
        self.tree[now] = a
        while now > 0:
            now = (now - 1) // 2
            self.tree[now] = max(self.tree[2 * now + 1], self.tree[2 * now + 2])

    def search(self, lower, higher, lbound, hbound, pos): #search minimum value of [lower, higher) init: lbound = 0, hbound = self.size, pos = 0
        if higher <= lbound or hbound <= lower: return 0
        if lower <= lbound and hbound <= higher: return self.tree[pos]
        else:
            left = self.search(lower, higher, lbound, (lbound + hbound) // 2, 2 * pos + 1)
            right = self.search(lower, higher, (lbound + hbound) // 2, hbound, 2 * pos + 2)
            return max(left, right)

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 = RMQ(N, 0)
    DP = [1] * (N + 1)
    for i in reversed(range(N)):
        right = max(i, Connect.search(i, bisect_left(X, X[i] + D[i]), 0, Connect.size, 0))
        Connect.update(i, right)
        DP[i] = (DP[right + 1] + DP[i + 1]) % mod
    print(DP[0])
    

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect, bisect_left

class RMQ(): #range minimum query
    def __init__(self, N, V): #create segment tree with initial value V
        d, k = 1, 0
        while d < N:
            d <<= 1
            k += 1
        self.tree = [V for _ in range(2 * d - 1)]
        self.size = d
    
    def update(self, i, a): #update cell i by value a
        now = self.size - 1 + i 
        self.tree[now] = a
        while now > 0:
            now = (now - 1) // 2
            self.tree[now] = max(self.tree[2 * now + 1], self.tree[2 * now + 2])
        #print(self.tree)

    def search(self, lower, higher, lbound, hbound, pos): #search minimum value of [lower, higher) init: lbound = 0, hbound = self.size, pos = 0
        if higher <= lbound or hbound <= lower: return 0
        if lower <= lbound and hbound <= higher: return self.tree[pos]
        else:
            left = self.search(lower, higher, lbound, (lbound + hbound) // 2, 2 * pos + 1)
            right = self.search(lower, higher, (lbound + hbound) // 2, hbound, 2 * pos + 2)
            return max(left, right)

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 = RMQ(N, 0)
    DP = [1] * (N + 1)
    for i in reversed(range(N)):
        right = max(i, Connect.search(i, bisect_left(X, X[i] + D[i]), 0, Connect.size, 0))
        Connect.update(i, right)
        DP[i] = (DP[right + 1] + DP[i + 1]) % mod
    print(DP[0])
    

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect, bisect_left

class RMQ(): #range minimum query
    def __init__(self, N, V): #create segment tree with initial value V
        d, k = 1, 0
        while d < N:
            d <<= 1
            k += 1
        self.tree = [V for _ in range(2 * d - 1)]
        self.size = d
    
    def update(self, i, a): #update cell i by value a
        now = self.size - 1 + i 
        self.tree[now] = a
        while now > 0:
            now = (now - 1) // 2
            self.tree[now] = max(self.tree[2 * now + 1], self.tree[2 * now + 2])
        #print(self.tree)

    def search(self, lower, higher, lbound, hbound, pos): #search minimum value of [lower, higher) init: lbound = 0, hbound = self.size, pos = 0
        if higher <= lbound or hbound <= lower: return 0
        if lower <= lbound and hbound <= higher: return self.tree[pos]
        else:
            left = self.search(lower, higher, lbound, (lbound + hbound) // 2, 2 * pos + 1)
            right = self.search(lower, higher, (lbound + hbound) // 2, hbound, 2 * pos + 2)
            return max(left, right)

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)]
    Edge = [i for i in range(N)]
    Connect = RMQ(N, 0)
    for i in range(N):
        Connect.update(i, i)
        k = bisect_left(X, X[i] + D[i])
        Edge[i] = k - 1

    for i in reversed(range(N)):
        Connect.update(i, Connect.search(i, Edge[i] + 1, 0, Connect.size, 0))

    DP = [0] * N
    DP.append(1)
    for i in reversed(range(N)):
        right =  Connect.tree[Connect.size - 1 + i]
        DP[i] = (DP[right+1] + DP[i+1]) % mod
        
    print(DP[0])
    

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect, bisect_left
sys.setrecursionlimit(1000000)

def count(i, Edge, Connect):
    if Edge[i] == i: 
        Connect[i] = 0
        return 0
    if Connect[i] > -1: return Connect[i]   
    far = 0
    for k in range(i + 1, Edge[i] + 1): far = max(far, k - i + count(k, Edge, Connect))
    Connect[i] = far
    return far

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)]
    Edge = [i for i in range(N)]
    Connect = [-1] * N
    for i in range(N):
        k = bisect_left(X, X[i] + D[i])
        Edge[i] = k - 1

    #print(Edge)
    for i in range(N):
        if Connect[i] == -1: count(i, Edge, Connect)
    #print(Connect)
    DP = [0] * N
    DP.append(1)
    for i in reversed(range(N)):
        right = i + Connect[i]
        DP[i] = (DP[right + 1] + DP[i+1]) % mod
        
    print(DP[0])
    

    return 0

if __name__ == "__main__":
    solve()