Problem p02758 (python)

Fixed submission:
from bisect import bisect
from itertools import accumulate
from functools import reduce
from sys import setrecursionlimit

setrecursionlimit(10000000)

MOD = 998244353

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

    parent = [None]*(N+1)

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

    dp = [1]*(N+1)
    for i in reversed(range(1,N+1)):
        p = parent[i]
        dp[p] *= dp[i]+1
        dp[p] %= MOD
    return dp[0]

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

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))