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:
n = int(input())
xd = []
for i in range(n):
    x, d = map(int, input().split())
    xd.append((x, d))
xd.sort(key=lambda a: a[0])

X = 998244353
es = []
for i, (x, d) in enumerate(xd):
    es.append((x, False, i))
    es.append((x + d - 0.5, True, i))
es.sort(key=lambda a: a[0])

back = [None] * n
last = None
last_id = None
for p, f, i in es:
    if f:
        back[i] = last_id + 1
    else:
        last_id = i

cnt = [0] * (n + 1)
cnt[-1] = 1
for i in range(n):
    b = back[n - i - 1]
    back_cnt = cnt[b]
    score = back_cnt + cnt[n - i]
    while score >= X:
        score -= X
    cnt[n - i - 1] = score
print(cnt[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
# N: 処理する区間の長さ
N0 = 2**(N-1).bit_length()
INF = -1
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

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

X = [0]*N
D = [0]*N
XD = [None]*N
for i in range(N):
    X[i], D[i] = (int(i) for i in input().split())
    XD[i] = (X[i], D[i])
XD.sort()
import bisect

for i in range(N):
    update(i, i)
L = list(range(N))

for i in range(N)[::-1]:
    x, d = XD[i]
    b = bisect.bisect_left(XD, (x+d-0.5, d))-1
    m = query(i,b+1)
    update(i,m)
    L[i] = m

ans = [0]*N
res = 1
for i in range(N)[::-1]:
    if L[i] == i:
        ans[i] = res
        res *= 2
    else:
        ans[i] = ans[L[i]]
        res += ans[i]
print(res)

Submission status: Wrong Answer

Solution code:
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

N = int(input())

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

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

#sample
#n = 5
#A = [1,4,3,2,4]

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

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

#init
#init_max(A)

#A[1]~A[3]の最小値
#print(query_max(1,4)) #4

#A[3]を5に変更
#update_max(3,5)

#A[1]~A[3]の最小値
#print(query_max(1,4)) #5


X = [0]*N
D = [0]*N
XD = [None]*N
for i in range(N):
    X[i], D[i] = (int(i) for i in input().split())
    XD[i] = (X[i], D[i])
XD.sort()
import bisect
L = [i for i in range(N)]
init_max(L)

for i in range(N)[::-1]:
    x, d = XD[i]
    b = bisect.bisect_left(XD, (x+d-0.5, d))-1
    m = query_max(i,b+1)
    update_max(i,m)
    L[i] = m

ans = [0]*N
res = 1
for i in range(N)[::-1]:
    if L[i] == i:
        ans[i] = res
        res *= 2
    else:
        ans[i] = ans[L[i]]
        res += ans[i]
print(res)

Submission status: Wrong Answer

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
MOD = 998244353


XD = [[int(x) for x in readline().split()] for _ in range(N)]

E = []
for x, d in XD:
    E.append((x, 0, 1))
    E.append((x + d - 1, 1, x))

E.sort()

NUM = {}
B = {}
cnt = 0
for x, op, r in E:
    if op == 0:
        cnt += 1
        NUM[x] = cnt
    elif op == 1:
        B[r] = cnt - NUM[r]

C = {}
prev = None
for x, op, r in E:
    if op == 0:
        prev = x
    elif op == 1:
        ad = 0
        if r != prev:
            ad = B[prev]

        C[r] = B[r] + ad

s = 0
for x, d in XD:
    #cnt = NUM[x + d - 1] - NUM[x]
    cnt = C[x]
    m = pow(2, cnt, MOD) - 1
    s += m
    s %= MOD

al = pow(2, N, MOD)
ans = al - s
ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left
MOD = 998244353

# 点更新，区間クエリ
class SegTree:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 要素の更新 (init_list[k]=x)
    def update(self,k,x):
        k += self.num-1 #葉のノードのインデックス
        self.seg[k] = x
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])
     
    # 区間クエリ （区間[l,r)に対する演算結果）
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return max(x,y)


N = int(input())
XD = [list(map(int,input().split())) for _ in range(N)]
XD.sort()
X = []
for x,d in XD:
    X.append(x)

ans = pow(2,N,MOD)
initlist = [0]*N
initlist[-1] = X[-1]
seg = SegTree(N,initlist,segfunc,-10**9-1)



XD_r = reversed(XD[:-1])
i = 1
for x,d in XD_r:
    right = bisect_left(X,x+d) 
    left = N-1-i
    seg.update(left,x+d)
    d2 = seg.query(left,right)
    r2 = bisect_left(X,d2)
    key = r2-left-1
    ans += MOD
    ans -= pow(2,key,MOD)
    ans += 1
    ans %= MOD    
    i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
MOD = 998244353
XD = [tuple(map(int, input().split())) for _ in range(N)]
XD.sort(key=lambda x: x[0])
ans = 1
seq = []
seq_num = 1
reach_i = - float('inf')
for i in range(N-1):
    reach_i = max(XD[i][0] + XD[i][1],reach_i)
    #if XD[i][0] + XD[i][1] <= XD[i+1][0]:  # このロボットは次を起動しない。ここで一区切り # 前のロボが起動させることもあるので最大値保持
    if reach_i <= XD[i+1][0]:  # このロボットは次を起動しない。ここで一区切り # 前のロボが次を起動させることもあるので最大値保持
        seq.append(seq_num)
        seq_num = 1
        reach_i = XD[i][0] + XD[i][1]
        if i == N-2:
            seq.append(seq_num)

    elif i != N-2:  # 次も起動させる
        seq_num += 1
    else: # 最後
        seq_num += 1
        seq.append(seq_num)

for seq_len in seq:
    ans *= (seq_len + 1)  # 先頭のどこから押すかあるいはどれも押さないか
    ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from operator import itemgetter
import bisect
def main():
    input = sys.stdin.readline
    N = int(input())
    XD = [tuple(map(int, input().split())) for _ in range(N)]
    MOD = 998244353

    XD.sort(key=itemgetter(0))
    X = [xd[0] for xd in XD]

    E = [[] for _ in range(N)]
    j = 0
    for i in range(N):
        x, d = XD[i]
        j = bisect.bisect_left(X, x+d, j)
        for k in range(i+1, j):
            E[i].append(k)

    used = [False] * N
    def f(i):
        result = Mint(1, MOD)
        used[i] = True
        for to in E[i]:
            if used[to]: continue
            result *= f(to)
        return result + 1

    ans = Mint(1, MOD)
    for i in range(N):
        if used[i]: continue
        ans *= f(i)
    print(ans)


class Mint:
    def __init__(self, value=0, mod=10**9+7):
        self.value = ((value % mod) + mod) % mod
        self.mod = mod

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, self.mod
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        return (u + self.mod) % self.mod

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.val
    def __neg__(self): return Mint(-self.value, self.mod)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % self.mod
        return self
    def __add__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other) + self.mod) % self.mod
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % self.mod
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other, self.mod)
        self *= other.inverse
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
MOD = 998244353

N = int(input())
robot = []
xs = []
for i in range(N):
    X, D = map(int, input().split())
    robot.append((X,X+D-1))
    xs.append(X)
xs.sort()
robot.sort()
ans = 1
for i in range(N):
    tmp = bisect.bisect_right(xs, robot[i][1]) - bisect.bisect_left(xs, robot[i][0])
    ans += pow(2, N-i-tmp, MOD) 

ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
mod = 998244353
ro = []
st = []
for _ in range(n):
  x,d = map(int,input().split())
  ro.append([x,x+d])
  st.append(x)
ro.sort()
st.sort()
ro.append([10**10,10**10])
st.append(10**10)
#print(ro)
#print(st)
import bisect
ans = [0 for _ in range(n)]
sun = [0 for _ in range(n)]
ans[-1] = 1
sun[-1] = 1
ans.append(0)
for i in range(n-1)[::-1]:
  x,xd = ro[i]
  b = bisect.bisect_left(st,xd)
  ans[i] = (sun[i+1] + ans[b]) % mod
  sun[i] = (sun[i+1] + ans[i]) % mod
#print(ans)
print(sun[0])

Submission status: Wrong Answer

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num =2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [self.ide_ele]*2*self.num
        self.segfunc = segfunc
        
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1] = init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = segfunc(self.seg[2*i+1], self.seg[2*i+2]) 
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res
    
### 使い方 ##
N = int(input())


A = [-1]*N
INF = 10**15
ide_ele = -1
SEG = SegTree(A,ide_ele,max)


LIST = []
XX = []
mod = 998244353

for i in range(N):
    X,D = map(int,input().split())
    XX.append(X)
    LIST.append([X,D])

XX.sort()
LIST.sort(key=lambda x: x[0])

GOTO = [i for i in range(1,N+1)]
for i in range(N):
	SEG.update(i,i+1)
#print(LIST)
import bisect
for i in range(N-1):
    j = N-2-i
    Xj = LIST[j][0]
    Dj = LIST[j][1]
    Nj = bisect.bisect_right(XX, Xj+Dj-1)
    print(Xj,Dj,j+1,Nj)
    NEXT = SEG.query(j+1,Nj)
    if NEXT != -1:
        GOTO[j] = NEXT
        SEG.update(j,NEXT)
    
S = [-1]*(N+1)
S[N] = 1

#print(LIST)
#print(GOTO)
for i in range(N):
    j = N-1-i
    S[j] = S[j+1] + S[GOTO[j]]
    S[j] %= mod

print(S[0])

Submission status: Wrong Answer

Solution code:
M = 998244353

N = int(input())

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

robots.sort()

cm = 1
cs = 1
prev_x = robots[0][0]
prev_r = prev_x + robots[0][1]
for i in range(1, N):
	x, d = robots[i]
	if prev_r <= x:
		new_cm = (cm + cs) % M
		new_cs = (cm + cs) % M
	else:
		new_cm = (cm + cs)  % M
		new_cs = cs
	
	cm = new_cm
	cs = new_cs
	prev_x = x
	prev_r = max(prev_r, x + d)

print((cm + cs) % M)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
from operator import itemgetter


class SegTreeMax:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    def initialize(self, arr):
        for i, v in enumerate(arr, start=self.offset):
            self.tree[i] = v
        for i in range(self.offset - 1, 0, -1):
            j = i << 1
            self.tree[i] = max(self.tree[j], self.tree[j + 1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y >= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_max(self, a, b):
        """
        [a, b)の最大値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = max(result, self.tree[r - 1])
            if l & 1:
                result = max(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


n, *xd = map(int, sys.stdin.buffer.read().split())
xd = sorted(zip(xd[0::2], xd[1::2]))
# print(xd)
xxx = list(map(itemgetter(0), xd))
ans = [0] * (n + 1)
skip = list(range(1, n + 1))
ans[n] = 1
sgt = SegTreeMax(n + 1, 0)
sgt.initialize(list(range(1, n + 2)))
for i in range(n - 1, -1, -1):
    x, d = xd[i]
    r = x + d
    j = bisect_left(xxx, r)
    k = sgt.get_max(i, j)
    # skip[i] = k
    ans[i] = ans[i + 1] + ans[k]
    sgt.update(i, k)
    # print(ans)
    # print(skip)
print(ans[0])

Submission status: Wrong Answer

Solution code:
n = int(input())
mod = 998244353
ro = []
st = []
for _ in range(n):
  x,d = map(int,input().split())
  ro.append([x,x+d])
  st.append(x)
ro.sort()
st.sort()
ro.append([10**10,10**10])
st.append(10**10)
#print(ro)
#print(st)
import bisect
ans = [0 for _ in range(n)]
sun = [0 for _ in range(n)]
ans[-1] = 1
sun[-1] = 1
ans.append(0)
for i in range(n-1)[::-1]:
  x,xd = ro[i]
  b = bisect.bisect_left(st,xd)
  ans[i] = (sun[i+1] + ans[b]) % mod
  sun[i] = (sun[i+1] + ans[i]) % mod
#print(ans)
print(ans[0])

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())

in_dict = {}

for _ in range(N):
    x,d = map(int,input().split())
    in_dict[x] = d
x_list = list(in_dict.keys())
d_list = list(in_dict.values())

in_dict = sorted(in_dict.items(), key=lambda x:x[0])

dp = [0 for _ in range(N)] 
dp[0] = 2
move = np.array([d_list[0]])

for i in range(1,N):
    move = move -1 
    dp[i] = (dp[i-1] - sum(move>0)) **2 + dp[i-1]
    dp[i] = dp[i]%998244353
    
    np.append(move,d_list[i])

print(dp[-1]%998244353)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect, bisect_left
sys.setrecursionlimit(1000000)

def count(i, Edge, Connect):
    if Edge[i] == i: 
        Connect[i] = 0
        return 0
    
    Connect[i] = Edge[i] - i
    if Connect[Edge[i]] > -1: Connect[i] += Connect[Edge[i]]
    else: Connect[i] += count(Edge[i], Edge, Connect)
    return Connect[i]

def solve():
    input = sys.stdin.readline
    N = int(input())
    R = [[int(i) for i in input().split()] for _ in range(N)]
    R.sort()
    mod = 998244353
    X = [R[i][0] for i in range(N)]
    D = [R[i][1] for i in range(N)]
    Edge = [i for i in range(N)]
    Connect = [-1] * N
    for i in range(N):
        k = bisect_left(X, X[i] + D[i])
        Edge[i] = k - 1
    for i in range(N):
        if Connect[i] == -1: count(i, Edge, Connect)

    DP = [0] * N
    DP[N - 1] = 2
    for i in reversed(range(N-1)):
        right = i + Connect[i]
        if right < N - 1: #i番目を動かす
            DP[i] += DP[right]
        else: DP[i] += 1
        DP[i] += DP[i+1] #i番目を動かさない
        DP[i] %= mod
        
    print(DP[0])
    #print(Connect)
    #print(X)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())

in_dict = {}

for _ in range(N):
    x,d = map(int,input().split())
    in_dict[x] = d
x_list = list(in_dict.keys())
d_list = list(in_dict.values())

in_dict = sorted(in_dict.items(), key=lambda x:x[0])

dp = [0 for _ in range(N)] 
dp[0] = 2
move = np.array([d_list[0]])

for i in range(1,N):
    
    dp[i] = (dp[i-1] - sum(move>0)) **2 + dp[i-1]
    dp[i] = dp[i]%998244353
    move = move -1 
    np.append(move,d_list[i])

print(dp[-1]%998244353)

Submission status: Wrong Answer

Solution code:
n = int(input())
mod = 998244353
data = sorted([tuple(map(int,input().split())) for _ in range(n)])
go = [0 for _ in range(n)]
go[n-1] = n-1
for i in range(n-2,-1,-1):
    if data[i][0]+data[i][1] > data[n-1][0]:
        go[i] = n-1
        continue
    ok = i
    ng = n-1
    while ng-ok>1:
        mid = (ng+ok)//2
        if data[i][0]+data[i][1] > data[mid][0]:
            ok = mid
        else:
            ng = mid
    if ok == i:go[i] = i
    else:go[i] = max(ok,go[i+1])
dp = [[0,0] for _ in range(n)]
dp[n-1][0] = 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 go[i] == i:
        dp[i][1] = (dp[i+1][0]+dp[i+1][1])%mod
    elif go[i] == n-1:
        dp[i][1] = 1
    else:
        dp[i][1] = (dp[go[i]+1][0]+dp[go[i]+1][1])%mod

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

Submission status: Wrong Answer

Solution code:
def power_func(a, b, p):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, p)
        return d * d % p
    if b % 2 == 1:
        return (a * power_func(a, b - 1, p)) % p

N = int(input())
P = [list(map(int,input().split())) for i in range(N)]
print(power_func(2,N,998244353))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect, bisect_left
sys.setrecursionlimit(1000000)

def count(i, Edge, Connect):
    if Edge[i] == i: 
        Connect[i] = 0
        return 0
    
    Connect[i] = Edge[i] - i
    if Connect[Edge[i]] > -1: Connect[i] += Connect[Edge[i]]
    else: Connect[i] += count(Edge[i], Edge, Connect)
    return Connect[i]

def solve():
    input = sys.stdin.readline
    N = int(input())
    R = [[int(i) for i in input().split()] for _ in range(N)]
    R.sort()
    mod = 998244353
    X = [R[i][0] for i in range(N)]
    D = [R[i][1] for i in range(N)]
    Edge = [i for i in range(N)]
    Connect = [-1] * N
    for i in range(N):
        k = bisect_left(X, X[i] + D[i])
        Edge[i] = k - 1
    for i in range(N):
        if Connect[i] == -1: count(i, Edge, Connect)

    DP = [0] * N
    DP[N - 1] = 2
    for i in reversed(range(N-1)):
        right = i + Connect[i]
        if right < N - 1: #i番目を動かす
            DP[i] += DP[right + 1]
        else: DP[i] += 1
        DP[i] += DP[i+1] #i番目を動かさない
        DP[i] %= mod
        
    print(DP[0])
    #print(Connect)
    #print(X)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from sys import stdin

MOD = 998244353

n = input()
inp = stdin.readlines()

l = []
for line in inp:
    x, d = map(int, line.strip().split())
    l.append((x, d))

l.sort()

dp = [[0, 0] for i in xrange(n)]
same = [0 for i in xrange(n)]

dp[n - 1] = [1, 2]

for i in xrange(n - 2, -1, -1):
    dp[i][1] = 1 + dp[i + 1][1]
    
    # if collide
    if l[i + 1][0] <= l[i][0] + l[i][1] - 1:
        dp[i][0] = dp[i + 1][0]
    else:
        dp[i][0] = dp[i][1]

    if dp[i][0] >= MOD: dp[i][0] -= MOD
    if dp[i][1] >= MOD: dp[i][1] -= MOD

ans = dp[0][1]
print ans % MOD

Submission status: Wrong Answer

Solution code:
n = int(input())
mod = 998244353
data = sorted([tuple(map(int,input().split())) for _ in range(n)])
go = [0 for _ in range(n)]
go[n-1] = n-1
for i in range(n-2,-1,-1):
    if data[i][0]+data[i][1] > data[n-1][0]:
        go[i] = n-1
        continue
    ok = i
    ng = n-1
    while ng-ok>1:
        mid = (ng+ok)//2
        if data[i][0]+data[i][1] > data[mid][0]:
            ok = mid
        else:
            ng = mid
    if ok == i:go[i] = i
    else:go[i] = max(ok,go[i+1])
print(data)
print(go)
dp = [[0,0] for _ in range(n)]
dp[n-1][0] = 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 go[i] == i:
        dp[i][1] = (dp[i+1][0]+dp[i+1][1])%mod
    elif go[i] == n-1:
        dp[i][1] = 1
    else:
        dp[i][1] = (dp[go[i]+1][0]+dp[go[i]+1][1])%mod

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

Submission status: Wrong Answer

Solution code:
import bisect

mod = 998244353

n = int(input())
x = []
x1 = []
for i in range(n):
    p, q = map(int, input().split())
    x.append([p, p+q])
    x1.append(p)
x.sort()
x1.sort()
y = 0
for i in range(n):
    b = bisect.bisect_left(x1, x[i][1])-i-1
    if b > 0:
        y += 2**(b-1)
print((pow(2, n, mod) - y) % mod)

Submission status: Wrong Answer

Solution code:
n=int(input())
mod=998244353
xd=[tuple(map(int,input().split())) for _ in range(n)]
xd.sort(reverse=True)
ans=2
for i in range(1,n):
    fx,fd=xd[i-1]
    x,d=xd[i]
    if fx < x+d:
        ans=(ans+1)%mod
    else:
        ans=(ans*2)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left

    import sys
    input = sys.stdin.readline
    N = int(input())

    MOD = 998244353

    X = []
    X_append = X.append
    dic = dict() #Xから動ける先の場所

    for _ in range(N):
        x, d = map(int, input().split())
        X_append(x)
        dic[x] = x + d

    X.sort()
    lst = []
    lst_append = lst.append
    for x in X:
        tmp = bisect_left(X, dic[x])
        lst_append(tmp)

    #ここまででどれを動かしたら何番まで消えるかがわかった
    dp = [[-1] * (2) for _ in range(N + 1)]

    dp[N][0] = 1
    dp[N][1] = 0

    class SegmentTree:
        __slots__ = ["_default_value", "_seg_func", "_modifying_func", "_size", "_tree"]

        def __init__(self, initial_values: "Sequence", default_value: "Union[int, str]", seg_func: "Callable",
                    modifying_func: "Optional[Callable]" = None) -> None:
            self._default_value = default_value
            self._seg_func = seg_func
            self._modifying_func = modifying_func
            self._size = 1 << (len(initial_values) - 1).bit_length()
            self._tree = self._build(initial_values)

        def _build(self, initial_values: "Sequence") -> "List":
            """Build a segment tree with initial values."""
            tree = [self._default_value] * (2 * self._size)

            if self._modifying_func:
                initial_values = map(self._modifying_func, initial_values)

            for idx, val in enumerate(initial_values):  # set a tree
                tree[idx + self._size - 1] = val

            for idx in range(self._size - 2, -1, -1):  # build
                tree[idx] = self._seg_func(tree[2 * idx + 1], tree[2 * idx + 2])

            return tree

        def update(self, index: int, value: int) -> None:
            """Update index to value."""
            index += self._size - 1
            if self._modifying_func:
                value = self._modifying_func(value)
            self._tree[index] = value
            while index:
                index = (index - 1) // 2
                self._tree[index] = self._seg_func(self._tree[2 * index + 1], self._tree[2 * index + 2])

        def query(self, left: int, right: int) -> "Union[int, str]":
            """Respond to query in [left, right]."""
            left += self._size
            right += self._size
            result = self._default_value
            while left < right:
                if left & 1:
                    result = self._seg_func(result, self._tree[left - 1])
                    left += 1
                if right & 1:
                    right -= 1
                    result = self._seg_func(result, self._tree[right - 1])
                left >>= 1
                right >>= 1
            return result

    tree = SegmentTree(lst, 0, max, None)

    for i in range(N - 1, -1, -1):
        tmp = max(i + 1, tree.query(i, lst[i])) #動くべき場所
        # print (tmp)
        dp[i][0] = (dp[i + 1][0] + dp[i + 1][1]) % MOD
        dp[i][1] = (dp[tmp][0] + dp[tmp][1]) % MOD
        tree.update(i, tmp)

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

    # for i in range(N - 1, -1, -1):
    #     dp[i][0] = dp[i + 1][0] + dp[i + 1][1]
    #     dp[i][1] = dp[move[i]][0] + dp[move[i]][1]



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import bisect
from operator import itemgetter

N=int(input())
R=[tuple(map(int,input().split())) for i in range(N)]+[(1<<31,1<<31)]
R.sort(key=itemgetter(0))
RMAX=[x+y for x,y in R]

seg_el=1<<(N.bit_length())# Segment treeの台の要素数
SEG=[-1]*(2*seg_el)# 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def update(n,x,seg_el):# A[n]をxへ更新（反映）
    i=n+seg_el
    SEG[i]=x
    i>>=1# 子ノードへ
    
    while i!=0:
        SEG[i]=max(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r):# 区間[l,r)に関するminを調べる
    L=l+seg_el
    R=r+seg_el
    ANS=-1<<30

    while L<R:
        if L & 1:
            ANS=max(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=max(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

for i in range(N-1,-1,-1):
    x=bisect.bisect_left(R,(RMAX[i],0))
    MAX=getvalues(i,x)
    if MAX==-1:
        update(i,x,seg_el)
    else:
        update(i,MAX,seg_el)

mod=998244353


DP=[0]*(N+1)
DP[0]=1

for i in range(N):
    DP[i+1]+=DP[i]
    DP[getvalues(i,i+1)]+=DP[i]

    #print(DP)
print(DP[-1])

Submission status: Wrong Answer

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())

XD = [[int(x) for x in readline().split()] for _ in range(N)]

E = []
for x, d in XD:
    E.append((x, 1))
    E.append((x + d - 1, 2))

E.sort()

NUM = {}
prev = None
for x, p in E:
    if p == 2:
        NUM[x] = prev
    else:
        if prev == None:
            prev = 0
        prev += 1
        NUM[x] = prev

ans = 1
MOD = 998244353

# print(NUM)

s = 0
for x, d in XD:
    cnt = NUM[x + d - 1] - NUM[x]
    m = pow(2, cnt, MOD) - 1
    s += m
    s %= MOD

al = pow(2, N, MOD)
ans = al - s
ans %= MOD
print(ans)