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:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 998244353
input = lambda:sys.stdin.readline().rstrip()

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

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

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

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
from bisect import bisect_left as bisect
from operator import itemgetter
N = int(input())
XD = [list(map(int,input().split())) for _ in range(N)]
XD.sort(key=itemgetter(0))
X = [XD[i][0] for i in range(N)]
D = [XD[i][1] for i in range(N)]

N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(4*N0)

def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N-1,-1,-1):
    x,d = XD[i]
    j = bisect(X,x+d)
    update(i,-i)
    update(i,query(i,j))

dp = [1]*(N+1)

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

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

n = 0
x = []
d = []

def search(s):
    lo = 0
    hi = n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if s > x[mid]:
            lo = mid + 1
        elif s < x[mid]:
            hi = mid - 1
        else:
            return mid
    return max(lo, hi)


if __name__ == "__main__":
    xd = []
    n = int(input())
    for i in range(n):
        xi, di = map(int, input().split())
        xd.append((xi, di))

    xd.sort()
    x = list(map(lambda x: x[0], xd))
    d = list(map(lambda x: x[1], xd))

    dp = [0] * (n+1)
    dp[-1] = 1
    next = [0] * n

    for i in range(n-1, -1, -1):
        currend = search(x[i] + d[i])
        j =  i+1
        while j < currend:
            currend = max(search(x[j] + d[j]), currend)
            j += 1
        next[i] = currend

    for i in range(n - 1, -1, -1):
        dp[i] = (dp[next[i]] + dp[i + 1]) % mod
    
    print(dp[0])
    
    # print(x, d)
    # print(dp)
    # print(next)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
sys.setrecursionlimit(200005)
MOD = 998244353
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )


n = int(input())
ls = list()
for i in range(n):
    x,d = map(int, input().split())
    ls.append((x,x+d))

ls.sort()

g = [list() for _ in range(n)]
INF = 1001001001
last = -1
def dfs_g(u):
    global last
    to = ls[u][1]
    idx = bisect.bisect_left(ls, (to,-INF))
    v = u+1
    while v < idx:
        if last >= v:
            continue
        g[u].append(v)
        last = v
        dfs_g(v)
        v = last
        v += 1

root = list()
while last < n-1:
    last+=1
    root.append(last)
    dfs_g(last)
    
def dfs_dp(u,p=-1):
    if len(g[u]) == 0:
        return mint(2)
    res = mint(1)
    for v in g[u]:
        if v == p:
            continue
        res *= dfs_dp(v,u)
    res += mint(1)
    return res

ans = mint(1)

for r in root:
    ans *= dfs_dp(r)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    X = sorted([list(map(int,input().split())) for i in range(n)])
    mod = 998244353
    e = [[] for i in range(n)]

    def dfs(x):
        count = 1

        for i in e[x]:
            count *= dfs(i)
            count %= mod
        return count+1

    q = deque([])

    for i in range(n-1,-1,-1):
        a,b = X[i]
        while q and q[0][0] < a+b:
            e[i].append(q[0][1]) 
            q.popleft()
        q.appendleft([a,i])

    ans = 1
    for i,j in q:
        ans *= dfs(j)
        ans %= mod
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
MOD = 998244353


class SegmentTree1():
    """
    1-indexed Segment Tree
    """
    def __init__(self, n_, ele_id, op_func):
        self.n = 1 << (n_ - 1).bit_length()  # size
        self.data = [ele_id] * (2 * self.n)  # binary tree (1-indexed)
        self.ele_id = ele_id  # identity element
        self.op_func = op_func  # binary operation of monoid

    def __getitem__(self, i):
        return self.data[i + self.n]

    def build(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n] = data_init[i]  # set data in leaf
        for i in reversed(range(self.n)):
            self.data[i] = self.op_func(self.data[2 * i], self.data[2 * i + 1])

    def update(self, i, x):
        # change i-th element to x (i : 0-indexed)
        i += self.n
        self.data[i] = x
        while i > 1:
            i = i >> 1  # go to parenet-node
            self.data[i] = self.op_func(self.data[2 * i], self.data[2 * i + 1])

    def query(self, l, r):
        # query for interval [l, r) (l, r : 0-indexed)
        l += self.n
        r += self.n
        ret = self.ele_id
        while l < r:
            if l & 1:  # right child
                ret = self.op_func(ret, self.data[l])
                l += 1
            if r & 1:  # right child
                r -= 1
                ret = self.op_func(ret, self.data[r])
            # go to parent-nodes
            l = l >> 1
            r = r >> 1
        return ret


n = int(input())
robot = [tuple(map(int, input().split())) for _ in range(n)]
robot.sort(key=itemgetter(0))
x = [robot[i][0] for i in range(n)]

# dp[i] = (i番目のロボットを起動すると最終的にdp[i]番目まで起動する)
dp = [0] * n
dp[n - 1] = n - 1

st_rmq = SegmentTree1(n, 0, max)
st_rmq.update(n - 1, dp[n - 1])
for i in reversed(range(n - 1)):
    r = bisect_left(x, x[i] + robot[i][1])
    dp[i] = max(i, st_rmq.query(l=i + 1, r=r))
    st_rmq.update(i, dp[i])

# print(robot)
# print(dp)

dp2 = [0] * (n + 1)
dp2[n] = 1
for i in reversed(range(n)):
    dp2[i] = dp2[i + 1] + dp2[dp[i] + 1]
    dp2[i] %= MOD
# print(dp2)

print(dp2[0])

Submission status: Time Limit Exceeded

Solution code:
class Operation:
    def __init__(self, name, function, function_on_equal, neutral_value=0):
        self.name = name
        self.f = function
        self.f_on_equal = function_on_equal


def min_multiple(x, count):
    return x


min_operation = Operation("min", min, min_multiple, 1e9)


class SegmentTree:
    """
    SegmentTree class. Handles an underlying array as well as available
    operations and pointer to the root of a tree.
    """

    def __init__(self, array, operations=[min_operation]):
        """
        Builds a segment tree based on the provided `array`. Supports operations
        of class Operation provided in the operations array.
        """
        self.array = array
        if type(operations) != list:
            raise TypeError("operations must be a list")
        self.operations = {}
        for op in operations:
            self.operations[op.name] = op
        self.root = SegmentTreeNode(0, len(array) - 1, self)

    def query(self, start, end, operation_name):
        """
        Returns the result of the operation execution with `operation_name`
        on the range from [start, end]
        """
        if self.operations.get(operation_name) == None:
            raise Exception("This operation is not available")
        return self.root._query(start, end, self.operations[operation_name])

    def summary(self):
        """
        Prints the summary for the whole array (values in the root node).
        """
        return self.root.values

    def update(self, position, value):
        """
        Updates an old value at `position` to a new `value`.
        """
        self.root._update(position, value)

    def update_range(self, start, end, value):
        """
        Updates old values old in the range [start, end], inclusively, to a new value.
        """
        self.root._update_range(start, end, value)

    def __repr__(self):
        return self.root.__repr__()


class SegmentTreeNode:
    """
    Internal SegmentTreeNode class represents a node of a segment tree. Each node
    stores the reference to the left and the right bound of a segment this
    node is responsible for.
    """

    def __init__(self, start, end, segment_tree):
        self.range = (start, end)
        self.parent_tree = segment_tree
        self.range_value = None
        self.values = {}
        self.left = None
        self.right = None
        if start == end:
            self._sync()
            return
        self.left = SegmentTreeNode(start, start + (end - start) // 2, segment_tree)
        self.right = SegmentTreeNode(start + (end - start) // 2 + 1, end, segment_tree)
        self._sync()

    def _query(self, start, end, operation):
        if end < self.range[0] or start > self.range[1]:
            return None
        if start <= self.range[0] and self.range[1] <= end:
            return self.values[operation.name]
        self._push()
        left_res = self.left._query(start, end, operation) if self.left else None
        right_res = self.right._query(start, end, operation) if self.right else None
        if left_res is None:
            return right_res
        if right_res is None:
            return left_res
        return operation.f([left_res, right_res])

    def _update(self, position, value):
        if position < self.range[0] or position > self.range[1]:
            return
        if position == self.range[0] and self.range[1] == position:
            self.parent_tree.array[position] = value
            self._sync()
            return
        self._push()
        self.left._update(position, value)
        self.right._update(position, value)
        self._sync()

    def _update_range(self, start, end, value):
        if end < self.range[0] or start > self.range[1]:
            return
        if start <= self.range[0] and self.range[1] <= end:
            self.range_value = value
            self._sync()
            return
        self._push()
        self.left._update_range(start, end, value)
        self.right._update_range(start, end, value)
        self._sync()

    def _sync(self):
        if self.range[0] == self.range[1]:
            for op in self.parent_tree.operations.values():
                current_value = self.parent_tree.array[self.range[0]]
                if self.range_value is not None:
                    current_value = self.range_value
                self.values[op.name] = op.f([current_value])
        else:
            for op in self.parent_tree.operations.values():
                result = op.f([self.left.values[op.name], self.right.values[op.name]])
                if self.range_value is not None:
                    bound_length = self.range[1] - self.range[0] + 1
                    result = op.f_on_equal(self.range_value, bound_length)
                self.values[op.name] = result

    def _push(self):
        if self.range_value is None:
            return
        if self.left:
            self.left.range_value = self.range_value
            self.right.range_value = self.range_value
            self.left._sync()
            self.right._sync()
            self.range_value = None

    def __repr__(self):
        ans = "({}, {}): {}\n".format(self.range[0], self.range[1], self.values)
        if self.left:
            ans += self.left.__repr__()
        if self.right:
            ans += self.right.__repr__()
        return ans


import bisect

MOD = 998244353
N = int(input())
robots = []
for _ in range(N):
    x, d = map(int, input().split())
    robots.append((-x, -d))
robots.sort()
dp = [0] * (N + 1)
dp[0] = 1
st = SegmentTree([N] * (N + 1))
for i, (x, d) in enumerate(robots):
    lo = bisect.bisect_right(robots, (x + d, 10 ** 10), hi=i)
    lo = min(lo, st.query(lo, i, "min"))
    st.update(i, lo)
    dp[i + 1] += (dp[i] + dp[lo]) % MOD
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
size = 1 << 18
dat = [-mod] * (size * 2 - 1)
def seg_max(a, b, k = 0, l = 0, r = size):
    if r <= a or b <= l:
        return -mod
    if a <= l and r <= b:
        return dat[k]
    vl = seg_max(a, b, k * 2 + 1, l, (l + r) // 2)
    vr = seg_max(a, b, k * 2 + 2, (l + r) // 2, r)
    return max(vl, vr)

def seg_update(i, x):
    i += size - 1
    dat[i] = x
    while i > 0:
        i = (i - 1) // 2
        dat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);

N = int(input())
tmpX = []
for i in range(N):
    x, d = list(map(int, input().split()))
    tmpX.append((x, d))
tmpX.sort()


X, D = [0] * N, [0] * N
for i in range(N):
    X[i] = tmpX[i][0]
    D[i] = tmpX[i][1]

to = [0] * N
for i in range(N):
    seg_update(i, i)

for i in range(N-1, -1, -1):
    ok = i
    ng = N
    while ng - ok > 1:
        mid = (ng + ok) // 2
        if X[i] + D[i] > X[mid]:
            ok = mid
        else :
            ng = mid
    to[i] = seg_max(i, ok+1)
    seg_update(i, to[i])

dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
    dp[i+1] += dp[i]
    dp[i+1] %= mod
    dp[to[i]+1] += dp[i]
    dp[to[i]+1] %= mod
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
size = 1 << 20
dat = [-mod] * (size * 2 - 1)
def seg_max(a, b, k = 0, l = 0, r = size):
    if r <= a or b <= l:
        return -mod
    if a <= l and r <= b:
        return dat[k]
    vl = seg_max(a, b, k * 2 + 1, l, (l + r) // 2)
    vr = seg_max(a, b, k * 2 + 2, (l + r) // 2, r)
    return max(vl, vr)

def seg_update(i, x):
    i += size - 1
    dat[i] = x
    while i > 0:
        i = (i - 1) // 2
        dat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);

N = int(input())
tmpX = []
for i in range(N):
    x, d = list(map(int, input().split()))
    tmpX.append((x, d))
tmpX.sort()


X, D = [0] * N, [0] * N
for i in range(N):
    X[i] = tmpX[i][0]
    D[i] = tmpX[i][1]

to = [0] * N
for i in range(N):
    seg_update(i, i)

for i in range(N-1, -1, -1):
    ok = i
    ng = N
    while ng - ok > 1:
        mid = (ng + ok) // 2
        if X[i] + D[i] > X[mid]:
            ok = mid
        else :
            ng = mid
    to[i] = seg_max(i, ok+1)
    seg_update(i, to[i])

dp = [0] * (N+1)
dp[0] = 1
for i in range(N):
    dp[i+1] += dp[i]
    dp[i+1] %= mod
    dp[to[i]+1] += dp[i]
    dp[to[i]+1] %= mod
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import sys

input=sys.stdin.readline
sys.setrecursionlimit(1000000)

N=int(input())
robot=[]
for i in range(N):
    x,d=map(int,input().split())
    robot.append((x,d))
mod=998244353

robot.sort()
move=[i for i in range(0,N)]
for i in range(0,N):
    x,d=robot[i]
    start=i
    end=N-1
    while end-start>1:
        test=(end+start)//2
        if x+d>robot[test][0]:
            start=test
        else:
            end=test

    if x+d>robot[end][0]:
        move[i]=end
    else:
        move[i]=start


n=N
#####segfunc######
def segfunc(x,y):
    return max(x,y)

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

#####単位元######
ide_ele =0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

chain=[i for i in range(N)]
for _ in range(0,N):
    i=N-1-_
    if move[i]==i:
        chain[i]=i
        update(i,chain[i])
    else:
        chain[i]=query(i+1,move[i]+1)
        update(i,chain[i])

memo=[-1 for i in range(0,N+1)]
memo[N]=1
def dp(num):
    if memo[num]!=-1:
        return memo[num]

    if chain[num]==num:
        memo[num]=(2*dp(num+1))%mod
        return memo[num]
    else:
        memo[num]=(dp(num+1)+dp(chain[num]+1))%mod
        return memo[num]

print(dp(0))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
MOD = 998244353

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n = 2 ** (n-1).bit_length()
        self.data = [ide] * (self.n*2)
        self.func, self.ide = func, ide
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.n
        self.data[i] = x
        while i > 1:
            i //= 2
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.n; r += self.n 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l //= 2; r //= 2
        return res
    
    def get(self, i):
        return self.data[self.n + i]

n = int(input())
xd = [tuple(map(int, input().split())) for _ in range(n)]
xd.sort()
x, d = zip(*xd)

s = SegmentTree(n, lambda x, y: max(x, y), -float("inf"))
for i in range(n)[::-1]:
    r = bisect_left(x, x[i]+d[i])
    s.update(i, max(r-1, s.query(i, r)))

dp = [[0] * 2 for _ in range(n)]
dp[-1][0], dp[-1][1] = 1, 1

for i in range(n-1)[::-1]:
    dp[i][0] = dp[i+1][0] + dp[i+1][1] % MOD
    dp[i][1] = dp[s.get(i)][0]

print(sum(dp[0]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    xd = [list(map(int, input().split())) + [i] for i in range(1, n + 1)]
    mod = 998244353
    INF = 10 ** 10

    xd.sort()
    adj = [[] for _ in range(n + 1)]
    stack = [(INF, 0)]
    for x, d, i in xd:
        while stack[-1][0] <= x:
            stack.pop()
        pi = stack[-1][1]
        adj[pi].append(i)
        stack.append((x + d, i))

    stack2 = [0]
    d = [-1] * (n + 1)
    d[0] = 0
    c = [[] for _ in range(n + 1)]
    order = []
    while stack2:
        u = stack2.pop()
        order.append(u)
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                c[u].append(v)
                stack2.append(v)

    dp = [1] * (n + 1)
    for u in order[::-1]:
        for v in c[u]:
            dp[u] *= dp[v]
            dp[u] %= mod

        dp[u] += 1
        dp[u] %= mod

    ans = dp[0] - 1
    ans %= mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xd = [list(map(int, input().split())) for _ in range(n)]
mod = 998244353
INF = 10 ** 18

xx = [[x, x + d, i] for i, (x, d) in enumerate(xd, 1)]
xx.sort()
adj = [[] for _ in range(n + 1)]
stack = [[INF, 0]]
for l, r, i in xx:
    while stack[-1][0] <= l:
        stack.pop()

    ip = stack[-1][1]
    adj[ip].append(i)
    stack.append([r, i])

stack = [0]
d = [-1] * (n + 1)
d[0] = 0
c = [[] for _ in range(n + 1)]
order = []
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            c[u].append(v)
            stack.append(v)

dp = [1] * (n + 1)
for u in order[::-1]:
    for v in c[u]:
        dp[u] *= dp[v]
        dp[u] %= mod

    dp[u] += 1
    dp[u] %= mod

ans = dp[0] - 1
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xd = [list(map(int, input().split())) for _ in range(n)]
mod = 998244353
INF = 10 ** 18

xx = []
for i, (x, d) in enumerate(xd, 1):
    xx.append([i, x, 0])
    xx.append([i, x + d - 0.5, 1])

xx.sort(key=lambda x: x[1])

adj = [[] for _ in range(n + 1)]
now = {0}
stack = [(INF, 0)]
for i, x, remove in xx:
    if remove:
        now.remove(i)

    else:
        while stack[-1][1] not in now:
            stack.pop()

        px, pi = stack[-1]
        adj[pi].append(i)

        now.add(i)
        stack.append([x, i])

stack = [0]
d = [-1] * (n + 1)
d[0] = 0
c = [[] for _ in range(n + 1)]
order = []
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            c[u].append(v)
            stack.append(v)

dp = [1] * (n + 1)
for u in order[::-1]:
    for v in c[u]:
        dp[u] *= dp[v]
        dp[u] %= mod

    dp[u] += 1
    dp[u] %= mod

ans = dp[0] - 1
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


n = int(input())
xd = [list(map(int, input().split())) for _ in range(n)]
mod = 998244353
INF = 10 ** 18

xx = []
for i, (x, d) in enumerate(xd, 1):
    xx.append([i, x, 0])
    xx.append([i, x + d - 0.5, 1])

xx.sort(key=lambda x: x[1])

adj = [[] for _ in range(n + 1)]
hp = [(INF, 0)]
uf = UnionFind(2 * (n + 1))

for i, x, remove in xx:
    if remove:
        uf.unite(0, i + n + 1)

    else:
        while uf.same(hp[0][1], hp[0][1] + n + 1):
            heappop(hp)

        px, pi = hp[0]
        adj[pi].append(i)

        uf.unite(0, i)
        heappush(hp, (-x, i))

stack = [0]
d = [-1] * (n + 1)
d[0] = 0
c = [[] for _ in range(n + 1)]
order = []
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            c[u].append(v)
            stack.append(v)

dp = [1] * (n + 1)
for u in order[::-1]:
    for v in c[u]:
        dp[u] *= dp[v]
        dp[u] %= mod

    dp[u] += 1
    dp[u] %= mod

ans = dp[0] - 1
ans %= mod
print(ans)