Problem:


Score : 200 points

Problem Statement

In a factory, there are N robots placed on a number line.
Robot i is placed at coordinate X_i and can extend its arms of length L_i in both directions, positive and negative.

We want to remove zero or more robots so that the movable ranges of arms of no two remaining robots intersect.
Here, for each i (1 \leq i \leq N), the movable range of arms of Robot i is the part of the number line between the coordinates X_i - L_i and X_i + L_i, excluding the endpoints.

Find the maximum number of robots that we can keep.

Constraints

1 \leq N \leq 100,000

0 \leq X_i \leq 10^9 (1 \leq i \leq N)

1 \leq L_i \leq 10^9 (1 \leq i \leq N)

If i \neq j, X_i \neq X_j.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 L_1
X_2 L_2
\vdots
X_N L_N

Output

Print the maximum number of robots that we can keep.

Sample Input 1

4
2 4
4 3
9 3
100 5

Sample Output 1

3

By removing Robot 2, we can keep the other three robots.

Sample Input 2

2
8 20
1 10

Sample Output 2

1

Sample Input 3

5
10 1
2 1
4 1
6 1
8 1

Sample Output 3

5



Sample input:
4
2 4
4 3
9 3
100 5


Sample output:
3

Submission status: Wrong Answer

Solution code:
def main():
    n=int(input())
    x=sorted([tuple(map(int,input().split())) for _ in range(n)], key=lambda x: x[0])
    r = -(10**9+1)
    a=0
    for i,l in x:
        if r <= i-l:
            r = i+l
            a += 1
    print(a)
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# 多次元リストの sort に使える
from operator import itemgetter

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

#入力リストに(座標+右側腕の範囲)を要素に追加
for i in range(n):
  x = XLs[i][0]
  l = XLs[i][1]
  XLs[i].append(x+l)

#右手の端の位置でソート
XLs.sort(key=itemgetter(2))
  
#print(XLs)
#範囲を初期化
choice = -10**10 
#残すロボの数を初期化
cnt = 0

#choiceに取り上げたロボを更新していく
#ロボ腕の範囲に競合しないものを取り上げていく
for i in range(n):
  x = XLs[i][0]
  l = XLs[i][1]
  
  if choice <= x-l:
    choice = x+1
    cnt += 1
    
print(cnt)

Submission status: Wrong Answer

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

xllist=[]
for _ in range(N):
  X,L=map(int,input().split())
  xllist.append((X,L))
xllist.sort()
#print(xllist)

dp=[0]*N
dp[0]=1
for i in range(1,N):
  x,l=xllist[i]
  
  pos=bisect.bisect(xllist,(x-l,float("inf")))
  #print(i,pos)
  if pos==0:
    dp[i]=dp[i-1]
  else:
    dp[i]=max(dp[i-1],dp[pos-1]+1)
  
#print(dp)
print(dp[-1])

Submission status: Wrong Answer

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

xllist=[]
for _ in range(N):
  X,L=map(int,input().split())
  xllist.append((X,L))
xllist.sort()
#print(xllist)

dp=[0]*N
dp[0]=1
for i in range(1,N):
  x,l=xllist[i]
  
  pos=bisect.bisect(xllist,(x-l,0))
  #print(i,pos)
  if pos==0:
    dp[i]=dp[i-1]
  else:
    dp[i]=max(dp[i-1],dp[pos-1]+1)
  
#print(dp)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
#区間スケジューリング問題

N = int(input())

robots = {}

for _ in range(N):
    X, L = list(map(int, input().split()))

    robots[X] = (X-L, X+L)

#終端が早い順にソートして、取れるものから貪欲法でとっていく

robots_sorted = sorted(robots.items(), key=lambda x:x[1][1])

ans = 1
current_robot = robots_sorted[0]

for i in range(0, N):
    if current_robot[1][1] >= robots_sorted[i][0]:
        continue

    ans += 1
    current_robot = robots_sorted[i]


print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = [[0]*2 for i in range(n)]
for i in range(n):
    x[i][0], x[i][1] = MAP()

x.sort()
tmp = -inf
ans = n
for i in range(n):
    if tmp > x[i][0] - x[i][1]:
        ans -= 1
        tmp = min(tmp, x[i][0] + x[i][1])
        print(i)
    else:
        tmp = x[i][0] + x[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
arms= []

for i in range(n):
  x,l = map(int,input().split())
  arms.append((x-l,x+l))
 
arms.sort()
arms.sort(key=lambda x:x[1])

maxarm = arms[0][0]
pick = 0
for i in range(1,n):
  if arms[i][0]<maxarm:
    pick += 1
  else:
    maxarm = arms[i][1]
print(n-pick)

Submission status: Wrong Answer

Solution code:
n = int(input())
arms= []

for i in range(n):
  x,l = map(int,input().split())
  arms.append((x-l,x+l))
 
arms.sort()
arms.sort(key=lambda x:x[1])

maxarm = -arms[0][0]
pick = 0
for i in range(1,n):
  if arms[i][0]<maxarm:
    pick += 1
  else:
    maxarm = arms[i][1]
print(n-pick)

Submission status: Wrong Answer

Solution code:
n = int(input())
xlt = []
for i in range(n):
    xi,li = map(int,input().split())
    xlt.append((xi+li,xi-li))
xlt.sort()
ans = 0
x = -float("INF")
for i in range(n):
    if x <= xlt[i][1]:
        ans += 1
        x = xlt[0][0]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
cou = n
l_h = []
for i in range(n):
  x,l  = map(int,input().split())
  l_h.append([x-l,x+l])
l_h.sort(key=lambda x: x[1])
d = deque(l_h)
t= d.popleft()
a,b = t[0],t[1]
for i in range(n-1):
  m= d.popleft()
  c,e= m[0],m[1]
  if b<=c:
    b = c
  else:
    cou -= 1
print(cou)

Submission status: Wrong Answer

Solution code:
def solve(XL, N):
    XL.sort(key=lambda x:x[0])
    count = N
    for i in range(1, N):
        if XL[i][0] < XL[i-1][1]:
            XL[i][1] = XL[i-1][1]
            count -= 1
    return count
N = int(input())
XL = []
for i in range(N):
    x, l = map(int, input().split(' '))
    XL.append([x-l, x+l])
print(solve(XL, N))

Submission status: Wrong Answer

Solution code:
import numpy as np
def solve(XL, N):
    XL.sort(key = lambda x:x[0])
    for i in range(N):
        if XL[i][0] == None:
            pass
        else:
            right = XL[i][0] + XL[i][1]
        for j in range(i+1, N):
            if XL[j][0] == None:
                pass
            elif XL[j][0] - XL[j][1] < right:
                XL[j][0] = None
    count = 0
    for i in range(N):
        if XL[i][0] != 0:
            count += 1
    return count

N = int(input())
XL = []
for i in range(N):
    x, l = map(int, input().split(' '))
    XL.append([x, l])
print(solve(XL, N))

Submission status: Wrong Answer

Solution code:
import copy
import numpy as np
n=int(input())
xl=[]
for i in range(n):
    x,l = map(int,input().split())
    xl.append([x-l,l+x])
#print(xl)
xl = sorted(xl, key=lambda x: x[0],reverse=True)
#print(xl)

ans=0
r=10**5+1
for i in range(len(xl)):
  if xl[i][1]>r:
    continue
  if xl[i][0]<=r:
    r=xl[i][0]
    #print("r",r)
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl.sort()
x = [0] * n
l = [0] * n
for i in range(n):
    x[i], l[i] = xl[i]
ans = 1
p = 0
for i in range(1, n):
    if x[p] + l[p] <= x[i] - l[i]:
        ans += 1
        p = i
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl.sort()
x = [0] * n
l = [0] * n
for i in range(n):
    x[i], l[i] = xl[i]
ans = [False] * n
ans[0] = True
p = 0
for i in range(1, n):
    if ans[p] and x[p] + l[p] <= x[i] - l[i]:
        ans[i] = True
        p = i
print(sum(ans))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl.sort()
x = [0] * n
l = [0] * n
for i in range(n):
    x[i], l[i] = xl[i]
ans1 = [True] * n
for i in range(n):
    if i > 0 and ans1[i - 1] and x[i - 1] + l[i - 1] > x[i] - l[i]:
        ans1[i] = False
ans2 = [True] * n
for i in range(n)[::-1]:
    if i < n - 1 and ans2[i + 1] and x[i] + l[i] > x[i + 1] - l[i + 1]:
        ans2[i] = False
print(max(sum(ans1), sum(ans2)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl.sort()
x = [0] * n
l = [0] * n
for i in range(n):
    x[i], l[i] = xl[i]
ans1 = [True] * n
for i in range(n):
    if i > 0 and ans1[i - 1] and x[i - 1] + l[i - 1] + 1 > x[i] - l[i]:
        ans1[i] = False
ans2 = [True] * n
for i in range(n)[::-1]:
    if i < n - 1 and ans2[i + 1] and x[i] + l[i] > x[i + 1] - l[i + 1]:
        ans2[i] = False
print(max(sum(ans1), sum(ans2)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl.sort()
x = [0] * n
l = [0] * n
for i in range(n):
    x[i], l[i] = xl[i]
ans1 = [True] * n
for i in range(n):
    if i > 0 and ans1[i - 1] and x[i - 1] + l[i - 1] > x[i] - l[i]:
        ans1[i] = False
ans2 = [True] * n
for i in range(n)[::-1]:
    if i < n - 1 and ans2[i + 1] and x[i] + l[i] > x[i + 1] - l[i + 1]:
        ans2[i] = False
print(min(sum(ans1), sum(ans2)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl.sort()
x = [0] * n
l = [0] * n
for i in range(n):
    x[i], l[i] = xl[i]
ans = [True] * n
for i in range(n):
    if i > 0 and ans[i - 1] and x[i - 1] + l[i - 1] > x[i] - l[i]:
        ans[i] = False
print(sum(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
r = [list(map(int,input().split())) for _ in range(n)]
for i in range(n):
  r[i] = [r[i][0] - r[i][1], r[i][0] + r[i][1]]
r.sort(key = lambda x:x[1])
print(r)
cur = -1001001001
ans = 0
for i in range(n):
  if cur <= r[i][0]:
    ans += 1
    cur = r[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
r = [list(map(int,input().split())) for _ in range(n)]
for i in range(n):
  r[i] = [r[i][0] - r[i][1], r[i][0] + r[i][1]]
r.sort()
#print(r)
cur = -1001001001
ans = 0
for i in range(n):
  if cur <= r[i][0]:
    ans += 1
    cur = r[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xl = sorted([list(map(int, input().split())) for _ in range(n)])
now = xl[0][0]+xl[0][1]
ans =1
for x,l in xl[1:]:
    if now <= x-l:
        now = x+l
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xl = sorted([list(map(int, input().split())) for _ in range(n)])
now = 0
ans = 0
for x,l in xl:
    if now < x:
        now += l
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
data = []
for i in range(n):
    x, l = map(int, input().split())
    data.append([x, l])
data = sorted(data, key = lambda x: x[0])
ans = 0
pre = -(10 ** 10)
for i in range(n):
    if data[i][0] - data[i][1] >= pre:
        ans += 1
        pre = data[i][0] + data[i][1]

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
data = []
for i in range(n):
    x, l = map(int, input().split())
    data.append([x, l])
data = sorted(data, key = lambda x: x[0])
ans = 1
pre = data[0][0] + data[0][1]
for i in range(1, n):
    if data[i][0] - data[i][1] >= pre:
        ans += 1
        pre = data[i][0] + data[i][1]

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
XL = [list(map(int, input().split())) for x in range(N)]

XL = sorted(XL, key=lambda x: x[0]+x[1])

cnt = 0
prev_right = -10**9+10
for x, l in XL:
    left = x - l + 1
    right = x + l - 1
    if left > prev_right:
        cnt += 1
        prev_right = right

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
XL = [list(map(int, input().split())) for x in range(N)]

XL = sorted(XL, key=lambda x: x[0]+x[1])

cnt = 0
prev_right = -100000000000
for x, l in XL:
    left = x - l + 1
    right = x + l - 1
    if left <= prev_right:
        cnt += 1
    else:
        prev_right = right

print(N-cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
XL=[]
for _ in range(N):
    a=list(map(int,input().split()))
    XL.append(a)
XL = sorted(XL, key=lambda x:x[0])
#前から順に取っていく
#DP[i]:i番目までのロボットで残せるロボットの最大数
#i番目のロボットがどこまでをカバーしているかを格納する必要がある
DP=[[0,0] for i in range(N)]
DP[0][0]=1#個数
DP[0][1]=XL[0][0]+XL[0][1]#カバーしている距離
for i in range(1,N):
    if XL[i][0]-XL[i][1]>=DP[i-1][1]:
        DP[i][0]=DP[i-1][0]+1
        DP[i][1]=XL[i][0]+XL[i][1]
    else:
        DP[i][0]=DP[i-1][0]
        DP[i][1]=DP[i-1][1]
print(DP[-1][0])

Submission status: Wrong Answer

Solution code:
N = int(input())
T = []

for _ in range(N):
    x, l = map(int,input().split())
    T.append((x, l))

# sort by x
T.sort(key=lambda x: x[0])

lans = 1
llast = 0
for ix in range(1, N):
    if T[llast][0] + T[llast][1] <=  T[ix][0] - T[ix][1]:
        lans += 1
        llast = ix

rans = 1
rlast = N-1
for ix in range(N-2, -1, -1):
    if T[rlast][0] - T[rlast][1] >= T[ix][0] + T[ix][1]:
        rans += 1
        rlast = ix

print(max(lans, rans))

Submission status: Wrong Answer

Solution code:
n = int(input())
X = [[] for _ in range(n)]
for i in range(n):
    x,l = list(map(int, input().split()))
    X[i] = [x-l,x+l]

X.sort(key = lambda x: x[1])
cnt = 0
rIdx = 1
for lIdx in range(n):
    while (lIdx<rIdx<n and X[rIdx][0]<X[lIdx][1]):
        X[rIdx][1] = -1
        rIdx += 1
        cnt += 1
    if rIdx == lIdx:
        rIdx += 1
print(n-cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
L = []
for i in range(n):
    a,b = map(int,input().split())
    L.append([a-b+1,a+b-1])
L.sort()
print(L)
cnt = 0
for i in range(n-1):
    if L[i][1] > L[i+1][0]:
        cnt +=1
        L[i+1] = L[i]
        #L.appendleft([-10**10,-10**10])
print(n-cnt)

Submission status: Wrong Answer

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


N = int(readline())
XL = map(int, read().split())

LR = sorted(
    [(x - l, x + l) for x, l in zip(XL, XL)],
    key=lambda x: x[1])
LR += [(3 * 10 ** 9, 3 * 10 ** 9)]
i = 1
while True:
    if len(LR) - 1 <= i:
        break

    _, pr = LR[i - 1]
    cl, cr = LR[i]
    nl, _ = LR[i + 1]

    if pr <= cl and cr <= nl:
        i += 1
    else:
        del LR[i]

print(len(LR) - 1)

Submission status: Wrong Answer

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


N = int(readline())
XL = map(int, read().split())

LR = sorted(
    [(x - l, x + l) for x, l in zip(XL, XL)],
    key=lambda x: x[1])
LR += [(3 * 10 ** 9, 3 * 10 ** 9)]

remove = [0] * N
count = 1
i = 1
while True:
    if len(LR) - 1 <= i:
        break

    _, pr = LR[i - 1]
    cl, cr = LR[i]
    nl, _ = LR[i + 1]

    if pr <= cl and cr <= nl:
        count += 1
        i += 1
    else:
        del LR[i]

print(count)

Submission status: Wrong Answer

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


N = int(readline())
XL = map(int, read().split())

LR = sorted(
    [(x - l, x + l) for x, l in zip(XL, XL)],
    key=lambda x: x[1])
LR += [(3 * 10 ** 9, 3 * 10 ** 9)]

count = 1
for i in range(1, N):
    _, pr = LR[i - 1]
    cl, cr = LR[i]
    nl, _ = LR[i + 1]

    if pr <= cl and cr <= nl:
        count += 1
    else:
        LR[i] = LR[i - 1]

print(count)

Submission status: Wrong Answer

Solution code:
def main():
    import sys

    readline = sys.stdin.readline

    N = int(readline())
    XL = [list(map(int, readline().split())) for _ in [0] * N]
    arm = [(x + length, x - length) for x, length in XL]
    arm.sort()
    time, ans = 0, 0
    for i in range(N):
        end, start = arm[i]
        if time <= start:
            ans += 1
            time = end
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys

    readline = sys.stdin.readline

    N = int(readline())
    XL = [list(map(int, readline().split())) for _ in [0] * N]
    arm = [(x + length, x - length) for x, length in XL]
    arm.sort()
    time, ans = 0, 0
    for i in range(N):
        end, start = arm[i]
        if time < start:
            ans += 1
            time = end
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys

    readline = sys.stdin.readline

    N = int(readline())
    XL = [list(map(int, readline().split())) for _ in [0] * N]
    arm = [(x + length, x + length) for x, length in XL]
    arm.sort()
    time, ans = 0, 0
    for i in range(N):
        end, start = arm[i]
        if time <= start:
            ans += 1
            time = end
    print(ans)


main()

Submission status: Wrong Answer

Solution code:

n=int(input())
xl=[]
lr=[]
for i in range(n):
    xl.append(list(map(int,input().split())))

xl.sort()

for i in range(n):
    lr.append([xl[i][0]-(xl[i][1]-1),xl[i][0]+(xl[i][1]-1)])
#print(xl)    
#print(lr)


cnt=0
l=lr[0][0]
r=lr[0][1]
for i in range(1,n):
    if r>=lr[i][0]:
        r=min(r,lr[i][1])
        cnt+=1
ans=n-cnt
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
xl=[]
lr=[]
for i in range(n):
    xl.append(list(map(int,input().split())))

xl.sort()

for i in range(n):
    lr.append([xl[i][0]-(xl[i][1]-1),xl[i][0]+(xl[i][1]-1)])
#print(xl)    
#print(lr)


cnt=0
l=lr[0][0]
r=lr[0][1]
for i in range(1,n):
    if r>=lr[i][0]:
        r=min(r,lr[i][0])
        cnt+=1
ans=n-cnt
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
X = []
L = []
for _ in range(n):
    x,l = map(int,input().split())
    X.append(x)
    L.append(l)
add = np.array(X)+np.array(L)
sub = np.array(X)-np.array(L)

cnt = 0
for i in range(n-1):
    if add[i]>sub[i+1]:
        cnt+=1
        add[i+1]=add[i]
        sub[i+1]=sub[i]
print(n-cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
xl=[list(map(int, input().split())) for _ in range(n)]

rl=[]
for x,l in xl:
    right=x-l
    left=x+l
    rl.append([right,left])
rl.sort(key=lambda x: x[1],reverse=True)
# print(rl)

cnt=0
pos=float('inf')
for i in range(n):
    if rl[i][1]<=pos:
        pos=rl[i][0]
        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    xl = [list(map(int, input().split())) for _ in range(n)]
    xl.sort()
    ans1 = 0
    max1 = -float('inf')
    ans2 = 0
    max2 = -float('inf')
    for i in range(n):
        x, l = xl[i]
        if i == 0:
            if max1 <= x - l:
                ans1 += 1
                max1 = x + l
        else:
            if max1 <= x - l:
                ans1 += 1
                max1 = x + l
            if max2 <= x - l:
                ans2 += 1
                max2 = x + l
    print(max(ans1, ans2))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
XL = []
for _ in range(n):
    x, l = map(int, input().split())
    XL.append([x-l, x+l])
XL.sort()
INF = 10**18
cur = -INF
ans = 0
for i in range(n):
    if cur <= XL[i][0]:
        ans += 1
        cur = XL[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
XL = []
for _ in range(n):
    x, l = map(int, input().split())
    XL.append([x-l, x+l])
XL.sort()
XL += [-1]
i = 0
cnt = 1
before = XL[0][1]
while XL[i] != -1:
    if before <= XL[i][0]:
        before = XL[i][1]
        cnt += 1
    i += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
XL = []
for _ in range(n):
    x, l = map(int, input().split())
    XL.append([x-l, x+l])
XL.sort()
XL += [-1]
i = 0
cnt = 1
before = XL[0][1]
while XL[i] != -1:
    if before <= XL[i][0]:
        before = XL[i][0]
        cnt += 1
    i += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
x = []

for _ in range(N):
    X, L = MAP()
    x.append([X-L+1, X+L-1])

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

ans = 0
tmp = -INF
for l, r in x:
    if tmp < l:
        tmp = r
        ans += 1
   

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    N = II()

    xl = []
    for _ in range(N):
        X, L = MII()
        xl.append((X, L))
    
    xl = sorted(xl, key=lambda x: x[0])

    ans = 1
    r = xl[0][0] + xl[0][1]
    for x, l in xl[1:]:
        if r <= x - l:
            r = x + l
            ans += 1
       
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
robot = [0]*n
for i in range(n):
    x,l = map(int,input().split())
    robot[i] = (x-l, x+l)
robot.sort()

ans = 1
right = robot[0][1]
for i in range(1,n):
    if right <= robot[i][0]:
        right = robot[i][1]
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list()
for i in range(n):
    l.append(list(map(int,input().split())))
l.sort(key=lambda x:x[0])
p=[1 for i in l]
for i in range(1,n):
    if p[i-1] and l[i-1][0]+l[i-1][1]>l[i][0]-l[i][1]:
        p[i]=0
        #print(i)
print(sum(p))

Submission status: Wrong Answer

Solution code:
from collections import deque
from sys import stdin
input = stdin.readline


def main():
  N = int(input())
  X_L = [list(map(int, input().split())) for _ in range(N)]
  # print(N)

  X_L.sort(key=lambda x: x[0])
  # print(X_L)

  def min_robots(X_L):
    # print(X_L)
    N = len(X_L)
    added = [0]
    for i in range(1, N):
      pre = added[-1]
      if X_L[pre][0] + X_L[pre][1] <= X_L[i][0] - X_L[i][1]:
        added.append(i)
    return len(added)

  print(min(min_robots(X_L), min_robots(list(map(lambda x: [-x[0], x[1]], (reversed(X_L)))))))


if(__name__ == '__main__'):
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque
from sys import stdin
input = stdin.readline


def main():
  N = int(input())
  X_L = [tuple(map(int, input().split())) for _ in range(N)]
  # print(N)

  X_L.sort(key=lambda x: x[0])
  # print(X_L)

  added = [0]
  for i in range(1, N):
    pre = added[-1]
    if X_L[pre][0] + X_L[pre][1] <= X_L[i][0] - X_L[i][1]:
      added.append(i)
  print(len(added))


if(__name__ == '__main__'):
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
L = []
for _ in range(n):
    x, l = map(int, input().split())
    left = x - l
    right = x + l
    L.append((left, right))
L = sorted(L, key=lambda x: x[0])
ans = 0
prev = -float('inf')
for r in L:
    if r[0] >= prev:
        ans += 1
        prev = r[1]
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

print(XLs)

for i in range(n):
    x = XLs[i][0]
    l = XLs[i][1]
    XLs[i].append(x+l)

print(XLs)

# 右手の端の位置でソート
XLs.sort(key=itemgetter(2))


print(XLs)

choice = -10**10
cnt = 0
for i in range(n):
    x = XLs[i][0]
    l = XLs[i][1]

    if choice <= x-l:
        choice = x+l
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for _ in range(n):
    a.append(list(map(int,input().split())))

d = [[a[i][0]-a[i][1],a[i][0]+a[i][1]] for i in range(n)]

d = sorted(d, key = lambda x: x[1])
#print(d)

b = [-100000000000000000]
c = [0]


for i in range(n):
    for j in range(len(b)):
        if d[i][0] >= b[j]:
            b = [d[i][1]]
            c = [c[j] + 1]
            break
        else:
            b.append(d[i][1])
            c.append(c[j]+1)
    
    #print(b)
    #print(c)

print(max(c))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for _ in range(n):
    a.append(list(map(int,input().split())))

d = [[a[i][0]-a[i][1],a[i][0]+a[i][1]] for i in range(n)]

d = sorted(d, key = lambda x: x[1])
#print(d)

b = [-100000000000000000]
c = [0]


for i in range(n):
    for j in range(len(b)):
        if d[i][0] >= b[j]:
            if d[i][1] in b:
                b = [d[i][1]]
                c = [c[j] + 1]
                break
            else:
                b.append(d[i][1])
                c.append(c[j]+1)
    
    #print(b)
    #print(c)

print(max(c))

Submission status: Wrong Answer

Solution code:
N = int(input())
XL = []
for _ in range(N):
    x, l = map(int, input().split())
    XL.append([x - l, x + l])
XL.sort(key=lambda x: x[1])

res = 0
i = 0
while i + 1 < len(XL):
    if XL[i][1] > XL[i + 1][0]:
        j = i + 2
        while j < len(XL):
            if XL[i][1] <= XL[j][0]:
                i = j - 1
                break
            j += 1
            res += 1
        res += 1
    i += 1

print(N - res)

Submission status: Wrong Answer

Solution code:
n = int(input())
L = []
for i in range(n):
    a,b = map(int,input().split())
    L.append([a-b,a+b])
L.sort()

cnt = 0
for i in range(n-1):
    if L[i][1] > L[i+1][0]:
        cnt +=1
        L[i+1] = L[i]
        #L.appendleft([-10**10,-10**10])
print(n-cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
L = []
for i in range(n):
    a,b = map(int,input().split())
    L.append([a-b,a+b])
L.sort()

cnt = 0
for i in range(n-1):
    if L[i][1] > L[i+1][0]:
        cnt +=1
        L[i],L[i+1] = L[i+1],L[i]
        #L.appendleft([-10**10,-10**10])
print(n-cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
L = []
for i in range(n):
    a,b = map(int,input().split())
    L.append([a-b,a+b])
L.sort()

cnt = 0
for i in range(n-1):
    if L[i][1] > L[i+1][0]:
        cnt +=1
        L[i+1] =[-10**10,-10**10]
print(n-cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())

xl = [[int(i) for i in input().split()] for j in range(n)]

xl= sorted(xl, key = lambda x:(x[0],x[1]))

now = xl[0][0] + xl[0][1]
count = 1

if(n == 1):
    print(1)
else:
    for i in range(1, n):
        if(now <= xl[i][0] - xl[i][1]):
            count += 1
            now = xl[i][0] + xl[i][1]

    print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())

xl = [[int(i) for i in input().split()] for j in range(n)]

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

now = xl[0][0] + xl[0][1]
count = 1

if(n == 1):
    print(1)
else:
    for i in range(1, n):
        if(now <= xl[i][0] - xl[i][1]):
            count += 1
            now = xl[i][0] + xl[i][1]

    print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())

xl = [[int(i) for i in input().split()] for j in range(n)]

xl.sort()

now = xl[0][0] + xl[0][1]
count = 1

if(n == 1):
    print(1)
else:
    for i in range(1, n):
        if(now <= xl[i][0] - xl[i][1]):
            count += 1
            now = xl[i][0] + xl[i][1]

    print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())

xl = [[int(i) for i in input().split()] for j in range(n)]

xl.sort()

now = xl[0][0] + xl[0][1]
count = 1

if(n == 1):
    print(1)
else:
    for i in range(1, n):
        if(now <= xl[i][0] - xl[i][1]):
            count += 1
            now <= xl[i][0] - xl[i][1]

    print(count)

Submission status: Wrong Answer

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

def main():
    N = int(readline())
    XL = [list(map(int, readline().rstrip().split())) for _ in range(N)]
    XL.sort()

    dp = [[0, 0] for _ in range(N)]  # 残ったロボットの個数
    dp[0][0] = 1  # 1番目のロボットを残す
    dp[0][1] = 0  # 1番目のロボットを取り除く

    pre_right = XL[0][0] + XL[0][1]  # 前回までの右端
    for i in range(1, N):
        x, l = XL[i]
        if x - l >= pre_right:
            dp[i][0] = max(dp[i-1]) + 1
        else:
            dp[i][0] = dp[i-1][1] + 1
        pre_right = x + l

        dp[i][1] = max(dp[i-1])
    
    print(max(dp[N-1]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    N = int(readline())
    XL = [list(map(int, readline().rstrip().split())) for _ in range(N)]
    XL.sort()

    dp = [[0, 0] for _ in range(N)]  # 残ったロボットの個数
    dp[0][0] = 1  # 1番目のロボットを残す
    dp[0][1] = 0  # 1番目のロボットを取り除く

    pre_right = XL[0][0] + XL[0][1]  # 前回までの右端
    for i in range(1, N):
        x, l = XL[i]
        if x - l >= pre_right:
            dp[i][0] = dp[i-1][0] + 1
        else:
            dp[i][0] = dp[i-1][1] + 1
        pre_right = x + l

        dp[i][1] = max(dp[i-1][0], dp[i-1][1])
    
    print(max(dp[N-1]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    N = int(readline())
    XL = [list(map(int, readline().rstrip().split())) for _ in range(N)]
    XL.sort()

    dp = [[0, 0] for _ in range(N)]
    dp[0][0] = 1  # 1番目のロボットを残す
    dp[0][1] = 0  # 1番目のロボットを取り除く

    pre_right = XL[0][0] + XL[0][1]  # 前回までの右端
    for i in range(1, N):
        x, l = XL[i]
        if x > pre_right:
            dp[i][0] = dp[i-1][0] + 1
        else:
            dp[i][0] = dp[i-1][1] + 1
        pre_right = x + l

        dp[i][1] = max(dp[i-1][0], dp[i-1][1])
    
    print(max(dp[N-1]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, *XL = map(int, open(0).read().split())
XL = sorted((x - l, x + l) for x, l in zip(*[iter(XL)] * 2))
curr = -float("inf")
ans = 0
for a, b in XL:
    if a >= curr:
        curr = b
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, *XL = map(int, open(0).read().split())
XL = sorted((x - l, x + l) for x, l in zip(*[iter(XL)] * 2))
curr = -float("inf")
ans = 0
for x, l in XL:
    if x - l >= curr:
        curr = x + l
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
(N,), *XL = [list(map(int, s.split())) for s in open(0)]
XL.sort(key=lambda x: x[0] + x[1])
print(XL)
curr = -float("inf")
ans = 0
for x, l in XL:
    if x - l >= curr:
        curr = x + l
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
itv = []
for i in range(n):
    x,l = map(int, input().split())
    start = x - l
    end = x + l
    itv.append([end, start])

itv.sort()

ans, t = 0, 0
for [x, l] in itv:
    if t <= l:
        ans += 1
        t = x

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

l = []
for _ in range(n):
  l.append(list(map(int, input().split())))
  
l = sorted(l)
num = 1
l_max = l[0][0] + l[0][1]

for i in range(1, n):
  if l[i][0] > l_max:
    num += 1
    l_max = l[i][0] + l[i][1]
    
print(num)