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: Accepted

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

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

mod = 998244353

XD.sort()

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

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

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

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

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

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

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

print(dp[N-1])

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

n, *xd = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
xd = sorted(zip(xd[0::2], xd[1::2]))
xxx = list(map(itemgetter(0), xd)) + [10 ** 10]
ans = [0] * n + [1]
stack = [n]

for i in range(n - 1, -1, -1):
    x, d = xd[i]
    r = x + d
    while r > xxx[stack[-1]]:
        stack.pop()
    ans[i] = (ans[i + 1] + ans[stack[-1]]) % MOD
    stack.append(i)
print(ans[0])

Submission status: Accepted

Solution code:
#input
N = int(input())
XD = []
for _ in range(N):
    x, d = map(int, input().split())
    XD.append((x, x+d))

MOD = 998244353

# process
XD.sort(reverse=True)

sei = [(10**9, 0)]
pattern = [0]*(N+1)
pattern[0] = 1
for i, (s, e) in enumerate(XD):
    ei = i
    while e > sei[-1][0]:
        _, ei = sei.pop()
    sei.append((s, ei))
    pattern[i+1] = (pattern[i] + pattern[ei]) % MOD

# output
print(pattern[-1])

Submission status: Accepted

Solution code:
mod = 998244353

N, *XD = map(int, open(0).read().split())

XD = sorted(zip(*[iter(XD)] * 2), reverse=True)

S = [(1e10, 0)]
dp = [1] + [0] * N
for i, (x, d) in enumerate(XD):
    j = i
    while S[-1][0] < x + d:
        _, j = S.pop()
    S.append((x, j))
    dp[i + 1] = (dp[i] + dp[j]) % mod

print(dp[-1])

Submission status: Accepted

Solution code:
from collections import deque


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
MOD = 998244353

info = [(10**10, 10 ** 10)] + sorted(info, reverse=True)
dp = [0] * (n + 1)
dp[0] = 1

q = deque([])
for i in range(n):
    if sum(info[i + 1]) <= info[i][0]:
        # 抜かさないとき
        dp[i + 1] = 2 * dp[i]
        dp[i + 1] %= MOD
        q.append((i, info[i]))
    else:
        # 抜かすとき
        if sum(info[i + 1]) <= q[-1][1][0]:
            dp[i + 1] = dp[i] + dp[q[-1][0]]
            dp[i + 1] %= MOD
        else:
            while q:
                q.pop()
                if sum(info[i + 1]) <= q[-1][1][0]:
                    dp[i + 1] = dp[i] + dp[q[-1][0]]
                    dp[i + 1] %= MOD
                    break
print(dp[-1] % MOD)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

MOD = 998244353
input = sys.stdin.readline


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

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

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

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


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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from operator import itemgetter
import bisect
def main():
    input = sys.stdin.readline
    N = int(input())
    XD = [tuple(map(int, input().split())) for _ in range(N)]
    MOD = 998244353

    XD.sort(key=itemgetter(0))
    X = [xd[0] for xd in XD]
    segtree = SegmentTree(N+1)
    for i in range(N-1,-1,-1):
        x, d = XD[i]
        j = bisect.bisect_left(X, x+d, i)
        end = max(j-1, segtree.query(i, j))
        segtree.update(i, end)

    dp = [None] * (N+1)
    dp[N] = Mint(1, MOD)
    for i in range(N-1,-1,-1):
        dp[i] = dp[i+1] + dp[segtree.get(i) + 1]
    print(dp[0])

class Mint:
    def __init__(self, value=0, mod=10**9+7):
        self.value = ((value % mod) + mod) % mod
        self.mod = mod

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, self.mod
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        return (u + self.mod) % self.mod

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.val
    def __neg__(self): return Mint(-self.value, self.mod)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % self.mod
        return self
    def __add__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other) + self.mod) % self.mod
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % self.mod
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other, self.mod)
        self *= other.inverse
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj //= self
        return new_obj

class SegmentTree:
    def __init__(self, n=None, f=max, identity_factory=int, initial_values=None):
        assert(n or initial_values)
        size = n if n else len(initial_values)
        d = [identity_factory() for _ in range(2 * size + 1)]
        self.__n, self.__d, self.__f, self.__e = size, d, f, identity_factory
        if initial_values:
            for i, v in enumerate(initial_values): d[size + i] = v
            for i in range(size - 1, 0, -1): d[i] = f(d[i<<1], d[i<<1|1])

    def get(self, index):
        return self.__d[index + self.__n]

    def update(self, index, value):
        i, d, f = index + self.__n, self.__d, self.__f
        if d[i] == value: return
        d[i] = value
        while i:
            i = i >> 1
            d[i] = f(d[i<<1], d[i<<1|1])

    def add(self, index, value):
        self.update(index, self.__f(self.__d[index + self.__n], value))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__e()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__d, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l+1
            if r & 1: ans, r = f(d[r-1], ans), r-1
            l, r = l >> 1, r >> 1
        return ans

    def bisect_left(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        i, n, f, d, v = 1, self.__n, self.__f, self.__d, self.__e()
        while i < n:
            if func(f(v, d[i<<1])): v, i = f(v, d[i<<1]), i<<1|1
            else: i = i<<1
        return i - n

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from operator import itemgetter
import bisect
def main():
    input = sys.stdin.readline
    N = int(input())
    XD = [tuple(map(int, input().split())) for _ in range(N)]
    MOD = 998244353

    XD.sort(key=itemgetter(0))
    X = [xd[0] for xd in XD]
    segtree = SegmentTree(N+1)
    for i in range(N-1,-1,-1):
        x, d = XD[i]
        j = bisect.bisect_left(X, x+d, i)
        end = max(j-1, segtree.query(i, j))
        segtree.update(i, end)

    dp = [Mint(0, MOD) for _ in range(N+1)]
    dp[N] = Mint(1, MOD)
    for i in range(N-1,-1,-1):
        dp[i] += dp[i+1]
        dp[i] += dp[segtree.get(i) + 1]
    print(dp[0])

class Mint:
    def __init__(self, value=0, mod=10**9+7):
        self.value = ((value % mod) + mod) % mod
        self.mod = mod

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, self.mod
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        return (u + self.mod) % self.mod

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.val
    def __neg__(self): return Mint(-self.value, self.mod)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % self.mod
        return self
    def __add__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other) + self.mod) % self.mod
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % self.mod
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other, self.mod)
        self *= other.inverse
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj //= self
        return new_obj

class SegmentTree:
    def __init__(self, n=None, f=max, identity_factory=int, initial_values=None):
        assert(n or initial_values)
        size = n if n else len(initial_values)
        d = [identity_factory() for _ in range(2 * size + 1)]
        self.__n, self.__d, self.__f, self.__e = size, d, f, identity_factory
        if initial_values:
            for i, v in enumerate(initial_values): d[size + i] = v
            for i in range(size - 1, 0, -1): d[i] = f(d[i<<1], d[i<<1|1])

    def get(self, index):
        return self.__d[index + self.__n]

    def update(self, index, value):
        i, d, f = index + self.__n, self.__d, self.__f
        if d[i] == value: return
        d[i] = value
        while i:
            i = i >> 1
            d[i] = f(d[i<<1], d[i<<1|1])

    def add(self, index, value):
        self.update(index, self.__f(self.__d[index + self.__n], value))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__e()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__d, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l+1
            if r & 1: ans, r = f(d[r-1], ans), r-1
            l, r = l >> 1, r >> 1
        return ans

    def bisect_left(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        i, n, f, d, v = 1, self.__n, self.__f, self.__d, self.__e()
        while i < n:
            if func(f(v, d[i<<1])): v, i = f(v, d[i<<1]), i<<1|1
            else: i = i<<1
        return i - n

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

MOD = 998244353

n = int(input())
robot = []
pos = []

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

robot = sorted(robot, key=lambda y: y[0])
pos = sorted(pos)


def init(init_val):
    for i in range(n):
        MI[i+num-1] = init_val[i]
        MA[i+num-1] = init_val[i]
    for i in range(num-2, -1, -1):
        MI[i] = min(MI[2*i+1], MI[2*i+2])
        MA[i] = max(MA[2*i+1], MA[2*i+2])


def update(k, x):
    k += num-1
    MI[k] = x
    MA[k] = x
    while k+1:
        k = (k-1)//2
        MI[k] = min(MI[k*2+1], MI[k*2+2])
        MA[k] = max(MA[k*2+1], MA[k*2+2])


def rangemax(p, q):
    if q <= p:
        return -1
    p += num-1
    q += num-2
    res = -1
    while q-p > 1:
        if p & 1 == 0:
            res = max(res, MA[p])
        if q & 1 == 1:
            res = max(res, MA[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res, MA[p])
    else:
        res = max(max(res, MA[p]), MA[q])
    return res


# n:リスト長
num = 2**(n-1).bit_length()
MI = [1 << 100]*2*num
MA = [-1]*2*num

r = []
for x, d in robot:
    r.append(bisect_left(pos, d))

init(r)

s = [0]*n

for x in range(n-1, -1, -1):
    right_max = rangemax(x, r[x])
    s[x] = right_max
    update(x, right_max)

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

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

print(dp[0])

Submission status: Accepted

Solution code:
from bisect import bisect_left
MOD = 998244353

n = int(input())
robot = []
pos = []

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

robot = sorted(robot, key=lambda y: y[0])
pos = sorted(pos)


def init(init_val):
    for i in range(n):
        MI[i+num-1] = init_val[i]
        MA[i+num-1] = init_val[i]
    for i in range(num-2, -1, -1):
        MI[i] = min(MI[2*i+1], MI[2*i+2])
        MA[i] = max(MA[2*i+1], MA[2*i+2])


def update(k, x):
    k += num-1
    MI[k] = x
    MA[k] = x
    while k+1:
        k = (k-1)//2
        MI[k] = min(MI[k*2+1], MI[k*2+2])
        MA[k] = max(MA[k*2+1], MA[k*2+2])


def rangemin(p, q):
    if q <= p:
        return 1 << 100
    p += num-1
    q += num-2
    res = 1 << 100
    while q-p > 1:
        if p & 1 == 0:
            res = min(res, MI[p])
        if q & 1 == 1:
            res = min(res, MI[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res, MI[p])
    else:
        res = min(min(res, MI[p]), MI[q])
    return res


def rangemax(p, q):
    if q <= p:
        return -1
    p += num-1
    q += num-2
    res = -1
    while q-p > 1:
        if p & 1 == 0:
            res = max(res, MA[p])
        if q & 1 == 1:
            res = max(res, MA[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res, MA[p])
    else:
        res = max(max(res, MA[p]), MA[q])
    return res


# n:リスト長
num = 2**(n-1).bit_length()
MI = [1 << 100]*2*num
MA = [-1]*2*num

r = []
for x, d in robot:
    r.append(bisect_left(pos, d))

init(r)

s = [0]*n

for x in range(n-1, -1, -1):
    right_max = rangemax(x, r[x])
    s[x] = right_max
    update(x, right_max)

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

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

print(dp[0])

Submission status: Accepted

Solution code:
MOD = 998244353
import bisect
import sys
input = sys.stdin.buffer.readline
N = int(input())

XR = []
for i in range(N):
    X,D = map(int,input().split())
    XR.append((X,X+D))

XR.sort()
X, R = map(list,zip(*XR))

#inds = np.searchsorted(X,R,side='left')-1
inds = [bisect.bisect_left(X,r)-1 for r in R]

l = 2**((N-1).bit_length())
data = [0] * l + inds + [0] * (l-N)
for i in range(l-1,0,-1):
    data[i] = max(data[2*i],data[2*i+1])

def set(i,val):
    i += l
    data[i] = val
    i //= 2
    while i > 0:
        data[i] = max(data[2*i], data[2*i+1])
        i //= 2
def get(i,j):
    i += l
    j += l
    s = data[i]
    while j-i > 0:
        if i & 1:
            s = max(s,data[i])
            i += 1
        if j & 1:
            s = max(s,data[j-1])
            j -= 1
        i//=2
        j//=2
    return s

for i in range(N-1,-1,-1):
    set(i,get(i,inds[i]+1))
#print(data)
#print(data[l:])

dp = [0]*(N+1)
dp[N] = 1
for i in range(N-1,-1,-1):
    dp[i] = (dp[i+1] + dp[data[l+i]+1]) % MOD
#print(dp)
print(dp[0])

Submission status: Accepted

Solution code:
import sys
import bisect
from collections import deque
sys.setrecursionlimit(10 ** 7)

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


N = int(readline())
MOD = 998244353

XD = [[int(x) for x in readline().split()] for _ in range(N)]
XD.sort()
#X = [x for x, _ in XD]

NXT = deque()
E = [[] for _ in range(N)]

for i in range(N - 1, -1, -1):
    x, d = XD[i]

    while NXT:
        j, nx = NXT.pop()

        if nx < x + d:
            E[i].append(j)
        else:
            NXT.append((j, nx))
            break

    NXT.append((i, x))


def dfs(i):
    rtn = 1
    for v in E[i]:
        rtn *= dfs(v)
        rtn %= MOD
    return rtn + 1


ans = 1
for i, x in NXT:
    ans *= dfs(i)
    ans %= MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

n = int(input())
xd = []
# Add sentinel
places = [(10**12, 0)]
for _ in range(n):
    x, d = [int(item) for item in input().split()]
    xd.append((x, d))

xd.sort(reverse=True)
dp = [0] * (n + 1)
dp[0] = 1
for i, (x, d) in enumerate(xd):
    frm = x
    too = x + d 
    too_idx = i
    while too > places[-1][0]:
        _, too_idx = places.pop()
    places.append((frm, too_idx))
    dp[i + 1] = dp[i] + dp[too_idx]
    dp[i + 1] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import bisect
MOD = 998244353

n = int(input())
xd = []
places = [(10**12, 0)]
for _ in range(n):
    x, d = [int(item) for item in input().split()]
    xd.append((x, d))

xd.sort(reverse=True)
affect = [0] * (n + 1)
dp = [0] * (n + 1)
dp[0] = 1
for i, (x, d) in enumerate(xd):
    frm = x
    too = x + d 
    too_idx = i
    while too > places[-1][0]:
        _, too_idx = places.pop()
    places.append((frm, too_idx))
    dp[i + 1] = dp[i] + dp[too_idx]
    dp[i + 1] %= MOD

print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
x = [list(map(int,input().split())) for i in range(n)] + [[11**9]]
x.sort(lambda x:x[0])
a = x[:-2]
y = a + [n]
a += [2,1]
for i in range(n-2,-1,-1):
  y[i] = i+1
  while x[y[i]][0] < sum(x[i]):
    y[i] = y[y[i]]
  a[i] = (a[i+1]+a[y[i]]) % 998244353
print(a[0])

Submission status: Accepted

Solution code:
n = int(input())
x = [list(map(int,input().split())) for i in range(n)] + [[10**10,]]
x.sort(key=lambda x:x[0])
a = [0]*(n-1)
y = a + [n]
a += [2,1]
for i in range(n-2,-1,-1):
  y[i] = i+1
  while x[y[i]][0] < sum(x[i]):
    y[i] = y[y[i]]
  a[i] = (a[i+1]+a[y[i]]) % 998244353
print(a[0])

Submission status: Accepted

Solution code:
n = int(input())
x = [list(map(int,input().split())) for i in range(n)]
x.sort(key=lambda x:x[0])
x.append([2*10**9+1,0])
y = [0]*(n-1) + [n-1]
a = [0]*(n-1) + [2]
for i in range(n-2,-1,-1):
  j = i+1
  while x[j][0] < sum(x[i]):
    j = y[j] + 1
  y[i] = j - 1
for i in range(n-2,-1,-1):
  a[i] = a[y[i]+1] if y[i]+1 < n else 1
  a[i] = (a[i]+a[i+1]) % 998244353
print(a[0])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left

class SegTree:
    def __init__(self, a):
        self.padding = -float('inf')
        self.n = len(a)
        self.N = 2 ** (self.n - 1).bit_length()
        self.data = [self.padding]*(self.N - 1) + a + [self.padding]*(self.N - self.n)
        for i in range(2 * self.N - 2, 0, -2):
            self.data[(i - 1) // 2] = max(self.data[i], self.data[i - 1])
    
    def __len__(self):
        return self.n
    
    def __getitem__(self, key):
        return self.data[self.N - 1 + key]

    def __setitem__(self, i, value):
        self._update(i, value)
    
    def _update(self, i, x):
        idx = self.N - 1 + i
        self.data[idx] = x
        while idx != 0:
            idx = (idx - 1) // 2
            self.data[idx] = max(self.data[2 * idx + 1], self.data[2 * idx + 2])
    
    def max(self, i, j):
        # [i, j)
        if i == j: #今回のみの措置
            return self.data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 + 1 < idx2:
                if idx1 % 2 == 0: # idx1が偶数
                    result = max(result, self.data[idx1])
                if idx2 % 2 == 1: # idx2が奇数
                    result = max(result, self.data[idx2])
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                result = max(result, self.data[idx1])
            else: # idx1 + 1 == idx2
                result = max(result, self.data[idx1], self.data[idx2])
            
            return result

n = int(input())
x_d = []
for _ in range(n):
    x_d.append(tuple(map(int, input().split())))
x_d.sort(key=lambda t: t[0])
x = [t[0] for t in x_d]
xplusd = [t[0] + t[1] for t in x_d]
shortright = [bisect_left(x, xpdi) for xpdi in xplusd]
right = SegTree([t for t in shortright])
for i in range(n - 1, -1, -1):
    right[i] = right.max(i, right[i])
dp = [None] * n
dp.append(1)
for i in range(n - 1, -1, -1):
    dp[i] = (dp[i + 1] + dp[right[i]]) % 998244353
print(dp[0])

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
mod = 998244353
rs = []
xs = []
for _ in range(N):
  x, d = map(int, input().split())
  rs.append((x, d))
  xs.append(x)
rs.sort()
xs.sort()

class SegTree:
  def segfunc(self, x, y):
    return max(x, y) #ここ判定関数（ただし結合則があるもの）
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res

seg = SegTree(N, 0, [0] * N)

for i in range(N - 1, -1, -1):
  j = bl(xs, rs[i][0] + rs[i][1])
  if j >= N: j -= 1
  else: j -= ((rs[i][0] + rs[i][1]) <= xs[j])
  seg.update(i, max(0, j, seg.query(i, j + 1)))
  #print((i, j), rs[i])

dp = [0] * (N + 1)
dp[0] = 1
for i in range(N):
  j = seg.query(i, i + 1)
  dp[i + 1] += dp[i]
  dp[i + 1] %= mod
  dp[j + 1] += dp[i]
  dp[j + 1] %= mod
  #print(rs[i], dp)
print(dp[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

class SegTree:
    """
    セグメント木
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        # 初期化の値が決まっている場合
        if A:
            # 1段目(最下段)の初期化
            for i in range(n):
                self.tree[n2+i] = A[i]
            # 2段目以降の初期化
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

N = INT()
XD = []
for _ in range(N):
    x, d = MAP()
    XD.append((x, d))

XD.sort()
X, _ = zip(*XD)
X = list(X)
X += [INF]
# st[i] := ロボットiが動くことで、何番目のロボットまで連動して動くか
st = SegTree(N+1, max, -INF)
st.update(N, N)
for i in range(N-1, -1, -1):
    x, d = XD[i]
    j = bisect_left(X, x+d)
    mx = st.query(i, j)
    st.update(i, max(i, mx))

# dp[i] := i番目のロボットまで(後ろから)見て、そこから後ろの状態の通り数
dp = [0] * (N+1)
dp[N] = 1
for i in range(N-1, -1, -1):
    # i番目を動かさない遷移(1つ前の状態全てを使える)
    dp[i] += dp[i+1]
    # i番目を動かす遷移(自分が影響する範囲は自由に変えられないので、その1つ前から持ってくる)
    dp[i] += dp[st.get(i)+1]
    dp[i] %= MOD
ans = dp[0]
print(ans)