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: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

n = int(input())
xd = [list(map(int, input().split())) for _ in range(n)]
mod = 998244353
INF = 10 ** 18

xx = []
for i, (x, d) in enumerate(xd, 1):
    xx.append([i, x, 0])
    xx.append([i, x + d - 0.5, 1])

xx.sort(key=lambda x: x[1])

adj = [[] for _ in range(n + 1)]
now = {0}
hp = [(INF, 0)]
for i, x, remove in xx:
    if remove:
        now.remove(i)

    else:
        while hp[0][1] not in now:
            heappop(hp)

        px, pi = hp[0]
        adj[pi].append(i)

        now.add(i)
        heappush(hp, (-x, i))

stack = [0]
d = [-1] * (n + 1)
d[0] = 0
c = [[] for _ in range(n + 1)]
order = []
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            c[u].append(v)
            stack.append(v)

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

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

ans = dp[0] - 1
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

n = int(input())
xd = [list(map(int, input().split())) for _ in range(n)]
mod = 998244353
INF = 10 ** 18

xx = []
for i, (x, d) in enumerate(xd, 1):
    xx.append([i, x, 0])
    xx.append([i, x + d - 0.5, 1])

xx.sort(key=lambda x: x[1])

adj = [[] for _ in range(n + 1)]
now = {0}
hp = [(INF, 0)]
for i, x, remove in xx:
    if remove:
        now.remove(i)

    else:
        now.add(i)
        while hp[0][1] not in now:
            heappop(hp)

        px, pi = hp[0]
        adj[pi].append(i)

        heappush(hp, (-x, i))

stack = [0]
d = [-1] * (n + 1)
d[0] = 0
c = [[] for _ in range(n + 1)]
order = []
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            c[u].append(v)
            stack.append(v)

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

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

ans = dp[0] - 1
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTreeMax():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,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())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda x:x[0])
st=SegmentTreeMax(n,0)
ranges=[]
for i in range(n):
  x=arr[i][0]+arr[i][1]
  l=-1
  r=n
  while r-l!=1:
    mid=(l+r)//2
    if arr[mid][0]>=x:
      r=mid
    else:
      l=mid
  ranges.append(r-1)
  st.update(i,r-1)
for i in range(n-1,-1,-1):
  ranges[i]=st.query(i,ranges[i])
  st.update(i,ranges[i])
dp=[0]*(n+1)
dp[-1]=1
for i in range(n-1,-1,-1):
  j=ranges[i]+1
  dp[i]=dp[i+1]+dp[j]
  dp[i]%=mod
print(dp[0])

Submission status: Time Limit Exceeded

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

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: Time Limit Exceeded

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+1)
dp2 = [0] * (N+1)
dp1[N] = 1
dp1[N-1] = 1
dp2[N-1] = 1
reach_last = [0] * N
reach = [sum(row) for row in XD]

reach_last[N-1] = N

for i in range(N-2, -1, -1):
    # initialization
    reach_last[i] = i+1
    search = i + 1
    _search = search
    max_ = i + 1
    while XD[search][0] < reach[i]:
        max_ = max([max_, reach_last[search]])
        search += 1
        if search > N - 1: break
    if _search == search: continue
    reach_last[i] = max_

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

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

Submission status: Time Limit Exceeded

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+1)
dp2 = [0] * (N+1)
dp1[N] = 1
dp1[N-1] = 1
dp2[N-1] = 1
reach_last = [0] * N
reach = [sum(row) for row in XD]

reach_last[N-1] = N

for i in range(N-2, -1, -1):
    # initialization
    reach_last[i] = i+1
    search = i + 1
    _search = search
    max_ = i + 1
    while True:
        if search > N - 1: break
        if XD[search][0] < reach[i]:
            if max_ < reach_last[search]:
                max_ = reach_last[search]
            search += 1
        else:break
    if _search == search: continue
    reach_last[i] = max_

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

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

Submission status: Time Limit Exceeded

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+1)
dp2 = [0] * (N+1)
dp1[N] = 1
dp1[N-1] = 1
dp2[N-1] = 1
reach_last = [0] * N
reach = [sum(row) for row in XD]

reach_last[N-1] = N

for i in range(N-2, -1, -1):
    # initialization
    reach_last[i] = i+1
    search = i+1

    while True:
        if search > N-1:break
        _search = search
        tmp_list = []
        while True:
            if search > N-1:break
            if XD[search][0] < reach[i]:
                tmp_list.append(reach_last[search])
                search += 1
            else:break
        if _search == search:break
        if tmp_list == []:break
        reach_last[i] = max(tmp_list)

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

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

Submission status: Time Limit Exceeded

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+1)
dp2 = [0] * (N+1)
dp1[N] = 1
dp1[N-1] = 1
dp2[N-1] = 1
reach_last = [0] * N
reach = [sum(row) for row in XD]

reach_last[N-1] = N

for i in range(N-2, -1, -1):
    reach_last[i] = i+1
    search = i+1
    next_max = reach[i]
    while True:
        if search > N-1:break
        _search = search
        tmp_list = []
        while True:
            if search > N-1:break
            if XD[search][0] < next_max:
                tmp_list.append([search, reach[search]])
                search += 1
            else:break
        if _search == search:break
        reach_last[i] = search
        if tmp_list == []:break
        next_max = max(tmp_list, key=lambda x:x[1])[1]

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
MOD = 998244353

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx - self.N0
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx - self.N0

N = int(readline())
XD = [tuple(map(int, readline().split())) for _ in range(N)]
XD.sort(key = lambda x: (x[0], -x[1]))

sXD = []
seen = set()
for x, d in XD:
    if x not in seen:
        sXD.append((x, d))
        seen.add(x)

N = len(sXD)
table = list(range(N))
T = Segtree(table, -1, initialize = True, segf = max)
X, D = map(list, zip(*sXD))
for i in range(N-1, -1, -1):
    ok = i
    ng = N
    gi = X[i] + D[i]
    while abs(ok-ng) > 1:
        med = (ok+ng)//2
        if X[med] < gi:
            ok = med
        else:
            ng = med
    table[i] = T.query(i, ok+1)
    T.update(i, table[i])

dp = [0]*(N+1)
dp[N] = 1
for i in range(N-1, -1, -1):
    dp[i] = sum(dp[table[i]+1:])
print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
MOD = 998244353

N = int(readline())
XD = [tuple(map(int, readline().split())) for _ in range(N)]
XD.sort(key = lambda x: (x[0], -x[1]))

sXD = []
seen = set()
for x, d in XD:
    if x not in seen:
        sXD.append((x, d))
        seen.add(x)

N = len(sXD)
table = list(range(N))
X, D = map(list, zip(*sXD))
for i in range(N-1, -1, -1):
    ok = i
    ng = N
    gi = X[i] + D[i]
    while abs(ok-ng) > 1:
        med = (ok+ng)//2
        if X[med] < gi:
            ok = med
        else:
            ng = med
    table[i] = max(table[i:ok+1])

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

Submission status: Time Limit Exceeded

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)]
seg_tree_update(N-1,N-1)
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)

ans=[0]*(N+1)
ans[0]=1
ans[data[0]+1]+=1
ans[1]+=ans[0]

for i in range(1,N):
    ans[data[i]+1]=(ans[data[i]+1]+ans[i])%mod
    ans[i+1]=(ans[i+1]+ans[i])%mod


print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
input = sys.stdin.readline
n = int(input())
xd = [list(map(int,input().split())) for i in range(n)]
mod = 998244353
xd.sort()
go = [[] for i in range(n+1)]
come = [-1 for i in range(n+1)]
deg = [0]*(n+1)
move = [-1]*n
xdsum = [(sum(xd[i]),i) for i in range(n)]
xdsum.sort()
for i in range(n-2,-1,-1):
  for j in range(i+1,n):
    if move[j] != -1:
      continue
    if xd[i][0]+xd[i][1] > xd[j][0]:
      move[j] = i+1
for i in range(n):
  if move[i] == -1:
    continue
  come[i+1] = move[i]
  go[move[i]].append(i+1)
  deg[move[i]] += 1
leafls = []
ans = 1
dp = [1]*(n+1)
for i in range(1,n+1):
  if not go[i]:
    leafls.append(i)
    dp[i] = 2
while leafls:
  x = leafls.pop()
  if come[x] == -1:
    ans = ans*dp[x]%mod
    continue
  y = come[x]
  if deg[y] >= 1:
    deg[y] -= 1
    dp[y] = dp[y]*dp[x]%mod
    if deg[y] == 0:
      dp[y] += 1
      leafls.append(y)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
from bisect import bisect_left
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)]

class rmq(object):
    def __init__(self, N):
        self.N0 = 2**(N-1).bit_length()
        self.INF = 2**31-1
        self.data = [self.INF]*(4*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] = min(self.data[2*k+1], self.data[2*k+2])

    # [l,r)の最小値
    def query(self, l, r):
        L = l + self.N0; R = r + self.N0
        s = self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])

            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

tree = rmq(N)
for i in range(N-1,-1,-1):
    j = bisect_left(X,X[i]+D[i])
    tree.update(i,-i)
    tree.update(i,tree.query(i,j))

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

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
INF = 10**18
MOD = 998244353

N = int(input())
robots = [(-INF, INF)]

for _ in range(N):
    x, d = map(int, input().split())
    robots.append((x, x + d))

robots.sort()
stack = list()

tree = [[] for _ in range(N + 1)]

for i in range(N + 1)[::-1]:
    x, r = robots[i]
    while stack and stack[-1][0] < r:
        y, j = stack.pop()
        tree[i].append(j)
    stack.append((x, i))

stack = list()
stack.append(0)

order = [None for _ in range(N + 1)]
order[0] = (0, 0)
od = 0

while stack:
    node = stack.pop()
    for adj in tree[node]:
        if order[adj] is None:
            od += 1
            order[adj] = (od, adj)
            stack.append(adj)

order.sort()
dp = [1 for _ in range(N + 1)]

for od, node in order[::-1]:
    for adj in tree[node]:
        dp[node] *= dp[adj]
    dp[node] += 1
    dp[node] %= MOD

print(dp[0] - 1)

Submission status: Time Limit Exceeded

Solution code:

M = 998244353

n = int(input())
xs = [0] * n
ds = [0] * n
for i in range(n):
    x, d = (int(c) for c in input().split())
    ds[i] = d
    xs[i] = (x,i)

import sys
sys.setrecursionlimit(max(1000,n))

xs.sort()
index = [x[1] for x in xs]
xs = [x[0] for x in xs]
ds = [ds[ind] for ind in index]

def _sub(i):
    # 深さ優先探索しながらi番目以下の組み合わせと、次に調べるべき番号を返す
    if i==n-1:
        return 2, n
    res = 1
    ind = i+1
    while True:
        if (xs[i]+ds[i] <= xs[ind]):
            break
        o, ind = _sub(ind)
        res *= o
        res %= M
        if ind>=n:
            break
    return res+1, ind
out = []
done = 0
while True:
    o, done = _sub(done)
    out.append(o)
    if done>=n:
        break
result = 1
for o in out:
    result *= o
    result %= M
print(result)

Submission status: Time Limit Exceeded

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

N = int(input())
MOD = 998244353
XD = [tuple(map(int, input().split())) for _ in range(N)]
XD.sort()
X = [x for x, _ in XD]
R = [bisect_left(X, x + d) for x, d in XD]

visited = [False] * N

def dfs(i):
    global visited
    if visited[i]:
        return 0
    visited[i] = True

    ret = 1
    for to in range(i + 1, R[i]):
        ret = (ret * (dfs(to) + 1)) % MOD

    return ret

ans = 1
for i in range(N):
    if visited[i]:
        continue

    prd = 1
    for to in range(i + 1, R[i]):
        if not visited[to]:
            prd = (prd * (dfs(to) + 1)) % MOD
    ans = (ans * (prd + 1)) % MOD

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
MOD = 998244353
XD = [tuple(map(int, input().split())) for _ in range(N)]
XD.sort()
X = [x for x, _ in XD]

visited = [False] * N

def dfs(i):
    global visited
    if visited[i]:
        return 0
    visited[i] = True

    x, d = XD[i]

    ret = 1
    for to in range(i + 1, bisect_left(X, x + d)):
        ret = (ret * (dfs(to) + 1)) % MOD

    return ret

ans = 1
for i in range(N):
    if not visited[i]:
        x, d = XD[i]
        prd = 1
        for to in range(i + 1, bisect_left(X, x + d)):
            if not visited[to]:
                prd = (prd * (dfs(to) + 1)) % MOD
        ans = (ans * (prd + 1)) % MOD

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
MOD = 998244353
XD = [tuple(map(int, input().split())) for _ in range(N)]
XD.sort()
X = [x for x, _ in XD]

visited = [False] * N

def dfs(i):
    global visited
    if visited[i]:
        return 0

    x, d = XD[i]

    ret = 1
    for to in range(i + 1, bisect_left(X, x + d)):
        ret *= (dfs(to) + 1)
        ret %= MOD

    visited[i] = True
    return ret % MOD

ans = 1
for i in range(N):
    if not visited[i]:
        x, d = XD[i]
        prd = 1
        for to in range(i + 1, bisect_left(X, x + d)):
            if not visited[to]:
                prd *= (dfs(to) + 1)
                prd %= MOD
        prd += 1
        ans *= prd
        ans %= MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

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

N = int(input())
MOD = 998244353
XD = [tuple(map(int, input().split())) for _ in range(N)]
XD.sort()
X = [x for x, _ in XD]

visited = [False] * N

def dfs(i):
    global visited
    if visited[i]:
        return 0

    x, d = XD[i]

    ret = 1
    for to in range(i + 1, bisect_left(X, x + d)):
        ret *= (dfs(to) + 1)

    visited[i] = True
    return ret % MOD

ans = 1
for i in range(N):
    if not visited[i]:
        x, d = XD[i]
        prd = 1
        for to in range(i + 1, bisect_left(X, x + d)):
            if not visited[to]:
                prd *= (dfs(to) + 1)
                prd %= MOD
        prd += 1
        ans *= prd
        ans %= MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

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


class SegmentTreeRMQ(object):  # 1-indexed
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def update(self, i, x):
        i += self.len
        while i > 0:
            self.array[i] = max(self.array[i], x)
            i >>= 1
        # print(self.array)

    def get(self, i):
        return self.array[i + self.len]

    def query(self, l, r, i, a, b):
        if l == a and r == b:
            return self.array[i]
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, i * 2 + 1, center, b)
        else:
            return max(
                self.query(l, center, i * 2, a, center),
                self.query(center, r, i * 2 + 1, center, b))

    def get_maximum(self, l, r):
        return self.query(l, r, 1, 0, self.len)


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

xd_array = sorted(xd_array, key=lambda x: x[0])
x_array = [i[0] for i in xd_array]
d_array = [i[1] for i in xd_array]

mod = 998244353

tree = SegmentTreeRMQ(N, -1)
ans_array = [0] * (N+1)
ans_array[-1] = 1
for i in range(N-1, -1, -1):
    move = x_array[i] + d_array[i] - 0.1
    max_index = bisect.bisect_left(x_array, move)
    max_move = max(i, tree.get_maximum(i, max_index))
    tree.update(i, max_move)
    ans_array[i] = (ans_array[i+1] + ans_array[max_move + 1]) % mod

print(ans_array[0])

Submission status: Time Limit Exceeded

Solution code:
import bisect
class SegmentTreeRMQ(object):  # 1-indexed
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def update(self, i, x):
        i += self.len
        while i > 0:
            self.array[i] = max(self.array[i], x)
            i >>= 1
        # print(self.array)

    def get(self, i):
        return self.array[i + self.len]

    def query(self, l, r, i, a, b):
        if l == a and r == b:
            return self.array[i]
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, i * 2 + 1, center, b)
        else:
            return max(
                self.query(l, center, i * 2, a, center),
                self.query(center, r, i * 2 + 1, center, b))

    def get_maximum(self, l, r):
        return self.query(l, r, 1, 0, self.len)


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

xd_array = sorted(xd_array, key=lambda x: x[0])
x_array = [i[0] for i in xd_array]
d_array = [i[1] for i in xd_array]

mod = 998244353

tree = SegmentTreeRMQ(N, -1)
ans_array = [0] * (N+1)
ans_array[-1] = 1
for i in range(N-1, -1, -1):
    move = x_array[i] + d_array[i] - 0.1
    max_index = bisect.bisect_left(x_array, move)
    max_move = max(i, tree.get_maximum(i, max_index))
    tree.update(i, max_move)
    ans_array[i] = (ans_array[i+1] + ans_array[max_move + 1]) % mod

print(ans_array[0])

Submission status: Time Limit Exceeded

Solution code:
import bisect


class SegmentTreeRMQ(object):  # 1-indexed
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def update(self, i, x):
        i += self.len
        while i > 0:
            self.array[i] = max(self.array[i], x)
            i >>= 1
        # print(self.array)

    def get(self, i):
        return self.array[i + self.len]

    def query(self, l, r, i, a, b):
        if l == a and r == b:
            return self.array[i]
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, i * 2 + 1, center, b)
        else:
            return max(
                self.query(l, center, i * 2, a, center),
                self.query(center, r, i * 2 + 1, center, b))

    def get_maximum(self, l, r):
        return self.query(l, r, 1, 0, self.len)


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

xd_array = sorted(xd_array, key=lambda x: x[0])
x_array = [i[0] for i in xd_array]
d_array = [i[1] for i in xd_array]

mod = 998244353

tree = SegmentTreeRMQ(N, -1)
index_array = [0] * N
for i in range(N-1, -1, -1):
    move = x_array[i] + d_array[i] - 0.1
    max_index = bisect.bisect_left(x_array, move)
    max_move = tree.get_maximum(i, max_index)
    tree.update(i, max(max_move, i))
    index_array[i] = max(max_move, i)

ans_array = [0] * (N+1)
ans_array[-1] = 1
for i in range(N-1, -1, -1):
    ans_array[i] = (ans_array[i+1] + ans_array[index_array[i] + 1]) % mod

print(ans_array[0])

Submission status: Time Limit Exceeded

Solution code:
import bisect


class SegmentTreeRMQ(object):  # 1-indexed
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def update(self, i, x):
        i += self.len
        while i > 0:
            self.array[i] = max(self.array[i], x)
            i >>= 1
        # print(self.array)

    def get(self, i):
        return self.array[i + self.len]

    def query(self, l, r, i, a, b):
        if l == a and r == b:
            return self.array[i]
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, i * 2 + 1, center, b)
        else:
            return max(
                self.query(l, center, i * 2, a, center),
                self.query(center, r, i * 2 + 1, center, b))

    def get_maximum(self, l, r):
        return self.query(l, r, 1, 0, self.len)


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

xd_array = sorted(xd_array, key=lambda x: x[0])
x_array = [i[0] for i in xd_array]
d_array = [i[1] for i in xd_array]

mod = 998244353

tree = SegmentTreeRMQ(N, -1)

for i in range(N-1, -1, -1):
    move = x_array[i] + d_array[i] - 0.1
    max_index = bisect.bisect_left(x_array, move)
    max_move = tree.get_maximum(i, max_index)
    tree.update(i, max(max_move, i))

ans_array = [0] * (N+1)
ans_array[-1] = 1
for i in range(N-1, -1, -1):
    ans_array[i] = (ans_array[i+1] + ans_array[tree.get(i) + 1]) % mod

print(ans_array[0])

Submission status: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
mod=998244353
n=int(input())
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)//2
    if t[i*2+1]>t[i*2+2]:t[i]=t[i*2+1]
    else:t[i]=t[i*2+2]
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         if L<t[a]:L = t[a]
      if b&1==0:
         b-=1
         if R<t[b]:R = t[b]
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append([int(i) for i in input().split()])
d.sort()
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 tx=dx[i]+dd[i]
 j=bisect.bisect_left(dx,tx)
 tt=qr(i,j)
 if j-1>tt:ud(i,j-1)
 else:ud(i,tt)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])