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: Runtime Error

Solution code:
import queue


class Solution:

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

        m = 998244353

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

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

        li = []

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

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

        ans = 1

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

            return (res + 1) % m

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

        return ans


if __name__ == '__main__':

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

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

Submission status: Runtime Error

Solution code:
N = int(input())
XD = [[int(i) for i in input().split()] for _ in range(N)]
XD.sort()
MOD = 998244353
sorted_X = [X for X,_ in XD]

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

from bisect import bisect_left

parent = [-1] * N

for i in range(N-1, -1, -1):
    idx = bisect_left(sorted_X, XD[i][0] + XD[i][1])
    for j in range(i+1, idx):
        if parent[j] < 0:
            parent[j] = i

for i,par in enumerate(parent):
    if par < 0:
        continue
    edge[par].append(i)

def cnt(node):
    if not edge[node]:
        return 2
    
    res = 1
    for v in edge[node]:
        res = (res * cnt(v)) % MOD
    res += 1

    return res % MOD

ans = 1
for i,par in enumerate(parent):
    if par < 0:
        ans = (ans * cnt(i)) % MOD

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import *
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 998244353

def main():
    def dfs(i):
        res=mint(1)
        for j in to[i]:
            res*=dfs(j)
        return res+1

    n=II()
    xd=LLI(n)
    xd.sort(reverse=True)
    to=[[] for _ in range(n)]
    hp=[]
    for i,(x,d) in enumerate(xd):
        while hp and hp[0][0]<x+d:
            px,pi=heappop(hp)
            to[i].append(pi)
        heappush(hp,(x,i))
    ans=1
    while hp:
        _,i=heappop(hp)
        ans*=dfs(i)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
# XD = [tuple(map(int,input().split())) for i in range(n)]
XD = [(-10**10,inf)]
for i in range(n):
  x,d = map(int,input().split())
  XD.append((x,d))
XD.sort()
visited = [0] * (n+1)
def dfs(node):
  visited[node] = 1
  res = 1
  for i in range(node+1,n+1):
    if XD[i][0] < XD[node][0] + XD[node][1]:
      if visited[i]:continue
      res *= dfs(i)
      res %= mod
    else: break
  # print(node,res+1)
  return res + 1
print((dfs(0)-1)%mod)
# print(visited)
# print(XD)
# dfs(1)

Submission status: Runtime Error

Solution code:
import heapq

mod = 998244353

def dfs(v: int, child) -> int:
  res = 1
  for u in child[v]:
    res = res * dfs(u, child) % mod
  return res + 1

n = int(input())
robot = [tuple(map(int, input().split())) for _ in range(n)]
robot.sort()
child = [[] for _ in range(n)]

root = []
for i in range(n-1, -1, -1):
  x, d = robot[i]
  while root:
    r = heapq.heappop(root)
    if r[0] < x + d:
      child[i].append(r[1])
    else:
      heapq.heappush(root, r)
      break
  heapq.heappush(root, (x, i))
  
count = 1
for r in root:
  count = count * dfs(r[1], child) % mod
print(count)

Submission status: Runtime Error

Solution code:
import heapq

mod = 998244353

def dfs(v: int, child) -> int:
  res = 1
  for u in child[v]:
    res = res * dfs(u) % mod
  return res + 1

n = int(input())
robot = [tuple(map(int, input().split())) for _ in range(n)]
robot.sort()
child = [[] for _ in range(n)]

root = []
for i in range(n-1, -1, -1):
  x, d = robot[i]
  while root:
    r = heapq.heappop(root)
    if r[0] < x + d:
      child[i].append(r[1])
    else:
      heapq.heappush(root, r)
      break
  heapq.heappush(root, (x, i))
  
count = 1
for r in root:
  count = count * dfs(r[1], child) % mod
print(count)

Submission status: Runtime Error

Solution code:
import heapq

mod = 998244353

def dfs(v: int) -> int:
  res = 1
  for u in child[v]:
    res = res * dfs(u) % mod
  return res + 1

n = int(input())
robot = [tuple(map(int, input().split())) for _ in range(n)]
robot.sort()
child = [[] for _ in range(n)]

root = []
for i in range(n-1, -1, -1):
  x, d = robot[i]
  while root:
    r = heapq.heappop(root)
    if r[0] < x + d:
      child[i].append(r[1])
    else:
      heapq.heappush(root, r)
      break
  heapq.heappush(root, (x, i))
  
count = 1
for r in root:
  count = count * dfs(r[1]) % mod
print(count)

Submission status: Runtime Error

Solution code:
import heapq

def dfs(v: int) -> int:
  res = 1
  for u in child[v]:
    res *= dfs(u)
  return res + 1

n = int(input())
robot = [tuple(map(int, input().split())) for _ in range(n)]
robot.sort()
child = [[] for _ in range(n)]

root = []
for i in range(n-1, -1, -1):
  x, d = robot[i]
  while root:
    r = heapq.heappop(root)
    if r[0] < x + d:
      child[i].append(r[1])
    else:
      heapq.heappush(root, r)
      break
  heapq.heappush(root, (x, i))
  
count = 1
for r in root:
  count *= dfs(r[1])
print(count)

Submission status: Runtime Error

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

xds.insert(0, (-1000000001, 2000000004))
n += 1

def make_blocks(i):
    x, d = xds[i]
    right = x + d
    res = []
    nexti = i + 1
    while(nexti < n):
        xn, dn = xds[nexti]
        if xn < right:
            l, lasti = make_blocks(nexti)
            res.append(l)
            nexti = lasti + 1
        else:
            return res, nexti - 1
    return res, n - 1

l, _ = make_blocks(0)

def count(l):
    ans = 1
    for ll in l:
        ans = ans * (1 + count(ll)) % 998244353
    return ans

print(count(l))

Submission status: Runtime Error

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

xds.insert(0, (-1000000001, 2000000004))
n += 1

def make_blocks(i):
    x, d = xds[i]
    right = x + d
    res = []
    nexti = i + 1
    while(nexti < n):
        xn, dn = xds[nexti]
        if xn < right:
            l, lasti = make_blocks(nexti)
            res.append(l)
            nexti = lasti + 1
        else:
            return res, nexti - 1
    return res, n - 1

l, _ = make_blocks(0)

def count(l):
    ans = 1
    for ll in l:
        ans *= 1 + count(ll)
    return ans

print(count(l))

Submission status: Runtime Error

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

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


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

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

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

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

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

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

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

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

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

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

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

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

ddprint(xd)
ddprint(x)

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

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

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

ddprint(f)
print(f[0])

Submission status: Runtime Error

Solution code:
from bisect import bisect
from itertools import accumulate
from functools import reduce
MOD = 998244353

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

    parent = [None]*(N+1)

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

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

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

    return rec(0)

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

Submission status: Runtime Error

Solution code:
from bisect import bisect
from itertools import accumulate

MOD = 998244353

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

    origins = [x for x,d in robots]
    dests = [x+d for x,d in robots]

    parent = [None]*(N+1)

    stack = [(float('inf'),0)]
    for i,(o,d) in enumerate(zip(origins,dests),start=1):
        while stack[-1][0] <= o:
            stack.pop()
        parent[i] = stack[-1][1]
        while stack[-1][0] <= d:
            stack.pop()
        stack.append((d,i))

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

    def rec(i):
        if not adj[i]:
            return 1
        a = 1
        for j in adj[i]:
            a *= rec(j)+1
            a %= MOD
        return a

    return rec(0)

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

Submission status: Runtime Error

Solution code:
from functools import lru_cache
from bisect import bisect
from itertools import accumulate

MOD = 998244353

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

    origins = [-10**10]+[x for x,d in robots]
    dests = [10**10]+[x+d for x,d in robots]

    parent = [None]*N

    stack = [(float('inf'),None)]
    for i,(o,d) in enumerate(zip(origins,dests)):
        while stack[-1][0] <= o:
            stack.pop()
        parent[i] = stack[-1][1]
        while stack[-1][0] <= d:
            stack.pop()
        stack.append((d,i))

    adj = [list() for _ in range(N)]
    for i,p in enumerate(parent):
        if p is not None:
            adj[p].append(i)

    @lru_cache(None)
    def rec(i):
        if not adj[i]:
            return 1
        a = 1
        for j in adj[i]:
            a *= rec(j)+1
            a %= MOD
        return a

    return rec(0)

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
X_D_list = []
for i in range(N):
    X_D_list.append(list(map(int, input().split())))

X_D_list.sort()

ans = 2 ** N
i = 0
before_max_reach = X_D_list[0][0] + X_D_list[0][1]
for _ in range(N):
    for j in range(1, N - i):
        X_D = X_D_list[i + j]
        if X_D[0] > before_max_reach:
            i += j
            ans *= (1 - (2 ** (j - 1) - 1) // (2 ** j))
            break
        before_max_reach = max(before_max_reach, X_D[0] + X_D[1])
    else:
        ans *= (1 - (2 ** j - 1) / (2 ** (j + 1)))
    if i <= N - 1:
        break

mod_div_num = 998244353
print(int(ans % mod_div_num))

Submission status: Runtime Error

Solution code:
import bisect

p=998244353
def dfs(ten):
    if(len(kodomo[ten])==0):
        return 1
    ret=1
    for k in kodomo[ten]:
        ret*=1+dfs(k)
        ret %=p
    return ret

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

xd.sort()
basho.sort()
oya=[-1]*n

for i in range(n-1):
    doko=bisect.bisect_left(basho,xd[i][0]+xd[i][1])
    if(doko>i):
        for j in range(i+1,doko):
            oya[j]=i

kodomo=[[]for i in range(n)]
kami=[]
for i in range(n):
    if(oya[i]!=-1):
        kodomo[oya[i]].append(i)
    else:
        kami.append(i)

ans=1
for kaminoko in kami:
    ans*=1+dfs(kaminoko)
    ans%=p

print(ans)

Submission status: Runtime Error

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=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 [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[LI() for _ in range(n)]
  _l=sorted(l,key=lambda x:x[1])
  l=[]
  for x,y in _l:
    l.append(x)

  ans=1
  for i in range(n):
    ans*=2
    ans%=mod

  for i in range(n)[::-1]:
    a=_l[i][0]+_l[i][1]
    # print(a)
    # print(l)
    # print(bisect.bisect_left(l,a))

    b=bisect.bisect_left(l,a)-i
    ans-=2**(b-1)
    if ans<0:
      ans+=mod

  return ans

# main()
print(main())

Submission status: Runtime Error

Solution code:
# coding: utf-8
N=int(input())
MOD=998244353
G=[[] for i in range(N)]
P=[1 for i in range(N)]
X=[]
D=[]
XD=[]
m=[]
for i in range(N):
    x,d=map(int,input().split())
    X.append(x)
    D.append(d)
    XD.append(x+d)

for i in range(N):
    n=0
    for j in range(len(m)):
        k=m[j-n]
        if XD[k]<X[i]:
            m.pop(j)
            n+=1
    if m:
        G[max(m)].append(i)
    
    m.append(i)
    
for i in range(N):
    k=N-1-i
    if G[k]:
        for j in G[k]:

            P[k]*=P[j]

            P[k]=P[k]%MOD
        P[k]+=1
        P[k]=P[k]%MOD
    else:
        P[k]=2
        
print(max(P))

Submission status: Runtime Error

Solution code:
from functools import lru_cache
from bisect import bisect
from itertools import accumulate

MOD = 998244353

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

    origins = [-float('inf')]+[x for x,d in robots]
    dests = [10**10]+[x+d for x,d in robots]

    parent = [None]*N

    stack = [(float('inf'),None)]
    for i,(o,d) in enumerate(zip(origins,dests)):
        while stack[-1][0] <= o:
            stack.pop()
        parent[i] = stack[-1][1]
        while stack[-1][0] <= d:
            stack.pop()
        stack.append((d,i))

    adj = [list() for _ in range(N)]
    for i,p in enumerate(parent):
        if p is not None:
            adj[p].append(i)

    @lru_cache(None)
    def rec(i):
        if not adj[i]:
            return 1
        a = 1
        for j in adj[i]:
            a *= rec(j)+1
            a %= MOD
        return a

    return rec(0)

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

Submission status: Runtime Error

Solution code:
3 3

Submission status: Runtime Error

Solution code:
from bisect import bisect_left,bisect_right
mod=998244353
seg=[]
num=0
#####segfunc######
def segfunc(x,y):
    return max(x,y)

def init(init_val,seg,num):
    #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,seg,num):
    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,seg,num):
    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

def check(xd):
  n=len(xd)
  ide_ele = 0
  num=2**(n-1).bit_length()
  seg=[ide_ele]*2*num
  x=[]
  d=[]
  for i,j in xd:
    x.append(i)
    d.append(j)
  se=[x[i]+d[i] for i in range(n)]
  init(se,seg,num)
  dp=[0]*(n+1)
  dp[-1]=1
  dp[-2]=2
  for i in range(n-2,-1,-1):
    j=bisect_right(x,x[i]+d[i]-1)
    j=bisect_right(x,query(i,j,seg,num))
    dp[i]=dp[i+1]+dp[j]
  return dp[0]

n=int(input())
xd=[list(map(int,input().split()))for _ in range(n)]+[[10**18+7,0]]
xd.sort()
t=[]
m=sum(xd[0])
j=0
for i in range(1,n+1):
  if xd[i][0]<m:m=max(sum(xd[i]),m)
  else:
    t.append([j,i-1])
    j=i
    m=sum(xd[i])
print(t)
ans=1
for i,j in t:
  ans*=check(xd[i:j+1])
  ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
from bisect import bisect
from itertools import accumulate

MOD = 998244353

def solve(robots):
    robots.append((-float('inf'),float('inf')))
    N = len(robots)
    robots.sort()

    origins = [x for x,d in robots]
    dests = [x+d for x,d in robots]

    parent = [None]*N

    stack = [(float('inf'),None)]
    for i,(o,d) in enumerate(zip(origins,dests)):
        while stack[-1][0] <= o:
            stack.pop()
        parent[i] = stack[-1][1]
        while stack[-1][0] <= d:
            stack.pop()
        stack.append((d,i))

    adj = [list() for _ in range(N)]
    for i,p in enumerate(parent):
        if p is not None:
            adj[p].append(i)
    sources = [i for i,v in enumerate(parent) if v is None]

    @lru_cache(None)
    def rec(i):
        if not adj[i]:
            return 1
        a = 1
        for j in adj[i]:
            a *= rec(j)+1
            a %= MOD
        return a

    return rec(0)

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

Submission status: Runtime Error

Solution code:
N = int(input())
XD = [list(map(int, input().split())) for _ in range(N)]

import sys
sys.setrecursionlimit(N + 1)

DIVIDER = 998244353

XD.sort(key=lambda x: x[0])
X_l = []
X_r = []
for i, (Xi, Di) in enumerate(XD):
    X_l.append(Xi)
    X_r.append(Xi + Di)

import bisect

memo = [None] * N
memo[N - 1] = N - 1

def dp(pos):
    if memo[pos] != None: return memo[pos]
    #
    i_tar = bisect.bisect_left(X_l, X_r[pos])
    i_tar = max(0, i_tar - 1)
    #
    if i_tar <= pos:
        ret = pos
    else:
        ret = pos
        for i_next in range(pos + 1, i_tar + 1):
            # print("##", pos, '->', i_next)
            ret = max(ret, dp(i_next))
    #
    memo[pos] = ret
    # print("##", (pos, X_l[pos], X_r[pos]), i_tar, ret)
    return ret

# print("#", X_l)
# print("#", X_r)
for i in range(N):
    _ = dp(i)

# print("#", memo)

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

for i in range(N):
    ans[N - 1 - i] = (ans[N - 1 - i] + ans[N - i]) % DIVIDER
    ans[N - 1 - i] = (ans[N - 1 - i] + ans[memo[N - 1 - i] + 1]) % DIVIDER
                
print(ans[0])

Submission status: Runtime Error

Solution code:
N = int(input())
XD = [list(map(int, input().split())) for _ in range(N)]

DIVIDER = 998244353

XD.sort(key=lambda x: x[0])
X_l = []
X_r = []
for i, (Xi, Di) in enumerate(XD):
    X_l.append(Xi)
    X_r.append(Xi + Di)

import bisect

memo = [None] * N
memo[N - 1] = N - 1

def dp(pos):
    if memo[pos] != None: return memo[pos]
    #
    i_tar = bisect.bisect_left(X_l, X_r[pos])
    i_tar = max(0, i_tar - 1)
    #
    if i_tar <= pos:
        ret = pos
    else:
        ret = pos
        for i_next in range(pos + 1, i_tar + 1):
            # print("##", pos, '->', i_next)
            ret = max(ret, dp(i_next))
    #
    memo[pos] = ret
    # print("##", (pos, X_l[pos], X_r[pos]), i_tar, ret)
    return ret

# print("#", X_l)
# print("#", X_r)
for i in range(N):
    _ = dp(i)

# print("#", memo)

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

for i in range(N):
    ans[N - 1 - i] = (ans[N - 1 - i] + ans[N - i]) % DIVIDER
    ans[N - 1 - i] = (ans[N - 1 - i] + ans[memo[N - 1 - i] + 1]) % DIVIDER
                
print(ans[0])

Submission status: Runtime Error

Solution code:
MOD = 998244353
INF = 10 ** 10
n = int(input())
robots_finish = []
robots_index = []
for i in range(n):
    x, d = map(int, input().split())
    y = x + d
    robots_finish.append((y,x))
    robots_index.append(x)

robots_finish.append((INF, INF))
robots_index.append(INF)
n += 1

robots_finish.sort(reverse=True)
robots_index.sort()

from heapq import heappush, heappop

s = []
l = [-1] * n
r = 0
robot_dict = {}
for i in range(n):
    robot_dict[robots_index[i]] = i

for i in range(n-1, 0, -1):
    while(r < n and robots_finish[r][0] > robots_index[i][0]):
        heappush(s, -robots_finish[r][1])
        r += 1
    while len(s) > 0 and -s[0] >= robots_index[i]:
        heappop(s)
    if len(s) > 0:
        l[i] = robot_dict[-s[0]]

dp = [0] * n
dp_sum = [0] * n
dp[0] = 1
dp_sum[0] = 1

#print(l)
for i in range(1, n):
    dp[i] = dp_sum[i-1]
    if l[i] -1 >= 0:
        dp[i] -= dp_sum[l[i]-1]
    if l[i] == -1:
        dp[i] += 1
    dp[i] %= MOD
    dp_sum[i] = dp_sum[i-1] + dp[i]
    dp_sum[i] %= MOD

#print(dp)
print(dp[n-1])

Submission status: Runtime Error

Solution code:
import bisect
import sys

stdin = sys.stdin

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

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


class Segtreermq:
    M: int
    H: int
    vals: [int]

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

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

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

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

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

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

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

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

Submission status: Runtime Error

Solution code:
import bisect
from operator import itemgetter
import sys

stdin = sys.stdin

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

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


class Segtreermq:
    M: int
    H: int
    vals: [int]

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

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

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

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

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

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

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

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