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:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = 998244353 ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [tuple(map(int,input().split())) for i in range(n)]
XD.append((-10**10,inf))
XD.sort()

now = 0
def dfs(node):
  global now
  pro = 1
  while now < n :
    if XD[now+1][0] < XD[node][0] + XD[node][1]:
      now += 1
      pro *= dfs(now)
      pro %= mod
    else:break
  return pro + 1
ans = dfs(0)
print((ans-1)%mod)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left
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 operator import add
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] * n
    A[-1] = 1

    def compose(f, g):
        return f if f != INF else g

    def act(f, x):
        return f if f != INF else x

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

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

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.buffer.readline().rstrip()
from bisect import bisect_left
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 operator import add
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] * n
    A[-1] = 1

    def compose(f, g):
        return f if f != INF else g

    def act(f, x):
        return f if f != INF else x

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

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

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.buffer.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 operator import add
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] * n
    A[-1] = 1

    def compose(f, g):
        return f if f != INF else g

    def act(f, x):
        return f if f != INF else x

    tree = LazySegmentTree(A, add, 0, compose, INF, act)
    for i in range(n - 2, -1, -1):
        x = tree.sum(i + 1, n)
        tree.range_act(i, i + 1, (x + 1) % MOD) # pointwise update
        x, d = XD[i]
        if X[-1] < x + d:
            j = n
        elif X[0] >= x + d:
            j = 0
        else:
            l, r = 0, n - 1
            while r - l > 1:
                m = (l + r) // 2
                if X[m] < x + d:
                    l = m
                else:
                    r = m
            j = r
        tree.range_act(i + 1, j, 0)

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

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = 998244353 ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [tuple(map(int,input().split())) for i in range(n)]
XD.append((-10**10,inf))
XD.sort()

now = 0
visited1 = [] 
def dfs(node):
  visited1.append(node)

  global now
  pro = 1
  while now < n :
    if XD[now+1][0] < XD[node][0] + XD[node][1]:
      now += 1
      pro *= dfs(now)
      pro %= mod
    else:break
  return pro + 1
ans = dfs(0)
print((ans-1)%mod)

Submission status: Accepted

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

n = int(input())
XD = [tuple(map(int,input().split())) for i in range(n)]
XD.append((-10**10,inf))
XD.sort()

def dfs(node):
  res = 1
  i = node + 1
  while i < n+1:
    if XD[i][0] < XD[node][0] + XD[node][1]:
      pro,i = dfs(i)
      res *= pro
      res %= mod
    else: break

  return res + 1 , i
print((dfs(0)[0]-1)%mod)

Submission status: Accepted

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

n = int(input())
XD = [(-10**10,inf)]
for i in range(n):
  x,d = map(int,input().split())
  XD.append((x,d))
XD.sort()

def dfs(node):
  res = 1
  i = node + 1
  while i < n+1:
    if XD[i][0] < XD[node][0] + XD[node][1]:
      pro,i = dfs(i)
      res *= pro
      res %= mod
    else: break

  return res + 1 , i
print((dfs(0)[0]-1)%mod)

Submission status: Accepted

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

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

Submission status: Accepted

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

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)
#print(xs, a)
for l in range(N - 1, -1, -1):
  r = bl(xs, a[l][0] + a[l][1])
  mx = max(l, seg.query(l, r))
  seg.update(l, mx)
  #print(mx, a[i][0] + a[i][1])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 998244353
input = lambda:sys.stdin.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        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 = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._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 = [xd[0] for xd in XD]

    tree = SegmentTree([-INF] * n, max, -INF)
    for i in range(n - 1, -1, -1):
        x, d = XD[i]
        j = bisect_left(X, x + d)
        tree.update(i, max(j, tree.sum(i + 1, j)))

    dp = [0] * (n + 1)
    dp[n] = 1
    for i in range(n - 1, -1, -1):
        dp[i] += dp[i + 1]
        dp[i] += dp[tree[i]]
        dp[i] %= MOD
        
    print(dp[0])
resolve()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left,bisect_right
input = sys.stdin.readline
ide = 0
def func(a,b):
  return max(a,b)
class SegmentTree:
  def __init__(self,ls,commutative = True):
    if commutative == True:
      self.n = len(ls)
      self.tree = [ide for i in range(self.n)]+ls
    else:
      self.n = 2**((len(ls)-1).bit_length())
      self.tree = [ide for i in range(self.n)]+ls+[ide for i in range(self.n-len(ls))]
    for i in range(1,self.n)[::-1]:
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])
  def getall(self):
    return self.tree[1]
  def get(self,l,r):
    lret = ide
    rret = ide
    l += self.n
    r += self.n
    while l < r:
      if l&1:
        lret = func(lret,self.tree[l])
        l += 1
      if r&1:
        rret = func(self.tree[r-1],rret)
      l >>= 1
      r >>= 1
    ret = func(lret,rret)
    return ret
  def update(self,i,x):
    i += self.n
    self.tree[i] = x
    while i > 1:
      i >>= 1
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])
n = int(input())
xd = [list(map(int,input().split())) for i in range(n)]
mod = 998244353
xd.sort()
xls = list(zip(*xd))[0]
rls = [0]*n
st = SegmentTree(rls)
for i in range(n)[::-1]:
  idx = bisect_left(xls,xd[i][0]+xd[i][1])-1
  x = st.get(i,idx+1)
  st.update(i,max(i,x))
dp = [0]*(n)
dp[-1] = 2
for i in range(n-1)[::-1]:
  x = st.get(i,i+1)
  if x == n-1:
    dp[i] = dp[i+1]+1
  else:
    dp[i] = dp[i+1]+dp[x+1]
  dp[i] %= mod
print(dp[0])

Submission status: Accepted

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

    st = []
    st.append((n, 2e9))

    for i in range(n-1, -1, -1):

        while st[-1][1] < x[i] + d[i]:
            st.pop()
        next[i] = st[-1][0]
        st.append((i, x[i]))

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
XD = [tuple(map(int,input().split())) for i in range(N)]
XD.sort()
MOD = 998244353
ns = [-1] * N

for i,(x,d) in reversed(list(enumerate(XD))):
    tmp = i
    while tmp < N-1:
        nx,_ = XD[tmp+1]
        if nx < x+d:
            tmp = ns[tmp+1]
        else:
            break
    ns[i] = tmp

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

Submission status: Accepted

Solution code:
def main():
    mod = 998244353
    n = int(input())
    ab = sorted([tuple(map(int, input().split())) for _ in [0]*n])
    next_idx = [-1]*n
    for i in range(n-1, -1, -1):
        dist = sum(ab[i])
        now = i
        while now < n-1:
            a1, b1 = ab[now+1]
            if a1 < dist:
                now = next_idx[now+1]
            else:
                break
        next_idx[i] = now
    dp = [0]*(n+1)
    dp[n] = 1
    for i in range(n-1, -1, -1):
        dp[i] = (dp[i+1]+dp[next_idx[i]+1]) % mod
    print(dp[0])
 
 
main()

Submission status: Accepted

Solution code:
import bisect


class SegTree:
    def __init__(self, n):
        self.n = n
        self.s = 1
        while self.s < self.n:
            self.s <<= 1
        self.mins = [1 << 30] * (self.s * 2)

    def update(self, i, val):
        i += self.s
        self.mins[i] = val
        i >>= 1
        while i:
            self.mins[i] = min(self.mins[i * 2], self.mins[i * 2 + 1])
            i >>= 1

    def min(self, l, r):
        l += self.s
        r += self.s
        res = self.mins[0]
        while l <= r:
            if l & 1:
                res = min(res, self.mins[l])
                l += 1
            if not r & 1:
                res = min(res, self.mins[r])
                r -= 1
            l >>= 1
            r >>= 1
        return res


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 = SegTree(N)
for i, (x, d) in enumerate(robots):
    lo = bisect.bisect_right(robots, (x + d, 0), hi=i)
    lo = min(lo, st.min(lo, i))
    st.update(i, lo)
    dp[i + 1] += (dp[i] + dp[lo]) % MOD
print(dp[-1])

Submission status: Accepted

Solution code:
MOD = 998244353
N = int(input())
robots = []
for _ in range(N):
    x, d = map(int, input().split())
    robots.append((x, d))
robots.sort(reverse=True)
dp = [0] * (N + 1)
los = [N] * (N + 1)
dp[0] = 1
los[0] = 0
for i, (x, d) in enumerate(robots):
    lo = i
    while lo > 0 and robots[lo - 1][0] < x + d:
        lo = los[lo]
    los[i + 1] = lo
    dp[i + 1] += (dp[i] + dp[lo]) % MOD
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

mod = 998244353

# segment tree
def init_max(init_max_val, n):
    #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

#####単位元######
ide_ele_max = -1

#num_max:n以上の最小の2のべき乗
num_max = 1 << 18
seg_max=[ide_ele_max]*2*num_max



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):
    to[i] = i
init_max(to, N)

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] = query_max(i, ok+1)
    update_max(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: Accepted

Solution code:
from collections import deque


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

dp = [0] * (n + 1)
dp[0] = 1
q = deque([])

for i in range(n):
    # 起動しない場合
    dp[i + 1] += dp[i]
    
    # 起動する場合
    x, d = info[i]
    l, r = x, x + d
    num = 1
    while True:
        if not q:
            q.append((l, num))
            break
        tmp_l, tmp_num = q.pop()
        if r > tmp_l:
            num = tmp_num + num
        else:
            q.append((tmp_l, tmp_num))
            q.append((l, num))
            break
    num = q[-1][1]
    dp[i + 1] += dp[i + 1 - num]
    dp[i + 1] %= MOD
    
print(dp[-1])

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

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

dp=[0 for i in range(0,N+1)]
dp[N]=1
for j in range(0,N):
    i=N-1-j
    if chain[i]==i:
        dp[i]=(2*dp[i+1])%mod
    else:
        dp[i]=(dp[i+1]+dp[chain[i]+1])%mod

print(dp[0])

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right
input = lambda: sys.stdin.readline()
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 >>= 1
            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 >>= 1; r >>= 1
        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)))

dp1, dp2 = [0] * n, [0] * n
dp1[-1], dp2[-1] = 1, 1

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

print((dp1[0] + dp2[0]) % MOD)

Submission status: Accepted

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

    xx = [(x, x + d, i) for i, (x, d) in enumerate(xd, 1)]
    xx.sort()
    c = [[] 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]
        c[ip].append(i)
        stack.append((r, i))

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

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

    for v in c[0]:
        dp[0] *= dp[v]
        dp[0] %= mod

    ans = dp[0]
    print(ans)


if __name__ == "__main__":
    main()