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
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class SegTree:
        def __init__(self,N,ide,segfunc=min):
            self.ide_ele = ide
            """
            ex)
             最小値のセグ木 → +inf
              和のセグ木 → 0
              積のセグ木 → 1
              gcdのセグ木 → 0
            """
            
            self.segfunc=segfunc
            
            #num:N以上の最小の2のべき乗
            self.num =2**(N-1).bit_length()
            self.seg=[self.ide_ele]*2*self.num

        #リストで初期化する
        def setL(self,init_val):
            #init_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]) 


        #k番目の値をxに更新
        def update(self,k,x):
            k += self.num-1
            self.seg[k] = x
            while k:
                k = (k-1)//2
                self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])


        #[p,q)の区間に対するクエリへの応答
        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

    mod=998244353
    N=I()
    X=[0]*N
    D=[0]*N
    
    for i in range(N):
        X[i],D[i]=MI()
    
    X,D=zip(*sorted(zip(X,D)))
    
    dp=[0]*(N+1)
    """
    dp[i]はi番目まで見たときと通り数，後ろから見てく．
    i番目を動かさないならば，dp[i+1]
    i番目を動かすならば，連鎖していき，影響が出ないところまで見る
    この連鎖分をセグ木で事前計算しておく．
    """
    seg=SegTree(N,0,max)
    seg.setL(range(N))
    # セグ木は，何番目まで影響するか，を持つ
    
    import bisect 
    
    for i in range(N-1,-1,-1):
        t=X[i]+D[i]
        num=bisect.bisect_left(X,t)
        l=i
        r=num
        M=seg.query(l,r)
        seg.update(i,M)
        
    dp[-1]=1
    for i in range(N-1,-1,-1):
        temp=seg.query(i,i+1)
        dp[i]=(dp[i+1]+dp[temp+1])%mod
        
    print(dp[0])
    
    # for i in range(N):
    #     print(dp[i])
        

main()

Submission status: Accepted

Solution code:
import bisect
import sys


sys.setrecursionlimit(10**6)
INF = 10**6


class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [- INF] * (2 * N - 1)

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

    def elem(self, i):
        return self.data[self.N + i - 1]

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return - INF
        if a <= l and r <= b:
            return self.data[k]
        val_left = self._query(a, b, 2 * k + 1, l, (l + r) // 2)
        val_right = self._query(a, b, 2 * k + 2, (l + r) // 2, r)
        return max(val_left, val_right)

    def query(self, a, b):
        return self._query(a, b, 0, 0, self.N)


def main():
    MOD = 998244353
    N = int(input())
    robot_list = [list(map(int, input().split())) for _ in range(N)]
    robot_list.sort()  # x座標の昇順でソート
    X = [robot[0] for robot in robot_list]
    D = [robot[1] for robot in robot_list]

    PW_N = 1
    while PW_N < N:
        PW_N *= 2
    next_robot_tree = SegTree(PW_N)
    next_robot_tree.update(N - 1, N)
    for n in range(N - 2, - 1, - 1):
        if X[n] + D[n] <= X[n + 1]:
            next_robot_tree.update(n, n + 1)
        else:
            next_robot = bisect.bisect_left(X, X[n] + D[n])
            next_robot = next_robot_tree.query(n, next_robot)
            next_robot_tree.update(n, next_robot)

    cnt = [0] * (N + 1)
    cnt[0] = 1
    for n in range(N):
        cnt[n + 1] += cnt[n]
        cnt[n + 1] %= MOD
        next_robot = next_robot_tree.elem(n)
        cnt[next_robot] += cnt[n]
        cnt[next_robot] %= MOD
    print(cnt[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 998244353

def init(G, robots, fs, p):
    q = p
    while q < len(robots) and robots[q][0] < robots[p][0] + robots[p][1]:
        if fs[q]:
            G[p].append(q)
            fs[q] = False
            q = init(G, robots, fs, q) - 1
        q += 1
    return q

def calc(G, p, fs):
    fs[p] = False
    if len(G[p]) == 0:
        return 2
    tmp = 1
    for v in G[p]:
        tmp *= calc(G, v, fs)
        tmp %= MOD
    tmp += 1
    return tmp

def main():
    n = int(input())
    robots = [list(map(int, input().split())) for _ in range(n)]
    G = [[] for _ in range(n)]
    robots.sort(key=lambda x: x[0])
    fs = [True]*n
    q = 0
    while q < n:
        if fs[q]:
            fs[q] = False
            init(G, robots, fs, q)
        else:
            q += 1
    fs = [True]*n
    ans = 1
    for i in range(n):
        if fs[i]:
            ans *= calc(G, i, fs)
            ans %= MOD
    print(ans % MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=998244353
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
XD=[]
for i in range(N):
    XD.append(tuple(map(int,input().split())))
XD.sort(key=lambda t: t[0])
X,D=[0]*N,[0]*N
for i in range(N):
    X[i],D[i]=XD[i]

class SegmentTree:
    def __init__(self,n,segfunc,ide_ele):
        self.segfunc=segfunc
        self.ide_ele=ide_ele
        self.num=2**(n-1).bit_length()
        self.dat=[ide_ele]*2*self.num
    
    def init(self,iter):
        for i in range(len(iter)):
            self.dat[i+self.num]=iter[i]
        for i in range(self.num-1,0,-1):
            self.dat[i]=self.segfunc(self.dat[i*2],self.dat[i*2+1])
    
    def update(self,k,x):
        k+=self.num
        self.dat[k]=x
        while k:
            k//=2
            self.dat[k]=self.segfunc(self.dat[k*2],self.dat[k*2+1])
    
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num
        q+=self.num-1
        res=self.ide_ele
        while q-p>1:
            if p&1==1:
                res=self.segfunc(res,self.dat[p])
            if q&1==0:
                res=self.segfunc(res,self.dat[q])
                q-=1
            p=(p+1)//2
            q=q//2
        if p==q:
            res=self.segfunc(res,self.dat[p])
        else:
            res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
        return res

edge=[0]*N
s=SegmentTree(N,lambda a,b: max(a,b),0)
s.init([i for i in range(N)])
for i in range(N-1,-1,-1):
    res0=bisect_left(X,X[i]+D[i])
    res=s.query(i,res0)
    edge[i]=res
    s.update(i,res)
dp=[0]*(N+1)
dp[-1]=1
for i in range(N-1,-1,-1):
    dp[i]+=dp[i+1]+dp[edge[i]+1]
    dp[i]%=MOD
print(dp[0])

Submission status: Accepted

Solution code:
import numpy as np
import collections

Robot = collections.namedtuple('Robot', ['l', 'r'])

N = int(input())
MOD = 998244353
robots = []
for _ in range(N):
    x, d = map(int, input().split())
    robots.append(Robot(x, x + d))
robots.sort()

robots.append(Robot(10**10, 10**10 + 1))
stack = [N]

dp = np.zeros(N + 1, dtype=int)
dp[N] = 1

for i in range(N - 1, -1, -1):
    # For each i, we want the stack contains all the j such that
    # robots[j] is not affected by robot[i], therefore
    # we remove those robots that are intersected with robot[i]
    while robots[stack[-1]].l < robots[i].r:
        stack.pop()

    # dp[i] = dp[i + 1] (not activate robot i) + dp[j] (activate robot i)
    j = stack[-1]
    dp[i] = (dp[i + 1] + dp[j]) % MOD
    stack.append(i)

print(dp[0])

Submission status: Accepted

Solution code:
import bisect


#####segfunc#####
def segfunc(x, y):
    return max(x, y)
#################

#####ide_ele#####
ide_ele = -10000000000
#################


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


mod = 998244353
n = int(input())
x = []
xd = []
for _ in range(n):
    _x, _d = map(int, input().split())
    x.append(_x)
    xd.append((_x, _d))
x.sort()
xd.sort()

init_val = [i for i in range(n + 1)]
seg = SegTree(init_val, segfunc, ide_ele)
dp = [1] * (n + 1)
for i in range(n - 1, -1, -1):
    j = bisect.bisect_left(x, xd[i][0] + xd[i][1])
    k = seg.query(i, j)
    seg.update(i, k)
    dp[i] = dp[i + 1] + dp[k + 1]
    dp[i] %= mod

print(dp[0])

Submission status: Accepted

Solution code:
from functools import reduce
import heapq, sys


input = sys.stdin.readline
N = int(input())
XD = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0], reverse=True)
P = 998244353


class Node:
    def __init__(self, ch):
        self.ch = ch
        if len(self.ch) == 0:
            self.score = 2
        else:
            self.score = reduce(lambda a, b: (a * b) % P, [ch.score for ch in self.ch]) + 1

hq = []  # (x, Node)
heapq.heapify(hq)
for x, d in XD:
    ch = []
    while len(hq) != 0 and hq[0][0] < x+d:
        ch.append(heapq.heappop(hq)[1])
    heapq.heappush(hq, (x, Node(ch)))

ans = reduce(lambda a, b: (a * b) % P, [node.score for x, node in hq])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect
MOD = 998244353
n = int(input())
XD = sorted([list(map(int, input().split())) for _ in range(n)])
X, D = zip(*XD)


C = list(range(n))

class RmaxQ:
    def __init__(self, original):
        self.n = len(original)
        self.INF = -float("inf")
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = max(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            i >>= 1
            self.seg[i] = max(self.seg[2*i], self.seg[2*i+1])
                
    def query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = max(res, self.seg[r-1])
            if l & 1:
                res = max(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res
    
seg = RmaxQ(C)
for i in range(n):
  x, d = XD[n-1-i]
  t = bisect.bisect_left(X, x+d)
  seg.update(n-1-i, max(t, seg.query(n-1-i, t)))

dp = [0]*(n+1)
l = [0]*n
l[-1] = n
dp[-1] = 1
for i in range(n):
  x, d = XD[n-1-i]
  m = bisect.bisect_left(X, x+d)
  t = seg.query(n-1-i, m)
  dp[n-1-i] = dp[n-i] + dp[t]
  dp[n-1-i] %= MOD
print(dp[0])

Submission status: Accepted

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

from heapq import heappush, heappop
from collections import Counter
class HeapSet:
    def __init__(self):
        self.minQue = []
        self.maxQue = []
        self.counter = Counter()

    def insert(self, x):
        heappush(self.minQue, x)
        #heappush(self.maxQue, -x)
        self.counter[x] += 1

    def erase(self, x):
        self.counter[x] -= 1

    def max(self):
        while self.maxQue and self.counter[-self.maxQue[0]] == 0:
            heappop(self.maxQue)
        return -self.maxQue[0] if self.maxQue else None

    def min(self):
        while self.minQue and self.counter[self.minQue[0]] == 0:
            heappop(self.minQue)
        return self.minQue[0] if self.minQue else None

MOD = 998244353
def resolve():
    def dfs(v):
        res = 1
        for to in to_edge[v]:
            res *= dfs(to)
            res %= MOD
        return res +1

    N = int(input())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    AB.sort()
    st = HeapSet()
    to_edge = [[] for _ in range(N)]
    # treeを作成
    for i in range(N-1, -1, -1):
        x = AB[i][0] # 初期位置
        d = AB[i][1] # 移動距離

        while st.min() and st.min()[0] < x + d:
            to_edge[i].append(st.min()[1])
            st.erase(st.min())
        st.insert((x,i)) # 初期位置、頂点番号

    ans = 1
    for (x, v) in st.minQue:
        ans *= dfs(v)
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from bisect import bisect_left

class SegTree:
    def __init__(self, raw_data):
        n = len(raw_data)
        self.size = 1 << (n.bit_length()) # 葉の要素数
        self.data = [0] * (2*self.size)
        self.build(raw_data)

    def build(self, raw_data):
        for i, x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1, 0, -1):
            x = self.data[2*i]
            y = self.data[2*i+1]
            self.data[i] = x if x > y else y # ここを変更
    
    def update(self, i, x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[2*i]
            y = self.data[2*i+1]
            self.data[i] = x if x > y else y # ここを変更
            i >>= 1
    
    def get_data(self, i):
        return self.data[i+self.size]
    
    # これを変更
    def get_max(self, L, R):
        L += self.size
        R += self.size + 1
        x = 0
        while L < R:
            if L & 1:
                y = self.data[L]
                if x < y: x = y
                L += 1
            if R & 1:
                R -= 1
                y = self.data[R]
                if x < y: x = y
            L >>= 1
            R >>= 1
        return x

N = int(input())
robots = sorted([tuple(map(int, input().split())) for _ in range(N)])
X, D = zip(*robots)
mod = 998244353

affects = [0] + [bisect_left(X, x+d) for x, d in robots]
seg = SegTree(affects)

S = [0] * len(affects)
for n in range(N, 0, -1):
    affect = affects[n]
    x = seg.get_max(n, affect)
    S[n] = x
    seg.update(n, x)

dp = [0] * (N+1)
dp[0] = 1
dp_cum = [1] * (N+1)
for n, r in enumerate(S[1:], 1):
    dp[r] += dp_cum[n-1]
    dp[r] %= mod
    dp_cum[n] = dp_cum[n-1] + dp[n]
    dp_cum[n] %= mod
print(dp_cum[-1])

Submission status: Accepted

Solution code:
MOD=998244353
import bisect
N=int(input())

xdlist=[]
for _ in range(N):
  x,d=map(int,input().split())
  xdlist.append((x,d-0.5))
xdlist.sort()
#print(xdlist)

class SegTree:
  #init(init_val, ide_ele): 配列init_valで初期化 O(N)
  def __init__(self, init_val, segfunc, ide_ele):
    #init_val: 配列の初期値
    #segfunc: 区間にしたい操作
    #ide_ele: 単位元
    #n: 要素数
    #num: n以上の最小の2のべき乗
    #tree: セグメント木(1-index)
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    # 配列の値を葉にセット
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    # 構築していく
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  #update(k, x): k番目の値をxに更新 O(logN)
  def update(self, k, x):
    #k番目の値をxに更新
    #k: index(0-index)
    #x: update value
    k += self.num
    self.tree[k] = x
    while k > 1:
      self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
      k >>= 1

  #query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
  def query(self, l, r):
    #[l, r)のsegfuncしたものを得る
    #l: index(0-index)
    #r: index(0-index)
    res = self.ide_ele
    l += self.num
    r += self.num
    while l < r:
      if l & 1:
        res = self.segfunc(res, self.tree[l])
        l += 1
      if r & 1:
        res = self.segfunc(res, self.tree[r - 1])
      l >>= 1
      r >>= 1
    return res
  
def segfunc(x,y):
  return max(x,y) #最大値
ide_ele=-float("inf") #最大値
seg=SegTree([-float("inf")]*N, segfunc, ide_ele)

for i in reversed(range(N)):
  x,d=xdlist[i]
  right=x+d
  pos=bisect.bisect(xdlist,((x+d,float("inf"))))
  
  #print(pos)  
  if pos==i+1:
    seg.update(i,i)
  else:
    max_pos=seg.query(i+1,pos)
    seg.update(i,max_pos)
    
dp=[2]*N
for i in reversed(range(N-1)):
  dp[i]=dp[i+1]
  right=seg.query(i,i+1)
  if right<N-1:
    dp[i]+=dp[right+1]
  else:
    dp[i]+=1
  dp[i]%=MOD
  
#print(dp)
print(dp[0])

Submission status: Accepted

Solution code:
import sys
from bisect import bisect
def input():
	return sys.stdin.buffer.readline()[:-1]

MOD = 998244353
n = int(input())
r = []
for _ in range(n):
	x, d = map(int, input().split())
	r.append((-x, -x-d))
r.sort()

INF = 10**30

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

leftmost = Rmin(n)

wait = [r[0][0]]
dp = [[0 for _ in range(2)] for _ in range(n)]#0: いない 1: いる
dp[0] = [1, 1]
leftmost.Update(0, 0)

for i in range(1, n):
	dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % MOD	
	if r[i][1] < wait[-1]:
		b = bisect(wait, r[i][1])
		mi = leftmost.Get(b, i)
		dp[i][0] = dp[mi][0]
		leftmost.Update(i, mi)
	else:
		dp[i][0] = dp[i][1]
		leftmost.Update(i, i)
	wait.append(r[i][0])

print((dp[n-1][0] + dp[n-1][1]) % MOD)

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    mod = 998244353
    
    N = int(input())
    robot = [tuple(map(int, input().split())) for _ in range(N)]
    robot.sort()

    stack = []
    dp = [1] * (N+1)
    for i in reversed(range(N)):
        x, d = robot[i]
        while stack and robot[stack[-1]][0] < x + d:
            stack.pop()
        if stack:
            dp[i] = dp[i+1] + dp[stack[-1]]
        else:
            dp[i] = dp[i+1] + 1
        dp[i] %= mod
        stack.append(i)
    
    print(dp[0])

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

mod = 998244353
N = int(input())
XD = [tuple(map(int, input().split())) for _ in range(N)]
XD.sort(key=lambda x : x[0])
children = [[] for _ in range(N)]
stack = []
for i, (x, d) in list(enumerate(XD))[::-1]:
    while stack and stack[-1][0] < x + d:
        y, j = stack.pop()
        children[i].append(j)
    stack.append((x, i))
val = [0] * N
for i in range(N)[::-1]:
    res = 1
    for j in children[i]:
        res = res * val[j] % mod
    val[i] = res + 1
ans = 1
for x, i in stack:
    ans = ans * val[i] % mod
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

mod = 998244353
N = int(input())
XD = [tuple(map(int, input().split())) for _ in range(N)]
XD.sort(key=lambda x : x[0])
children = [[] for _ in range(N)]
pq = []
for i, (x, d) in list(enumerate(XD))[::-1]:
    while pq and pq[0][0] < x + d:
        y, j = heappop(pq)
        children[i].append(j)
    heappush(pq, (x, i))
val = [0] * N
for i in range(N)[::-1]:
    res = 1
    for j in children[i]:
        res = res * val[j] % mod
    val[i] = res + 1
ans = 1
while pq:
    x, i = heappop(pq)
    ans = ans * val[i] % mod
print(ans)

Submission status: Accepted

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

mod = 998244353

class BITree:
    def __init__(self,n):
        self.s = [-10**9-1]*(n+1)
        self.n = n
    def change(self,idx,val):
        # 1-index
        while idx < self.n+1:
            self.s[idx] = max(self.s[idx],val)
            idx += idx&(-idx)
        return
    def get(self,idx):
        # 1-index
        res = -10**9-1
        while idx > 0:
            res = max(res,self.s[idx])
            idx -= idx&(-idx)
        return res


n = int(input())
ans = 1
XD = []
X = []
for i in range(n):
    x,d = map(int,input().split())
    XD.append((x,d))
    X.append(x)
XD.sort()
X.sort()
dp = [0]*(n+1)
dp[-1] = 1
# dp[i] = 左からi+1番目から右側での問題文のやつ(ただしi = nのとき1)
# dp[0] を知りたい
BIT = BITree(n)
for i in range(n-1,-1,-1):
    x,d = XD[i]
    will = max(x+d,BIT.get(bisect.bisect_left(X, x+d)))
    BIT.change(i+1,will)
    # print(bisect.bisect_left(X, will)+1)
    dp[i] = dp[i+1] + dp[bisect.bisect_left(X, will)]
    dp[i] %= mod
print(dp[0])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left
MOD = 998244353  # type: int

import math


class SegmentTree(object):
    # セグメント木

    def __init__(self, N):
        """サイズNの配列を元にしたセグメント木
        """
        # 単位元
        self.idelem = -10**9
        # 比較関数
        self.func = max

        self.N0 = 1
        while self.N0 < N:
            self.N0 <<= 1
        self.tree = [self.idelem]*(2*self.N0)

    def update(self, k, x):
        """k番目の値をxに更新
        """
        k += self.N0-1
        self.tree[k] = x
        while k > 1:
            k = (k-1)//2
            self.tree[k] = self.func(self.tree[2*k+1], self.tree[2*k+2])

    def query(self, l, r):
        """区間[l, r)の最小値
        """
        l += self.N0-1
        r += self.N0-1
        s = self.idelem
        while l < r:
            if r % 2 == 0:
                r -= 1
                s = self.func(s, self.tree[r])

            if l % 2 == 0:
                s = self.func(s, self.tree[l])
                l += 1
            l //= 2
            r //= 2
        return s


def solve(N: int, X: "List[int]", D: "List[int]"):
    # グラフを構成しようとすると、O(N^2)が考えられる。
    # 接続先が単調に決まることを利用して、一番遠くだけ記憶しておく。
    reachable = [0]*N

    # ソートしておく
    X, D = zip(*sorted(zip(X, D)))
    # print(X, D)

    # O(NlogN)で直接的に影響範囲を整理する。
    for i, (x, d) in enumerate(zip(X, D)):
        reachable[i] = bisect_left(X, x+d)

    # SegmentTreeで、間接的な影響範囲を管理する
    seg = SegmentTree(N)

    # 後ろから、真の影響範囲を決めていく
    for v in reversed(range(N)):
        if v == N-1:
            seg.update(v, reachable[v])
            continue
        # vからreachable[v]-1までの間のノードの
        # 影響範囲の最大値が、真の影響範囲
        a = seg.query(v, reachable[v])
        if a > 0:
            seg.update(v, a)
        else:
            seg.update(v, v+1)

    true_reachable = [seg.query(v, v+1) for v in range(N)]

    # print(true_reachable)

    dp = [0]*(N+1)
    dp[N] = 1
    for v in reversed(range(N)):
        dp[v] = dp[v+1]+dp[true_reachable[v]]
        dp[v] %= MOD
    print(dp[0])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    D = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, X, D)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def solve():
    MOD = 998244353

    N = int(input())
    XDs = [tuple(map(int, input().split())) for _ in range(N)] + [(10**12, 0)]

    XDs.sort()
    Xs = [X for X, D in XDs]

    stack = [N]
    dp = [0] * (N+1)
    dp[-1] = 1
    for i in reversed(range(N)):
        X, D = XDs[i]
        while Xs[stack[-1]] < X+D:
            stack.pop()
        dp[i] = dp[stack[-1]] + dp[i+1]
        dp[i] %= MOD
        stack.append(i)

    print(dp[0])


solve()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    from operator import itemgetter
    import sys
    input = sys.stdin.readline

    MOD = 998244353

    N = int(input())

    xds = []
    xs = []
    for _ in range(N):
        x, d = map(int, input().split())
        xds.append((x, d))
        xs.append(x)

    xds.sort(key=itemgetter(0), reverse=True)
    xs.sort()

    ps = [-1] * (N + 1)
    cands = deque()  # 既出の頂点で有向辺の行き先に設定されていないもの,x昇順
    for j, (x, d) in enumerate(xds):
        j = N - 1 - j
        while cands:
            cx, ci = cands[0]
            if x + d <= cx:
                # candは独立
                break
            elif x <= cx < x + d:
                # candと連結
                ps[ci] = j
                cands.popleft()
        cands.appendleft((x, j))

    ret = 1
    ctr = [1] * N
    for j, (x, d) in enumerate(xds):
        j = N - 1 - j
        par = ps[j]
        ctr[j] += 1  # j=off,子の総積が設定されている->j=on=1を加算
        if ~par:
            ctr[par] = ctr[par] * ctr[j] % MOD
        else:
            ret = ret * ctr[j] % MOD  # j=木のroot

    print(ret)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import bisect
con = 998244353; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	def __init__(self, N):
		self.N0 = 2 ** (N - 1).bit_length()
		self.data = [0] * (2 * self.N0)

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

	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = 0
		while L < R:
			if R & 1:
				R -= 1
				m = max(m, self.data[R - 1])
			if L & 1:
				m = max(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

#処理内容
def main():
	N = int(input())
	XD = [None] * N
	for i in range(N):
		X, D = getlist()
		XD[i] = [X, D]
	XD.sort()
	Xl = [XD[i][0] for i in range(N)]
	Xl.append(INF)

	Seg = SegmentTree(N)
	IND = [None] * N
	for i in range(N):
		ind = bisect.bisect_left(Xl, XD[i][0] + XD[i][1]) - 1
		Seg.update(i, ind)
		IND[i] = ind

	#DP初期化
	DP = [[0] for i in range(N + 1)]
	DP[N] = 1
	# print(Xl)
	# print(IND)

	for i in range(N - 1, -1, -1):
		ind = Seg.query(i, IND[i])
		Seg.update(i, ind)
		DP[i] = DP[i + 1] + DP[ind + 1]
		DP[i] %= con

	ans = DP[0]
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n=int(readline())
segSize=n+1
def init_max(init_max_val):
    for i in range(segSize):
        seg_max[i+num_max-1]=init_max_val[i]
    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 = 0
num_max =2**(segSize-1).bit_length()
seg_max=[ide_ele_max]*2*num_max
mod=998244353

m = map(int,read().split())
XD = sorted(zip(m,m))
X=[x for x,d in XD]

from bisect import bisect_right
X=[bisect_right(X,x+d-1)for x,d in XD]

init_max(list(range(segSize)))
update_max(n,n)
combs=[1]*(n+1)
t=0
for x,d in reversed(XD):
    idx=n-1-t
    t+=1
    p=X[idx]
    p=query_max(idx,p)
    update_max(idx,p)
    combs[idx]=(combs[p+1]+combs[idx+1])%mod
print(combs[0])