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:
class SegTree:
    def __init__(self, init_val, ide_ele, seg_func):
        self.segfunc = seg_func
        n = len(init_val)
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        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
        # k+1ではなくkでは？
        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

def bsearch(mn, mx, func):
    #func(i)=False を満たす最大のi
    idx = (mx + mn)//2
    while mx-mn>1:
        if func(idx):
            idx, mx = (idx + mn)//2, idx
            continue
        idx, mn = (idx + mx)//2, idx
    return idx

import sys;input=sys.stdin.readline
mod = 998244353
N=int(input())
X = []
Y = []
for _ in range(N):
    x, d = map(int, input().split())
    X.append((x,d))
X.sort()
C = [0] * N
for i in range(N):
    x, d = X[i]
    k = bsearch(-1, N, lambda j: X[j][0] >= x+d)
    C[i] = k

st = SegTree(C, -1, max)
dp = [1]*(N+1)
for i in range(N-1, -1, -1):
    y=st.query(i, C[i]+1)
    st.update(i, y)
    dp[i] = (dp[i+1]+dp[y+1]) % mod
print(dp[0])

Submission status: Accepted

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

MOD = 998244353
N = int(input())
robo = list(list(map(int,input().split()))for i in range(N))
robo.sort()
child = [[]for i in range(N+1)]
stack = [] # 有効、名前

for i in range(N):
    x,d = robo[i]
    while stack and stack[-1][0] <= x:
        stack.pop()
    if stack:
        child[stack[-1][1]].append(i+1)
    else:
        child[0].append(i+1)
    stack.append([x+d,i+1])

def func(x):
    hoge = 1
    for i in child[x]:
        hoge *= func(i)
        hoge %= MOD
    return (hoge + 1) % MOD

print(func(0)-1)

Submission status: Accepted

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

class SegmentTree:
    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 update(self, i, x):
        idx = self.N - 1 + i
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = max(self.data[2*idx+1], self.data[2*idx+2])
    
    def query(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&1 == 0: # idx1が偶数
                    result = max(result, self.data[idx1])
                if idx2&1 == 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


MOD = 998244353
N = int(input())
XD = [list(map(int, input().split())) for i in range(N)]
XD.sort()

X = [xd[0] for xd in XD]

dp = [0] * (N+1)
dp[-1] = 1
st = SegmentTree([i for i in range(N)])
for i in range(N-1, -1, -1):
  idx = bisect.bisect_left(X, sum(XD[i])) - 1
  if idx > i:
    idx = st.query(i, idx+1)
    st.update(i, idx) 
  dp[i] = (dp[i+1] + dp[idx+1]) % MOD

print(dp[0])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
class SegTree:
    def __init__(self, l):
        emp=-1 #空白を埋める数
        #2の冪乗にする
        N=len(l)
        n=N
        layer=1
        bottom=1
        while n>1:
            n=n/2
            layer+=1
            bottom*=2
        L=[emp]*(2*bottom-1)
        #初期化
        for i in range(N):
            L[bottom-1+i]=l[i]
        for i in range(bottom-2,-1,-1):
            L[i]=max(L[2*i+1],L[2*i+2])
        self.tree=L
        self.bottom=bottom
        self.layer=layer
        self.emp=emp

    def add(self,index,num):
        x=self.bottom+index-1
        self.tree[x]+=num
        for _ in range(self.layer-1):
            x=(x-1)//2
            self.tree[x]=max(self.tree[2*x+1],self.tree[2*x+2])

    #l<=x<r
    def segment(self,l,r):
        s=-1
        L=self.bottom+l
        R=self.bottom+r
        while L<R:
            if L&1:
                s=max(s,self.tree[L-1])
                L+=1
            if R&1:
                R-=1
                s=max(s,self.tree[R-1])
            L//=2
            R//=2
        return s
INF=998244353
n=int(input())
l=[]
for i in range(n):
    x,d=map(int,input().split())
    l.append((x,d))
l.sort()
x=[]
d=[]
for i in l:
    x.append(i[0])
    d.append(i[1])
dp=[1]
Sum=[1]
import bisect
t=[0]*n
t=SegTree(t)
for i in range(n):
    y=x[n-1-i]+d[n-1-i]
    m=bisect.bisect_left(x,y)
    z=t.segment(n-1-i,m)
    m=max(m,z)
    t.add(n-1-i,m)
    dp.append(Sum[n-m])
    s=(Sum[-1]+dp[-1])%INF
    Sum.append(s)
print(Sum[-1])

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, seg_func):
        self.segfunc = seg_func
        n = len(init_val)
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        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
        # k+1ではなくkでは？
        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
import sys;input=sys.stdin.readline
mod = 998244353
N=int(input())
X = []
Y = []
for _ in range(N):
    x, d = map(int, input().split())
    X.append((x,d))
X.sort(key=lambda x:x[0])
for i, (x, d) in enumerate(X):
    Y.append((2*x,i,0))
    Y.append((2*x+2*d-1,i,1))
Y.sort(key=lambda x:x[0])
C = [0]*N
for x, i, t in Y:
    if t==0:
        j = i
    elif t==1:
        C[i] = j
st = SegTree(C, -1, max)
dp = [1]*(N+1)
for i in range(N-1, -1, -1):
    y=st.query(i, C[i]+1)
    st.update(i, y)
    dp[i] = (dp[i+1]+dp[y+1]) % mod
print(dp[0])

Submission status: Accepted

Solution code:
import bisect
import operator
import os
import sys
from functools import reduce


class SegmentTree:
    # http://codeforces.com/blog/entry/18051
    def __init__(self, values, op=operator.add):
        """
        :param list values:
        :param callable op: 結合律を満たす二項演算
        """
        self._size = len(values)
        self._op = op
        tree = [None] * self._size * 2
        tree[self._size:] = values[:]
        for i in reversed(range(1, self._size)):
            tree[i] = self._op(tree[i << 1], tree[i << 1 | 1])
        self._tree = tree

    def set(self, i, value):
        """
        values[i] = value
        :param int i:
        :param value:
        """
        i += self._size
        self._tree[i] = value
        i >>= 1
        while i > 0:
            self._tree[i] = self._op(self._tree[i << 1], self._tree[i << 1 | 1])
            i >>= 1

    def add(self, i, value):
        """
        values[i] = values[i]・value
        :param int i:
        :param value:
        """
        new_value = self._op(self._tree[self._size + i], value)
        self.set(i, new_value)

    def get(self, l, r=None):
        """
        [l, r) に op を順番に適用した値
        :param int l:
        :param int|None r:
        """
        if r is None:
            return self._tree[self._size + l]
        ret_l = []
        ret_r = []
        l += self._size
        r += self._size
        while l < r:
            if l & 1:
                ret_l.append(self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret_r.append(self._tree[r])
            l >>= 1
            r >>= 1
        return reduce(self._op, ret_l + ret_r)

    def __len__(self):
        return self._size

    def get_values_copy(self):
        return self._tree[self._size:]


if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353

N = int(sys.stdin.buffer.readline())
XD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

XD.sort()
X = [x for x, d in XD]
D = [d for x, d in XD]

# R[i]: i 番目のロボットがどこまで行くか
st = SegmentTree(list(range(N)), op=max)
for i, (x, d) in reversed(list(enumerate(XD))):
    ri = bisect.bisect_left(X, x + d) - 1
    st.set(i, st.get(i, ri + 1))
R = st.get_values_copy()

# dp[i]: ロボット i からロボット N - 1 までを使うときの組み合わせの数
dp = [0] * (N + 1)
dp[-1] = 1
for i, r in reversed(list(enumerate(R))):
    # 使わない場合
    dp[i] += dp[i + 1]
    # 使う場合
    dp[i] += dp[r + 1]
    dp[i] %= MOD
# print(dp)
print(dp[0])

Submission status: Accepted

Solution code:
import bisect
import operator
import os
import sys
from functools import reduce


class SegmentTree:
    # http://codeforces.com/blog/entry/18051
    def __init__(self, values, op=operator.add):
        """
        :param list values:
        :param callable op: 結合律を満たす二項演算
        """
        self._size = len(values)
        self._op = op
        tree = [None] * self._size * 2
        tree[self._size:] = values[:]
        for i in reversed(range(1, self._size)):
            tree[i] = self._op(tree[i << 1], tree[i << 1 | 1])
        self._tree = tree

    def set(self, i, value):
        """
        values[i] = value
        :param int i:
        :param value:
        """
        i += self._size
        self._tree[i] = value
        i >>= 1
        while i > 0:
            self._tree[i] = self._op(self._tree[i << 1], self._tree[i << 1 | 1])
            i >>= 1

    def add(self, i, value):
        """
        values[i] = values[i]・value
        :param int i:
        :param value:
        """
        new_value = self._op(self._tree[self._size + i], value)
        self.set(i, new_value)

    def get(self, l, r=None):
        """
        [l, r) に op を順番に適用した値
        :param int l:
        :param int|None r:
        """
        if r is None:
            return self._tree[self._size + l]
        ret_l = []
        ret_r = []
        l += self._size
        r += self._size
        while l < r:
            if l & 1:
                ret_l.append(self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret_r.append(self._tree[r])
            l >>= 1
            r >>= 1
        return reduce(self._op, ret_l + ret_r)

    def __len__(self):
        return self._size


if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353

N = int(sys.stdin.buffer.readline())
XD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

XD.sort()
X = [x for x, d in XD]
D = [d for x, d in XD]

# R[i]: i 番目のロボットがどこまで行くか
st = SegmentTree(list(range(N)), op=max)
for i, (x, d) in reversed(list(enumerate(XD))):
    ri = bisect.bisect_left(X, x + d) - 1
    st.set(i, st.get(i, ri + 1))
R = [st.get(i) for i in range(N)]

# dp[i]: ロボット i からロボット N - 1 までを使うときの組み合わせの数
dp = [0] * (N + 1)
dp[-1] = 1
for i, r in reversed(list(enumerate(R))):
    # 使わない場合
    dp[i] += dp[i + 1]
    # 使う場合
    dp[i] += dp[r + 1]
    dp[i] %= MOD
# print(dp)
print(dp[0])

Submission status: Accepted

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

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

def make():
    edge = [[] for _ in range(N)]
    parent = [-1] * N
    MAXIDX = N
    sorted_X = [X for X,_ in XD]
    for i in range(N-1, -1, -1):
        idx = bisect_left(sorted_X, XD[i][0] + XD[i][1])
        for j in range(i+1, min(idx, MAXIDX)):
            if parent[j] < 0:
                parent[j] = i
        if idx >= MAXIDX:
            MAXIDX = i + 1
    for i,par in enumerate(parent):
        if par < 0:
            continue
        edge[par].append(i)
    
    return parent, edge

parent, edge = make()

def cnt(node):
    if not edge[node]:
        return 2

    res = 1
    for v in edge[node]:
        res = (res * cnt(v)) % MOD
    res += 1

    return res % MOD

def main():
    ans = 1
    for i,par in enumerate(parent):
        if par < 0:
            ans = (ans * cnt(i)) % MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

X = sorted(X, key = lambda x: x[0])
L = [(0, -(10**9+1), 10**9+1)]
P = [-1] * (N+1)
for i, (x, y) in enumerate(X):
    while L[-1][2] <= y:
        if L[-1][2] > x and P[i+1] < 0:
            P[i+1] = L[-1][0]
        L.pop()
    if P[i+1] < 0:
        P[i+1] = L[-1][0]
    L.append((i+1, x, y))

C = [[] for _ in range(N+1)]
for i, p in enumerate(P):
    if p >= 0:
        C[p].append(i)

Y = [1] * (N+1)
for i in range(N+1)[::-1]:
    s = 1
    for j in C[i]:
        s = s * (Y[j] + 1) % mod
    Y[i] = s

print(Y[0])

Submission status: Accepted

Solution code:
n = int(input())
l = [tuple(map(int, input().split())) for _ in range(n)] + [(1<<31, 0)]
mod = 998244353
l.sort()
st = [n]
dp = [0]*n + [1]
for i in range(n-1,-1,-1):
  x,d = l[i]
  v = x + d
  while l[st[-1]][0] < v: st.pop()
  dp[i] = (dp[i+1] + dp[st[-1]]) % mod
  st.append(i)
print(dp[0])

Submission status: Accepted

Solution code:
mod = 998244353
n = int(input())
l = [tuple(map(int, input().split())) for _ in range(n)] + [(10**10, 0)]
l.sort()
st = [n]
nex = [n]*n
for i in range(n-1,-1,-1):
  x,d = l[i]
  v = x + d
  while l[st[-1]][0] < v: st.pop()
  nex[i] = st[-1]
  st.append(i)
dp = [0]*(n+1)
dp[n] = 1
for i in range(n-1,-1,-1):
  dp[i] = (dp[i+1] + dp[nex[i]]) % mod
print(dp[0])

Submission status: Accepted

Solution code:
# 解説放送
# https://atcoder.jp/contests/abc158/submissions/10643692
# dfsの代わりに親の頂点番号を配列で管理する方法
# PyPyでは通った

def main():
    from collections import deque, namedtuple
    from operator import attrgetter
    import sys
    input = sys.stdin.readline

    MOD = 998244353

    Robot = namedtuple('Robot', 'x d reach ind')

    N = int(input())

    robots = []
    for ind in range(N):
        X, D = map(int, input().split())
        robots.append(Robot(X, D, X + D, ind))
    robots.sort(key=attrgetter('x'), reverse=True)

    parents = [-1] * N
    to_candidates = deque()
    for robot_from in robots:  # x降順
        """
        右端に位置するロボットから順に「起点」と見なしていく
        既出のロボットで有向辺の行き先として一度も設定されていないものが
        to_candidatesにx昇順で溜められている
        to_candidatesに含まれるロボットで「起点」から接触範囲内のものがある限り、
        「起点」から有向辺を張り続ける
        to_candidatesの先頭候補(最も左側に位置する)に対して辺を張れない場合、
        それ以降の候補のxはより遠い座標で辺を張れないので
        「起点」から張れる辺がないとわかる
        すべてのロボットは「起点」から辺を張られてto_candidatesから外れるか
        to_candidatesに残り、グラフ(森)の各木のrootとなる
        """
        while to_candidates:
            robot_to = to_candidates[0]
            if robot_to.x < robot_from.reach:
                parents[robot_to.ind] = robot_from.ind
                to_candidates.popleft()
            else:
                break

        to_candidates.appendleft(robot_from)

    ret = 1
    count = [1] * N
    for robot in robots:  # x降順
        par = parents[robot.ind]
        count[robot.ind] += 1
        if ~par:
            count[par] = (count[par] * count[robot.ind]) % MOD
        else:
            ret = (ret * count[robot.ind]) % MOD
            # x降順で見ているのでpar==-1のrootのrobotを見る頃には
            # rootの子は全て見ているので安心してretにかけられる
    print(ret)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 解説放送
# https://atcoder.jp/contests/abc158/submissions/10643692
# dfsの代わりに親の頂点番号を配列で管理する方法

def main():
    from collections import deque, namedtuple
    from operator import attrgetter
    import sys
    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

    MOD = 998244353

    Robot = namedtuple('Robot', 'x d reach ind')

    N = int(input())

    robots = []
    for ind in range(N):
        X, D = map(int, input().split())
        robots.append(Robot(X, D, X + D, ind))
    robots.sort(key=attrgetter('x'), reverse=True)

    parents = [-1] * N
    to_candidates = deque()
    for robot_from in robots:  # x降順
        """
        右端に位置するロボットから順に「起点」と見なしていく
        既出のロボットで有向辺の行き先として一度も設定されていないものが
        to_candidatesにx昇順で溜められている
        to_candidatesに含まれるロボットで「起点」から接触範囲内のものがある限り、
        「起点」から有向辺を張り続ける
        to_candidatesの先頭候補(最も左側に位置する)に対して辺を張れない場合、
        それ以降の候補のxはより遠い座標で辺を張れないので
        「起点」から張れる辺がないとわかる
        すべてのロボットは「起点」から辺を張られてto_candidatesから外れるか
        to_candidatesに残り、グラフ(森)の各木のrootとなる
        """
        while to_candidates:
            robot_to = to_candidates[0]
            if robot_to.x < robot_from.reach:
                parents[robot_to.ind] = robot_from.ind
                to_candidates.popleft()
            else:
                break

        to_candidates.appendleft(robot_from)

    ret = 1
    count = [1] * N
    for robot in robots:  # x降順
        par = parents[robot.ind]
        count[robot.ind] += 1
        if ~par:
            count[par] = (count[par] * count[robot.ind]) % MOD
        else:
            ret = (ret * count[robot.ind]) % MOD
            # x降順で見ているのでpar==-1のrootのrobotを見る頃には
            # rootの子は全て見ているので安心してretにかけられる
    print(ret)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def dfs(i):
        res = 1
        for j in to[i]:
            res = res * dfs(j) % md
        return res + 1

    md = 998244353
    n = II()
    xd = LLI(n)
    xd.sort(reverse=True)
    to = [[] for _ in range(n)]
    hp = []
    for i, (x, d) in enumerate(xd):
        while hp and hp[0][0] < x + d:
            px, pi = heappop(hp)
            to[i].append(pi)
        heappush(hp, (x, i))
    ans = 1
    while hp:
        _, i = heappop(hp)
        ans = ans * dfs(i) % md
    print(ans)

main()

Submission status: Accepted

Solution code:
import heapq

mod = 998244353

n = int(input())
robot = [tuple(map(int, input().split())) for _ in range(n)]
robot.sort(reverse=True)
parent = list(range(n))

root = []
for i in range(n):
  x, d = robot[i]
  while root:
    r = heapq.heappop(root)
    if r[0] < x + d:
      parent[r[1]] = i
    else:
      heapq.heappush(root, r)
      break
  heapq.heappush(root, (x, i))
  
count = 1
dp = [1] * n
for i in range(n):
  p = parent[i]
  if p == i:
    count = count * (dp[i] + 1) % mod
  else:
    dp[p] = dp[p] * (dp[i] + 1) % mod
print(count)

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, seg_func):
        self.segfunc = seg_func
        n = len(init_val)
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        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
        # k+1ではなくkでは？
        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
import sys;input=sys.stdin.readline
mod = 998244353
N=int(input())
X = []
Y = []
for _ in range(N):
    x, d = map(int, input().split())
    X.append((x,d))
X.sort(key=lambda x:x[0])
for i, (x, d) in enumerate(X):
    Y.append((2*x,i,0))
    Y.append((2*x+2*d-1,i,1))
Y.sort(key=lambda x:x[0])
C = [0]*N
for x, i, t in Y:
    if t==0:
        j = i
    elif t==1:
        C[i] = j
st = SegTree(C, -1, max)
dp1 = [0]*(N+1)
dp2 = [1]*(N+1)
for i in range(N-1, -1, -1):
    y=st.query(i, C[i]+1)
    st.update(i, y)
    dp1[i] = (dp1[i+1]+dp2[i+1]) % mod
    dp2[i] = (dp1[y+1]+dp2[y+1]) % mod
print((dp1[0]+dp2[0])%mod)

Submission status: Accepted

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

n = int(input())
xd = [list(map(int, input().split())) for _ in range(n)]

mod = 998244353

xd.sort()

# 最大値を求めるセグメント木

def init_max(init_max_val):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]
    #built
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2])

def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])

def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res

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

#num_max:n以上の最小の2のべき乗
# num_max =2**(n-1).bit_length()
num_max = 2**(len(str(bin(n-1))) -2)
seg_max=[ide_ele_max]*2*num_max

import bisect
xs = list(map(lambda x: x[0], xd))

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

for i in range(n-1, -1, -1):
    move_r = bisect.bisect_left(xs, sum(xd[i]))
    if(i+1 == move_r):
        update_max(i, i)
    else:
        update_max(i, query_max(i+1, move_r))

    ans[i] = (ans[i+1] + ans[seg_max[i + num_max - 1] + 1]) % mod

print(ans[0])

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 998244353

def ddprint(x):
  if DBG:
    print(x)



# # # # class Segtree # # # #

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        l = x+s.n-1
        r = y+s.n-1
        res = s.unit
        while l<r:
            if not l%2:
                res = s.oper(res,s.ary[l])
                l += 1
            if not r%2:
                r -= 1
                res = s.oper(res,s.ary[r])
            l >>= 1
            r >>= 1
        return res


# # # # class Segtree end # # # #

# # # #
from bisect import bisect_left
n = inn()
xd = []
for i in range(n):
    xx,dd = inm()
    xd.append((xx,dd))
xd.sort()
x = [xd[i][0] for i in range(n)]

#ddprint(xd)
#ddprint(x)

r = [i for i in range(n)]
sgt = Segtree(n,0,max)
sgt.setary(r)
f = [0]*(n+1)
f[n] = 1
f[n-1] = 2
for i in range(n-2,-1,-1):
    xx,dd = xd[i]
    j = bisect_left(x,xx+dd)
    k = sgt.query(i,j)
    sgt.set(i,k)
    f[i] = (f[i+1] + f[k+1])%R
    #ddprint(f"i {i} x {xx} d {dd} j {j}")

#ddprint(f)
print(f[0])

Submission status: Accepted

Solution code:
# hmm...
from sys import setrecursionlimit
setrecursionlimit(10000000)

n = int(input())
xds = [tuple(map(int, input().split())) for _ in range(n)]
xds.sort()

xds.insert(0, (-1000000001, 2000000004))
n += 1

def make_blocks(i):
    x, d = xds[i]
    right = x + d
    res = []
    nexti = i + 1
    while(nexti < n):
        xn, dn = xds[nexti]
        if xn < right:
            l, lasti = make_blocks(nexti)
            res.append(l)
            nexti = lasti + 1
        else:
            return res, nexti - 1
    return res, n - 1

l, _ = make_blocks(0)

def count(l):
    ans = 1
    for ll in l:
        ans = ans * (1 + count(ll)) % 998244353
    return ans

print(count(l))