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: Wrong Answer

Solution code:
class SegTree:
    X_unit = -10**10
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

from bisect import bisect_left
mod = 10**9+7
N = int(input())
robots = []
for i in range(N):
    Xi,Di = map(int,input().split())
    robots.append((Xi,Di))
robots.sort(key=lambda x:x[0])
X = [rob[0] for rob in robots]
D = [rob[1] for rob in robots]

ST = SegTree(N)
ST.set_val(N-1,N-1)
for i in range(N-1)[::-1]:
    r = bisect_left(X,X[i]+D[i])
    if i+1 == r:
        ST.set_val(i,i)
    else:
        ST.set_val(i,ST.fold(i+1,r))
to = ST.X[N:]
dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
    dp[to[i]+1] += dp[i]
    dp[to[i]+1] %= mod
    dp[i+1] += dp[i]
    dp[i+1] %= mod
print(dp[N])

Submission status: Wrong Answer

Solution code:
from heapq import *
N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
X.sort(reverse=True)
Q=[]
heapify(Q)
Y=0
mod=10**9+7
for i in range(N):
  Y=1
  while len(Q):
    if Q[0][0]<X[i][0]+X[i][1]:
      Y=Y*Q[0][1]%mod
      heappop(Q)
    else:
      break
  heappush(Q,(X[i][0],Y+1))
P=1
while len(Q):
  P=P*heappop(Q)[1]%mod
print(P)

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    if S=="AAA" or S=="BBB":
        print("No")
    else:
        print("Yes")
    return

def examB():
    N, A, B = LI()
    loop = N//(A+B)
    ans = loop*A + min(A,N%(A+B))
    print(ans)
    return

def examC():
    A, B = LI()
    ans = -1
    for i in range(1,20000):
        if i*8//100==A:
            if i*10//100==B:
                ans = i
                break
    print(ans)
    return

def examD():
    S = SI()
    Q = I()
    rev = 0
    L = ""; R = ""
    for _ in range(Q):
        q = LSI()
        if q[0]=="1":
            rev += 1
        else:
            c = int(q[1])
            if (c+rev)%2==1:
                L += q[2]
            else:
                R += q[2]
    ans = ""
    if rev%2==0:
        ans = L[::-1] + S + R
    else:
        ans = R[::-1] + S[::-1] + L
    print(ans)
    return

def examE():
    N, P = LI()
    S = SI()
    A = [0]*(N+1)
    cur = 0
    if P==5:
        ans = 0
        for i in range(N):
            if int(S[N-1-i])%5==0:
                ans += N-i
        print(ans)
        return
    elif P==2:
        ans = 0
        for i in range(N):
            if int(S[N-1-i])%2==0:
                ans += N-i
        print(ans)
        return

    for i in range(N):
        s = int(S[N-1-i])
        cur += s*pow(10,i,P)
        A[i+1] = cur%P
    D = [0]*P
    for a in A:
        D[a] += 1
    ans = 0
    #print(A)
    for d in D:
        ans += d*(d-1)//2

    print(ans)
    return

def examF():
    def dfs(n, s):
        #input()
        #print(n,s)
        cur = 1
        can = sum(X[s])
        for i in range(s,n):
            if X[i][0]>=can:
                V[s] = cur
                return cur, i
            if i==n-1:
                return cur,i
            now, visited = dfs(n, i+1)
            cur += now
        V[s] = cur
        return cur, n
    N = I()
    X = [LI()for _ in range(N)]
    X.sort()
    V = [[]for _ in range(N)]
    neg = 0
    ans = dfs(N,0)
    print(V)

    print(ans)
    return

def examF2():
    N = I()
    X = [LI()for _ in range(N)]
    N += 1
    X.sort()
    parent = [-1] * N
    #print(X)

    stack = [(inf,-1)]
    for i,(x,d) in enumerate(X):
        d += x
        # x座標近いやつからチェック
        # 届かないやつ排除
        while(stack[-1][0]<=x):
            stack.pop()
        parent[i] = stack[-1][1]
        stack.append((d,i))

    #print(parent)
    dp = [1]*N
    ans = 1
    for i in range(N-1)[::-1]:
        p = parent[i]
        if p==-1:
            ans *= dp[i]+1
            ans %= mod
            continue
        dp[p] *= dp[i]+1
        dp[p] %= mod

    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examF2()

"""

"""

Submission status: Wrong Answer

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)
    print(will)
    dp[i] = dp[i+1] + dp[bisect.bisect_left(X, will)]
    dp[i] %= mod
print(dp[0])

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import bisect
con = 10 ** 9 + 7; 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: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import bisect
con = 10 ** 9 + 7; 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]
		

	ans = DP[0]
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        # A : array of monoid (M, dot, unit)
        # (S, compose, identity) : sub monoid of End(M)
        # compose : (f, g) -> fg (f, g in S)
        # act : (f, x) -> f(x) (f in S, x in M)
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

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

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

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

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

from bisect import bisect_left
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: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left
    from operator import itemgetter
    import sys
    sys.setrecursionlimit(10 ** 7)

    input = sys.stdin.readline

    MOD = 998244353

    N = int(input())

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

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

    g = tuple(set() for _ in range(N))
    for v, (x, d) in enumerate(xd):
        v = N - 1 - v  # range(0,N)->range(N-1,-1,-1)
        frm = bisect_left(xs, x)
        to = bisect_left(xs, x + d)
        for u in range(frm, to):  # [frm,to)
            g[v].add(u)  # 有向辺

    visited = [False] * N

    def dfs(v):
        visited[v] = True
        stay_me = 1
        for u in g[v]:
            if visited[u]: continue
            stay_me = stay_me * dfs(u) % MOD
        return stay_me + 1  # move_me

    ans = 1
    for v in range(N):
        if visited[v]: continue
        ans = ans * dfs(v) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
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
  pro += 1
  # print(node,pro)
  return pro % mod
ans = dfs(0)
print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
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
  pro += 1
  # print(node,pro)
  return pro % mod
ans = dfs(0)
print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
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)
    else:break
  pro += 1
  # print(node,pro)
  return pro % mod
ans = dfs(0)
print(ans-1)

Submission status: Wrong Answer

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

dp0 = [i for i in range(N)]
X.append(10**10)
for i in range(N-2,-1,-1):
    x,d = XD[i]
    j = bisect(X,x+d)-1
    if j != i:
        dp0[i] = max(dp0[i+1],dp0[j])

dp = [1]*(N+1)

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

Submission status: Wrong Answer

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

dp0 = [i for i in range(N)]
X.append(10**10)
for i in range(N-2,-1,-1):
    x,d = XD[i]
    j = bisect(X,x+d)-1
    if j != i:
        dp0[i] = max(dp0[i+1],dp0[j])

dp = [1]*(N+1)

for i in range(N-1,-1,-1):
    j = dp0[i]
    dp[i] = dp[i+1] + dp[j+1]
print(dp[0])

Submission status: Wrong Answer

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

dp0 = [i for i in range(N)]
X.append(10**10)
for i in range(N-2,-1,-1):
    x,d = XD[i]
    j = bisect(X,x+d)-1
    dp0[i] = dp0[j]

dp = [1]*(N+1)

for i in range(N-1,-1,-1):
    j = dp0[i]
    dp[i] = dp[i+1] + dp[j+1]
print(dp[0])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 19 15:35:41 2020

@author: ybt07
"""

class SegmentTreeMax():
    def __init__(self,n,init):
        # n = 7 のとき
        # offset = 2 ** 3 = 8
        # 実際のデータは tree[0+8], tree[1+8],,,, に入る
        # tree[0～8] は区間の値を入れるために使われている
        self.offset = 2 ** ((n-1).bit_length())  # セグメント木を配列で行玄する際のオフセット量
        self.tree = [init] * (2 * self.offset)
        self.init = init

    def update(self, pos, val): # pos番目の要素を覆う要素すべてについて値を更新する
        pos += self.offset
        self.tree[pos] = val  # n=7, pos=5 のとき tree[5+8] に val が入る
        while pos > 1:
            pos = pos // 2  # 13 // 2 = 6
            # tree[6] に tree[12],tree[13] の大きい方が入る
            self.tree[pos] = max(self.tree[2*pos],self.tree[2*pos+1])

    def query(self, l, r): # 区間[l,r]での最大値を求める
        # 例のごとく、オフセット
        l += self.offset
        r += self.offset
        ret = self.init  # 再帰的に書くので、初期値を設定
        while l <= r:
            ret = max(ret, self.tree[r])
            r = (r - 1) // 2
            ret = max(ret, self.tree[l])
            l = (l + 1) // 2
        return ret

mod=998244353
n=int(input())
xd=[list(map(int,input().split())) for _ in range(n)]
xd=sorted(xd,key=lambda x:x[0]) #X座標の小さい順にソートする

st=SegmentTreeMax(n,0)
ranges=[0]*n

for i in range(n):
    r = xd[i][0] + xd[i][1] #各ロボットが到達できる最大の位置
    left = -1
    right = n
    
    #2分探索によりどのロボットまで影響するかを求める(0-indexed)
    while right - left != 1:  # right と left の間が 1 （隣り合う） 行う
        mid = (left + right) // 2
        if xd[mid][0] >= r:  # index 上で中間の要素に届くか？
            right = mid  # ぶつからないところにいれば、もっと左を探す（さがす範囲を更新）

        else:
            left = mid  # ぶつかるところにいれば、もっと右を探す（さがす範囲を更新）
            
    ranges.append(right - 1)  # i 番目のロボットが right - 1 番目のロボットまで影響することを記録する
    st.update(i, right - 1) # セグメント木のi番目の要素を right - 1に更新する

for i in range(n-1,-1,-1):
    # x の大きい側から求めていくことで、玉突きでどこまで影響するか？の数字が求められる
    # j番目 = ranges[i] が影響する 範囲が、既にrange[j] に入っている
    ranges[i] = st.query(i,ranges[i]) # 区間[i,k]での番号の最大値を求める
    st.update(i, ranges[i]) # セグメント木のi番目の要素を上記の最大値に更新する

dp = [0] * (n+1)
dp[-1] = 1 #DPの初期値は1(すべてのロボットを除いた場合に相当する)

for i in range(n-1,-1,-1):
    j = ranges[i] + 1  # j : i の動作が影響を及ぼさない、右側にある、最小の j
    dp[i] = dp[i+1] + dp[j] #後ろから順にDP[i]=DP[i+1]+DP[j]として更新する
    dp[i] %= mod

print(dp[0])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
mod = 998244353
N = int(input())
XD = []
for _ in range(N):
    XD.append(list(map(int, input().split())))
XD = sorted(XD, key=lambda x:x[0])
#print(XD)

dp1 = [0] * N
dp2 = [0] * N
dp1[N-1] = 1
dp2[N-1] = 1
for i in range(N-2, -1, -1):
    dp1[i] = (dp1[i+1] + dp2[i+1])%mod

    a = XD[i][0] + XD[i][1]
    max = 0
    idx = None
    for k in range(i+1, N):
        if XD[k][0] < a:
            if max <= XD[k][0] + XD[k][1]:
                max = XD[k][0] + XD[k][1]
                idx = k
        else:break
    if idx==None:
        dp2[i] = (dp1[i+1] + dp2[i+1])%mod
    else:
        dp2[i] = dp2[idx]
print((dp2[0]+dp1[0])%mod)
#print(dp1)
#print(dp2)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
mod = 998244353
N = int(input())
XD = []
for _ in range(N):
    XD.append(list(map(int, input().split())))
XD = sorted(XD, key=lambda x:x[0])


dp1 = [0] * N
dp2 = [0] * N
dp1[N-1] = 1
dp2[N-1] = 1
for i in range(N-2, -1, -1):
    dp1[i] = (dp1[i+1] + dp2[i+1])%mod

    a = XD[i][0] + XD[i][1]
    max = 0
    idx = None
    for k in range(i+1, N):
        if XD[k][0] < a:
            if max < XD[k][0] + XD[k][1]:
                max = XD[k][0] + XD[k][1]
                idx = k
        else:break
    if idx==None:
        dp2[i] = (dp1[i+1] + dp2[i+1])%mod
    else:
        dp2[i] = dp2[idx]
print((dp2[0]+dp1[0])%mod)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np
mod = 998244353
N = int(input())
XD = []
for _ in range(N):
    XD.append(list(map(int, input().split())))
XD = sorted(XD, key=lambda x:x[0])


dp1 = [0] * N
dp2 = [0] * N
dp1[N-1] = 1
dp2[N-1] = 1
for i in range(N-2, -1, -1):
    dp1[i] = (dp1[i+1] + dp2[i+1])%mod

    a = XD[i][0] + XD[i][1]
    max = 0
    idx = None
    for k in range(i+1, N):
        if XD[k][0] < a:
            if max < XD[k][0] + XD[k][1]:
                max = XD[k][0] + XD[k][1]
                idx = k
        else:break
    if idx==None:
        dp2[i] = (dp1[i+1] + dp2[i+1])%mod
    else:
        dp2[i] = dp2[idx]
print((dp2[0]+dp1[0])%mod)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np
mod = 998244353
N = int(input())
XD = []
for _ in range(N):
    XD.append(list(map(int, input().split())))
XD = sorted(XD, key=lambda x:x[0])
print(XD)
dp1 = [0] * N
dp2 = [0] * N
dp1[N-1] = 1
dp2[N-1] = 1
for i in range(N-2, -1, -1):
    dp1[i] = (dp1[i+1] + dp2[i+1])%mod

    a = XD[i][0] + XD[i][1]
    max = 0
    idx = None
    for k in range(i+1, N):
        if XD[k][0] < a:
            if max < XD[k][0] + XD[k][1]:
                max = XD[k][0] + XD[k][1]
                idx = k
        else:break
    if idx==None:
        dp2[i] = (dp1[i+1] + dp2[i+1])%mod
    else:
        dp2[i] = dp2[idx]
print((dp2[0]+dp1[0])%mod)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
mod=998244353
n=int(input())
if n==1: print(2);sys.exit()

l=[list(map(int,input().split())) for _ in range(n)]
l=sorted(l)
x=[l[i][0] for i in range(n)]
d=[l[i][1] for i in range(n)]
dp=[[0,0] for _ in range(n)]
dp[n-1]=[1,1]

p=[i for i in range(n)]
for i in range(n-2,-1,-1):
    dp[i][0]=(dp[i+1][0]+dp[i+1][1])%mod
    if x[i]+d[i]<=x[i+1]: dp[i][1]=dp[i][0]
    else:
        p[i]=max(p[i+1],p[bisect.bisect_left(x,x[i]+d[i])-1])
        dp[i][1]=dp[p[i]][1]

print((dp[0][0]+dp[0][1]) %mod)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
mod=998244353
n=int(input())
if n==1: print(2);sys.exit()

l=[list(map(int,input().split())) for _ in range(n)]
l=sorted(l)
x=[l[i][0] for i in range(n)]
d=[l[i][1] for i in range(n)]
dp=[[0,0] for _ in range(n)]
dp[n-1]=[1,1]

p=[i for i in range(n)]
for i in range(n-2,-1,-1):
    dp[i][0]=(dp[i+1][0]+dp[i+1][1])%mod
    if x[i]+d[i]<=x[i+1]: dp[i][1]=dp[i][0]
    else:
        p[i]=max(p[i+1],bisect.bisect_left(x,x[i]+d[i])-1)
        dp[i][1]=dp[p[i]][1]

print((dp[0][0]+dp[0][1]) %mod)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
mod=998244353
n=int(input())
if n==1: print(2);sys.exit()

l=[list(map(int,input().split())) for _ in range(n)]
l=sorted(l)
x=[l[i][0] for i in range(n)]
d=[l[i][1] for i in range(n)]
dp=[[0,0] for _ in range(n)]
dp[n-1]=[1,1]

for i in range(n-2,-1,-1):
    dp[i][0]=(dp[i+1][0]+dp[i+1][1])%mod
    if x[i]+d[i]<=x[i+1]: dp[i][1]=dp[i][0]
    else:
        p=bisect.bisect_left(x,x[i]+d[i])-1
        dp[i][1]=min(dp[p][1],dp[i+1][1])%mod

print((dp[0][0]+dp[0][1]) %mod)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
mod=998244353
n=int(input())
if n==1: print(2);sys.exit()

l=[list(map(int,input().split())) for _ in range(n)]
l=sorted(l)
x=[l[i][0] for i in range(n)]
d=[l[i][1] for i in range(n)]
dp=[[0,0] for _ in range(n)]
dp[n-1]=[1,1]

for i in range(n-2,-1,-1):
    dp[i][0]=(dp[i+1][0]+dp[i+1][1])%mod
    if x[i]+d[i]<=x[i+1]: dp[i][1]=dp[i][0]
    elif x[i]+d[i]<=x[i+1]+d[i+1]: dp[i][1]=dp[i+1][1]
    else:
        p=bisect.bisect_left(x,x[i]+d[i])-1
        dp[i][1]=min(dp[p][1],dp[i+1][1])%mod

print((dp[0][0]+dp[0][1]) %mod)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
mod=998244353
n=int(input())
if n==1: print(2);sys.exit()

l=[list(map(int,input().split())) for _ in range(n)]
l=sorted(l)
x=[l[i][0] for i in range(n)]
d=[l[i][1] for i in range(n)]
dp=[[0,0] for _ in range(n)]
dp[n-1]=[1,1]

for i in range(n-2,-1,-1):
    dp[i][0]=dp[i+1][0]+dp[i+1][1]
    if x[i]+d[i]<=x[i+1]: dp[i][1]=dp[i][0]
    elif x[i]+d[i]<=x[i+1]+d[i+1]: dp[i][1]=dp[i+1][1]
    else:
        p=bisect.bisect_left(x,x[i]+d[i])-1
        dp[i][1]=min(dp[p][1],dp[i+1][1])
    dp[i][0]%=mod
    dp[i][1]%=mod

print((dp[0][0]+dp[0][1]) %mod)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
mod=998244353
n=int(input())
if n==1: print(2);sys.exit()

l=[list(map(int,input().split())) for _ in range(n)]
l=sorted(l)
x=[l[i][0] for i in range(n)]
d=[l[i][1] for i in range(n)]
dp=[[0,0] for _ in range(n)]
dp[n-1]=[1,1]

for i in range(n-2,-1,-1):
    dp[i][0]=dp[i+1][0]+dp[i+1][1]
    if x[i]+d[i]<=x[i+1]: dp[i][1]=dp[i][0]
    elif x[i]+d[i]<=x[i+1]+d[i+1]: dp[i][1]=dp[i+1][1]
    else:
        p=bisect.bisect_right(x,x[i]+d[i])-1
        dp[i][1]=min(dp[p][1],dp[i+1][1])
    dp[i][0]%=mod
    dp[i][1]%=mod

print((dp[0][0]+dp[0][1]) %mod)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
mod=998244353
n=int(input())
if n==1: print(2);sys.exit()

l=[list(map(int,input().split())) for _ in range(n)]
l=sorted(l)
x=[l[i][0] for i in range(n)]
d=[l[i][1] for i in range(n)]
dp=[[0,0] for _ in range(n)]
dp[n-1]=[1,1]

for i in range(n-2,-1,-1):
    dp[i][0]=dp[i+1][0]+dp[i+1][1]
    if x[i]+d[i]<=x[i+1]: dp[i][1]=dp[i][0]
    elif x[i]+d[i]<=x[i+1]+d[i+1]: dp[i][1]=dp[i+1][1]
    else:
        p=bisect.bisect_right(x,x[i]+d[i])-1
        dp[i][1]=min(dp[p][1],dp[i+1][1])
    dp[i]=[x%mod for x in dp[i]]

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

Submission status: Wrong Answer

Solution code:
import bisect
import sys
mod=998244353
n=int(input())
if n==1: print(2);sys.exit()

l=[list(map(int,input().split())) for _ in range(n)]
l=sorted(l)
x=[l[i][0] for i in range(n)]
d=[l[i][1] for i in range(n)]
dp=[[0,0] for _ in range(n)]
dp[n-1]=[1,1]

for i in range(n-2,-1,-1):
    dp[i][0]=dp[i+1][0]+dp[i+1][1]
    if x[i]+d[i]<=x[i+1]: dp[i][1]=dp[i][0]
    elif x[i]+d[i]<=x[i+1]+d[i+1]: dp[i][1]=dp[i+1][1]
    else:
        p=bisect.bisect_right(x,x[i]+d[i])-1
        dp[i][1]=min(dp[p][1],dp[i+1][1])
    dp[i]=[x%mod for x in dp[i]]

print(sum(dp[0]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n = I()
XD = sorted(LIR(n))
X = []
D = []
for x, d in XD:
    X += [x]
    D += [d]

last = [l for l in range(n)]
for i in range(n - 2, -1, -1):
    last[i] = last[bisect_left(X, X[i] + D[i]) - 1]

dp = [1] * (n + 1)
for j in range(n - 1, -1, -1):
    k = last[j]
    dp[j] = (dp[j + 1] + dp[k + 1]) % mod


print(dp[0])

Submission status: Wrong Answer

Solution code:
"""
F
"""
import sys
input=sys.stdin.readline
#n番目をxに変更して更新する
def seg_tree_update(n,x):
    ind=2**m-1+n
    tree[ind]=x
    ind=(ind-1)//2
    while ind>=0:
        tree[ind]=max(tree[2*ind+1],tree[2*ind+2])
        ind=(ind-1)//2

#区間[L,R]における最大値を返す(非負整数)
def seg_tree_find_max(L,R):
    L,R=2**m-1+L,2**m-1+R
    qqq=0
    while L<R:
        if L%2==0:
            qqq=max(qqq,tree[L])
        if R%2==1:
            qqq=max(qqq,tree[R])
        L//=2
        R=R//2-1
        
    if L==R:
        qqq=max(qqq,tree[L])
    return qqq

from bisect import bisect

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

m=0
while pow(2,m)<N:
    m+=1
tree=[0]*(pow(2,m+1)-1)

XD.sort()
data=[i for i in range(N)]
for i in range(N-2,-1,-1):
    Y=XD[i][0]+XD[i][1]
    b=bisect(XD,[Y])
    if i<b-1:
        num=seg_tree_find_max(i+1,b-1)
        seg_tree_update(i,num)
        data[i]=num
    else:
        seg_tree_update(i,i)