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 main():
    from bisect import bisect_left

    import sys
    input = sys.stdin.readline
    N = int(input())

    MOD = 998244353

    X = []
    X_append = X.append
    dic = dict() #Xから動ける先の場所

    for _ in range(N):
        x, d = map(int, input().split())
        X_append(x)
        dic[x] = x + d

    X.sort()
    lst = []
    lst_append = lst.append
    for x in X:
        tmp = bisect_left(X, dic[x])
        lst_append(tmp)

    move = [0] * N

    INT_MIN = -10 ** 18
    MAX_N = 10 ** 6

    data = [INT_MIN] * (2 * MAX_N - 1)

    def init(n_):
        #簡単にするために2のべき乗に揃える
        n = 1
        while n < n_:
            n *= 2
        return n

    n = init(N)

    def update(k, a):
        k += n - 1
        data[k] = a
        while k > 0:
            k = (k - 1) // 2
            data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k = 0, l = 0, r = n):
        if r <= a or b <= l:
            return INT_MIN
        if a <= l and r <= b:
            return data[k]
        else:
            v1 = query(a, b, 2 * k + 1, l, (l + r)//2)
            v2 = query(a, b, 2 * k + 2, (l + r)//2, r)
            return max(v1, v2)

    def initialize(A): #リストAを与えて初期化する
        for i, a in enumerate(A):
            data[i + n - 1] = a
        for i in range(N + n - 1, 0, -2):
            tmp = i
            tmp = (tmp - 1) //2
            data[tmp] = max(data[tmp * 2 + 1], data[tmp * 2 + 2])

    #初期化
    initialize(lst)

    #ここまででどれを動かしたら何番まで消えるかがわかった
    dp = [[-1] * (2) for _ in range(N + 1)]

    dp[N][0] = 1
    dp[N][1] = 0

    for i in range(N - 1, -1, -1):
        tmp = max(i + 1, query(i, lst[i])) #動くべき場所
        # print (tmp)
        dp[i][0] = (dp[i + 1][0] + dp[i + 1][1]) % MOD
        dp[i][1] = (dp[tmp][0] + dp[tmp][1]) % MOD
        update(i, tmp)

    print (dp[0][0] + dp[0][1])

    # for i in range(N - 1, -1, -1):
    #     dp[i][0] = dp[i + 1][0] + dp[i + 1][1]
    #     dp[i][1] = dp[move[i]][0] + dp[move[i]][1]

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

MOD = 998244353
MIN = -int(2e9)

input = sys.stdin.readline


class RangeMaximumQuery():
    def __init__(self, values):
        n = len(values)
        self.size = 1
        while self.size < n:
            self.size *= 2
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [MIN] * 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] = min(self.tree[i*2], self.tree[i*2+1])

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

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return MIN
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return max(left, right)

    # query segmentation value of [a, b)
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


def main():
    N = int(input())
    robo = [None] * N
    for i in range(N):
        robo[i] = tuple(map(int, input().split()))
    robo.sort(key=itemgetter(0))
    pos = [x[0] for x in robo]
    dst = [x[0] + x[1] for x in robo]
    rmq = RangeMaximumQuery(dst)
    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
def input():
    return sys.stdin.readline()
n = int(input())
xd = [[int(i) for i in input().split()] for _ in range(n)]
xd.sort()


num_max = 2**(n-1).bit_length()
seg_max = [0] * (2 * num_max)
ide_ele_max = -1


def init_max(init_max_val):
    # set_val
    for i in range(n):
        seg_max[i+num_max-1] = init_max_val[i]
    # built
    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


y = [0] * n
j = n-1
for x, d in reversed(xd):
    if x + d > xd[-1][0]:
        y[j] = n
    else:
        mi = 0
        ma = n - 1
        while mi != ma:
            m = (mi + ma) // 2 + 1
            if xd[m][0] < x + d:
                mi = m
            else:
                ma = m - 1
        if mi == j:
            y[j] = mi+1
        else:
            y[j] = query_max(j+1, mi+1)
    update_max(j, y[j])
    j -= 1
dp = [0] * (n + 1)
dp[-1] = 1
j = n-1
for i in y:
    if j == y[j]:
        dp[j] = dp[j+1]
    dp[j] = (dp[j + 1] + dp[y[j]]) % 998244353
    j -= 1
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left

MOD = 998244353
MIN = -int(2e9)

input = sys.stdin.readline


class RangeMaximumQuery():
    def __init__(self, values):
        n = len(values)
        self.size = 1
        while self.size < n:
            self.size *= 2
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [MIN] * 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] = min(self.tree[i*2], self.tree[i*2+1])

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

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return MIN
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return max(left, right)

    # query segmentation value of [a, b)
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


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 = RangeMaximumQuery(dst)
    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:
from bisect import bisect_left

MOD = 998244353
MIN = -int(2e9)


class RangeMaximumQuery():
    def __init__(self, values):
        n = len(values)
        self.size = 1
        while self.size < n:
            self.size *= 2
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [MIN] * 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] = min(self.tree[i*2], self.tree[i*2+1])

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

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return MIN
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return max(left, right)

    # query segmentation value of [a, b)
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


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 = RangeMaximumQuery(dst)
    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:
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,y))

robots_finish.append((INF, INF))
robots_index.append((INF, 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][0]] = 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][0]:
        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: Time Limit Exceeded

Solution code:
from bisect import bisect_left

MOD = 998244353


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])

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.default
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return self.merge(left, right)

    # query segmentation value of [a, b)
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


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:
n = int(input())
xd = [[int(i) for i in input().split()] for _ in range(n)]
xd.sort()


num_max = 2**(n-1).bit_length()
seg_max = [0] * (2 * num_max)
ide_ele_max = -1


def init_max(init_max_val):
    # set_val
    for i in range(n):
        seg_max[i+num_max-1] = init_max_val[i]
    # built
    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


y = [0] * n
init_max(y)
j = n-1
for x, d in reversed(xd):
    if x + d > xd[-1][0]:
        y[j] = n
    else:
        mi = 0
        ma = n - 1
        while mi != ma:
            m = (mi + ma) // 2 + 1
            if xd[m][0] < x + d:
                mi = m
            else:
                ma = m - 1
        if mi == j:
            y[j] = mi+1
        else:
            y[j] = query_max(j+1, mi+1)
    update_max(j, y[j])
    j -= 1
dp = [0] * (n + 1)
dp[-1] = 1
j = n-1
for i in y:
    if j == y[j]:
        dp[j] = dp[j+1]
    dp[j] = (dp[j + 1] + dp[y[j]]) % 998244353
    j -= 1
print(dp[0])

Submission status: Accepted

Solution code:
class SegTree:
    X_unit = -10**10
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

from bisect import bisect_left
mod = 998244353
N = int(input())
robots = []
for i in range(N):
    Xi,Di = map(int,input().split())
    robots.append((Xi,Di))
robots.sort(key=lambda x:x[0])
X = [rob[0] for rob in robots]
D = [rob[1] for rob in robots]

ST = SegTree(N)
ST.set_val(N-1,N-1)
for i in range(N-1)[::-1]:
    r = bisect_left(X,X[i]+D[i])
    if i+1 == r:
        ST.set_val(i,i)
    else:
        ST.set_val(i,ST.fold(i+1,r))
to = ST.X[N:]
dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
    dp[to[i]+1] += dp[i]
    dp[to[i]+1] %= mod
    dp[i+1] += dp[i]
    dp[i+1] %= mod
print(dp[N])

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit
from numba.types import Omitted
i4 = numba.int32
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

@njit((numba.types.optional(i8), ) * 2, cache=True)
def seg_f(x, y):
    if x is None:
        return y
    if y is None:
        return x
    return max(x, y)


@njit((i8[:], ), cache=True)
def build(raw_data):
    N = len(raw_data)
    seg = np.zeros(N + N, np.int64)
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
    return seg


@njit((i8[:], i8, i8), cache=True)
def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])


@njit((i8[:], i8, i8), cache=True)
def fold(seg, l, r):
    vl = vr = None
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)

def main(XD):
    X, D = XD[::2], XD[1::2]
    N = len(X)
    argsort = np.argsort(X)
    X, D = X[argsort], D[argsort]
    INF = 1 << 60
    X = np.append(X, INF)
    D = np.append(D, 1)
    # i 台目を起動したとき、生き残るはじめてのロボを求める
    dp0 = np.searchsorted(X, X + D)
    seg = build(dp0)
    for n in range(N - 1, -1, -1):
        x = fold(seg, n, dp0[n])
        dp0[n] = x
        set_val(seg, n, x)
    # n 台目より右側での状態の数え上げ
    dp = np.zeros(N + 1, np.int64)
    dp[-1] = 1
    for n in range(N - 1, -1, -1):
        nxt = dp0[n]
        dp[n] = (dp[n + 1] + dp[nxt]) % MOD  # 動かさない、動かす
    return dp[0]

N = int(readline())
XD = np.array(read().split(), np.int64)

print(main(XD))

Submission status: Accepted

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

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : max(x,y), default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res
st=SegmentTree(n)
for i in range(n):
    st.update(i,i)

for i in range(n):
    x,d=xd[n-1-i]
    tmp=bisect_left(aryx,x+d)
    sti=st.query(n-1-i,tmp)
    st.update(n-1-i,sti)
    dp[n-1-i]=dp[n-1-i+1]+dp[sti+1]
    dp[n-1-i]%=mod
print(dp[0])

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
from bisect import bisect_left
from operator import itemgetter


import numpy as np

def segment_tree_op(a, b):
    return a if a[0] > b[0] else b

def segment_tree_get(seg, l, r):
    elem_size, tree, result, _ = seg
    l += elem_size
    r += elem_size
    while l < r:
        if l & 1:
            result = segment_tree_op(tree[l], result)
            l += 1
        if r & 1:
            r -= 1
            result = segment_tree_op(tree[r], result)
        l, r = l >> 1, r >> 1
    return result

def segment_tree_set(seg, i, value):
    elem_size, tree, _, _ = seg
    k = elem_size + i
    tree[k] = value
    while k > 1:
        k >>= 1
        tree[k] = segment_tree_op(tree[k<<1], tree[k<<1|1])

def segment_tree_get_one(seg, i):
    elem_size, tree, _, _ = seg
    return tree[i+elem_size]

def segment_tree_construct(arr):
    identity = np.array([0], dtype=np.int64)
    real_size = len(arr)
    elem_size = 1 << int(np.log2(real_size-1))+1
    tree = np.empty((elem_size*2, len(identity)), dtype=np.int64)
    tree[elem_size:elem_size+real_size] = arr
    tree[elem_size+real_size:] = identity
    for i in range(elem_size - 1, 0, -1):
        tree[i] = segment_tree_op(tree[i<<1], tree[i<<1|1])
    return elem_size, tree, identity, real_size

class SegmentTree:
    element_type = "i8[:]"
    a_type = f"Tuple((i8,i8[:,:],{element_type},i8))"
    numba_config = [
        [segment_tree_op, f"{element_type}({element_type},{element_type})"],
        [segment_tree_construct, f"{a_type}(i8[:,:])"],
        [segment_tree_get, f"{element_type}({a_type},i8,i8)"],
        [segment_tree_set, f"void({a_type},i8,{element_type})"],
        [segment_tree_get_one, f"{element_type}({a_type},i8)"],
    ]
    def __init__(self, arr):
        self.a = segment_tree_construct(arr)

    def get(self, l, r):
        return segment_tree_get(self.a, l, r)

    def set(self, i, value):
        return segment_tree_set(self.a, i, value)

    def get_one(self, i):
        return segment_tree_get_one(self.a, i)

numba_compile(SegmentTree.numba_config)

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(np.arange(N, dtype=np.int64).reshape(N, 1))
    for i, (x, d) in zip(range(N-1,-1,-1), XD[::-1]):
        r = bisect_left(X, x+d, lo=i)
        seg.set(i, seg.get(i, r))
    D2 = seg.a[1][seg.a[0]:seg.a[0]+seg.a[3]].ravel()
    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: Accepted

Solution code:
from heapq import *
N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
X.sort(reverse=True)
Q=[]
heapify(Q)
Y=0
mod=998244353
for i in range(N):
  Y=1
  while len(Q):
    if Q[0][0]<X[i][0]+X[i][1]:
      Y=Y*Q[0][1]%mod
      heappop(Q)
    else:
      break
  heappush(Q,(X[i][0],Y+1))
P=1
while len(Q):
  P=P*heappop(Q)[1]%mod
print(P)

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    if S=="AAA" or S=="BBB":
        print("No")
    else:
        print("Yes")
    return

def examB():
    N, A, B = LI()
    loop = N//(A+B)
    ans = loop*A + min(A,N%(A+B))
    print(ans)
    return

def examC():
    A, B = LI()
    ans = -1
    for i in range(1,20000):
        if i*8//100==A:
            if i*10//100==B:
                ans = i
                break
    print(ans)
    return

def examD():
    S = SI()
    Q = I()
    rev = 0
    L = ""; R = ""
    for _ in range(Q):
        q = LSI()
        if q[0]=="1":
            rev += 1
        else:
            c = int(q[1])
            if (c+rev)%2==1:
                L += q[2]
            else:
                R += q[2]
    ans = ""
    if rev%2==0:
        ans = L[::-1] + S + R
    else:
        ans = R[::-1] + S[::-1] + L
    print(ans)
    return

def examE():
    N, P = LI()
    S = SI()
    A = [0]*(N+1)
    cur = 0
    if P==5:
        ans = 0
        for i in range(N):
            if int(S[N-1-i])%5==0:
                ans += N-i
        print(ans)
        return
    elif P==2:
        ans = 0
        for i in range(N):
            if int(S[N-1-i])%2==0:
                ans += N-i
        print(ans)
        return

    for i in range(N):
        s = int(S[N-1-i])
        cur += s*pow(10,i,P)
        A[i+1] = cur%P
    D = [0]*P
    for a in A:
        D[a] += 1
    ans = 0
    #print(A)
    for d in D:
        ans += d*(d-1)//2

    print(ans)
    return

def examF():
    def dfs(n, s):
        #input()
        #print(n,s)
        cur = 1
        can = sum(X[s])
        for i in range(s,n):
            if X[i][0]>=can:
                V[s] = cur
                return cur, i
            if i==n-1:
                return cur,i
            now, visited = dfs(n, i+1)
            cur += now
        V[s] = cur
        return cur, n
    N = I()
    X = [LI()for _ in range(N)]
    X.sort()
    V = [[]for _ in range(N)]
    neg = 0
    ans = dfs(N,0)
    print(V)

    print(ans)
    return

def examF2():
    N = I()
    X = [LI()for _ in range(N)]
    N += 1
    X.sort()
    parent = [-1] * N
    #print(X)

    stack = [(inf,-1)]
    for i,(x,d) in enumerate(X):
        d += x
        # x座標近いやつからチェック
        # 届かないやつ排除
        while(stack[-1][0]<=x):
            stack.pop()
        parent[i] = stack[-1][1]
        stack.append((d,i))

    #print(parent)
    dp = [1]*N
    ans = 1
    for i in range(N-1)[::-1]:
        p = parent[i]
        if p==-1:
            ans *= dp[i]+1
            ans %= mod2
            continue
        dp[p] *= dp[i]+1
        dp[p] %= mod2

    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examF2()

"""

"""

Submission status: Accepted

Solution code:
import sys
import bisect
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
inf = 10**18
mod = 998244353


class SegmentTree:
    def __init__(self, N, arr=None, op=None, unit=None):
        """
        INPUT
        N: 配列のサイズ
        segment tree: 1-indexedで構築
        original array: 0-indexed
                 1
           2           3
         4    5     6     7
        8 9 10 11 12 13 14 15
        ---------------------
        0 1 2  3  4  5  6  7
        """
        self.N = N
        self.unit = unit
        self.op = op
        self.tree = [unit] * (2 * N + 1)
        if arr is not None:
            self._build(arr)

    def _build(self, arr):
        op = self.op
        N = self.N
        for i, a in enumerate(arr, N):
            self.tree[i] = a
        for i in reversed(range(1, N)):
            self.tree[i] = op(self.tree[i << 1], self.tree[i << 1 | 1])

    def update(self, i, x):
        """
        arr[i]の値をxに変更する
        i: 0-indexed
        """
        i += self.N
        op = self.op
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = op(self.tree[i << 1], self.tree[i << 1 | 1])

    def val(self, i):
        return self.tree[i + self.N]

    def query(self, L, R):
        """
        L,R: 0-indexed
        半開区間[L,R)の累積演算した値を返す
        """
        op = self.op
        res = self.unit
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                res = op(res, self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                res = op(res, self.tree[R])
            L >>= 1
            R >>= 1
        return res


N = int(input())
XD = list(tuple(map(int, input().split())) for _ in range(N))
XD.sort()
X, D = zip(*XD)
X += (inf, )


seg = SegmentTree(N+1, None, max, 0)
for L in reversed(range(N)):
    R = bisect.bisect_left(X, X[L] + D[L])
    p = seg.query(L, R)
    seg.update(L, max(L, p))

dp = [0] * (N + 1)
dp[-1] = 1
for i in reversed(range(N)):
    p = seg.val(i)
    dp[i] = (dp[i + 1] + dp[p + 1]) % mod

print(dp[0])