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:
n=int(input())
lr=[]
for i in range(n):
  x,l=map(int,input().split())
  lr.append((x-l,x+1))
lr.sort(key=lambda x: x[1])
ans=0
l=-10**18
r=0
for i in range(n):
  if i==0:
    tl,tr=lr[i]
    l=tl
    r=tr
    ans+=1
    continue
  tl,tr=lr[i]
  if tl>=r:
    ans+=1
    r=tr
    l=tl
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
import bisect
L=[]
for i in range(n):
    x,l=map(int,input().split())
    a=x-l+1
    b=x+l-1
    L.append((b,a))
L=sorted(L)
rob=1
bottom=L[0][0]
for i in range(1,n):
    if L[i][1]>bottom:
        rob += 1
        bottom=L[i][0]
print(rob)

Submission status: Wrong Answer

Solution code:
from collections import deque
from operator import itemgetter
def main():
    n = int(input())
    robots = []
    for _ in range(n):
        x, l = map(int, input().split())
        lside = x - l
        rside = x + l
        robots.append((lside, rside))

    robots = sorted(robots, key=itemgetter(1))
    robots = deque(robots)
    a_robot = robots.popleft()
    cnt = n
    while robots:
        robot_next = robots.popleft()
        if a_robot[1] > robot_next[0]:
            cnt -= 1
        else:
            continue
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
XL = [list(map(int, input().split())) for _ in range(N)]
A = []
for x, l in XL:
    A.append([x + l, x - l])
A.sort()
B = []
i = 0
while True:
    B.append(A[i])
    if i == N - 1:
        break
    j = 1
    while True:
        if A[i][0] > A[i + j][1]:
            j += 1
            if i + j >= N - 1:
                break
            continue
        else:
            break
    i = i + j
    if i > N - 1:
        break
print(len(B))

Submission status: Wrong Answer

Solution code:
from collections import deque
from operator import itemgetter
def main():
    n = int(input())
    robots = []
    for _ in range(n):
        x, l = map(int, input().split())
        lside = x - l
        rside = x + l
        robots.append((lside, rside))

    robots = sorted(robots, key=itemgetter(1), reverse=True)
    robots = sorted(robots, key=itemgetter(0))
    robots = deque(robots)
    a_robot = robots.popleft()
    cnt = 1
    while robots:
        robot_next = robots.popleft()
        if a_robot[1] > robot_next[0]:
            continue
        else:
            cnt += 1
            a_robot = robot_next
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
n = int(input())
accum = [0 for _ in range(n)]
x_list = []
for _ in range(n):
    x, l = map(int, input().split())
    x_list.append((x, l))
x_list.sort()
xx = [x[0] - x[1] for x in x_list]
for i in range(n):    
    x, l = x_list[i]
    if i != 0:
        accum[i] += accum[i - 1]
    accum[i] += 1
    index = bisect_right(xx, xx[i] + (l * 2) - 1)
    if index < n:
        accum[index] -= 1
ans = 0
for i in range(n - 1):
    if accum[i + 1] > accum[i]:
        ans += 1
print(n - ans)

Submission status: Wrong Answer

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


def read():
    N = int(input().strip())
    XL = []
    for i in range(N):
        x, l = map(int, input().strip().split())
        XL.append((x, l))
    return N, XL


def solve(N, XL):
    XL.sort()
    r = -10**9-1
    lcount = 0
    for x, l in XL:
        if r <= x - l:
            r = x + l
            lcount += 1
    l = 10**9+1
    rcount = 0
    for x, r in XL[::-1]:
        if l >= x + r:
            l = x - r
            rcount += 1
    return max(lcount, rcount)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

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


def read():
    N = int(input().strip())
    XL = []
    for i in range(N):
        x, l = map(int, input().strip().split())
        XL.append((x, l))
    return N, XL


def solve(N, XL):
    XL.sort()
    r = -10**9-1
    count = 0
    for x, l in XL:
        if r <= x - l:
            r = x + l
            count += 1
    return count


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
def main():
    N, *XL = map(int, open(0).read().split())
    # print(N, XL)
    robots = [0]*N
    for i in range(N):
        X, L = XL[2 * i + 0], XL[2 * i + 1]
        robots[i] = (X - L, X + L)
    robots.sort(key=lambda x: x[1])
    # print(robots)
    ans = 0
    last = robots[0][0] - 1
    for robot in robots:
        if last <= robot[1]:
            last = robot[1]
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
sec = []

for _ in range(N):
    x, l = map(int, sys.stdin.readline().rstrip().split())
    sec.append((x - l + 1, x + l - 1))

sec = sorted(sec, key=lambda x: x[1])
r = -float("inf")
ans = 0
for s, t in sec:
    if r < s:
        ans += 1
        r = t
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
sec = []

for _ in range(N):
    x, l = map(int, sys.stdin.readline().rstrip().split())
    sec.append((x - l + 1, x + l - 1))

sec = sorted(sec, key=lambda x: x[1])
r = -10**10
ans = 0
for s, t in sec:
    if r <= s:
        ans += 1
        r = t
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
sec = []

for _ in range(N):
    x, l = map(int, sys.stdin.readline().rstrip().split())
    sec.append((x - l + 1, x + l - 1))

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

r = -10**10
ans = 0
for s, t in sec:
    if r < s:
        ans += 1
        r = t
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N = int(input())
arms = []
finishtime = float('-inf')
for i in range(N):
    x,l = map(int,input().split())
    arms.append((x-l,x+l))
arms.sort(key=itemgetter(1))
cnt=0
for L,R in arms:
    if R >= finishtime:
        cnt+=1
        finishtime = R
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = [[] for _ in range(N)]
L = [[] for _ in range(N)]

for i in range(N):
    X[i], L[i] = map(int, input().split())


def indexSort(L):
    D = dict(zip(range(len(L)), L))
    E = sorted(D.items(), key=lambda x: x[1])
    F = [e[0] for e in E]
    return F

L1 = [x-l for x, l in zip(X, L)]
L2 = [x+l for x, l in zip(X, L)]


Ind = indexSort(L1)

count = 0
i = 0
while i < len(Ind) - 1:
    now = Ind[i]
    After = Ind[i+1:]

    skip = 0
    for after in After:
        if L2[now] > L1[after]:
            count += 1
            skip += 1
        else:
            break
    i += 1 + skip
print(N - count)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = [[] for _ in range(N)]
L = [[] for _ in range(N)]

for i in range(N):
    X[i], L[i] = map(int, input().split())



def indexSort(L):
    D = dict(zip(range(len(L)), L))
    E = sorted(D.items(), key=lambda x: x[1])
    F = [e[0] for e in E]
    return F

L1 = [x-l for x, l in zip(X, L)]
L2 = [x+l for x, l in zip(X, L)]


Ind = indexSort(L1)

count = 0
i = 0
while i < len(Ind) - 1:
    now = Ind[i]
    After = Ind[i+1:]

    skip = 0
    for after in After:
        if L2[now] > L1[after]:
            count += 1
            skip += 1
    i += 1 + skip
print(N - count)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = [[] for _ in range(N)]
L = [[] for _ in range(N)]

for i in range(N):
    X[i], L[i] = map(int, input().split())
    
def indexSort(L):
    D = dict(zip(range(len(L)), L))
    E = sorted(D.items(), key=lambda x: x[1])
    F = [e[0] for e in E]
    return F

L1 = [x-l for x, l in zip(X, L)]
L2 = [x+l for x, l in zip(X, L)]


Ind = indexSort(L1)


count = 0
i = 0
while i < len(Ind) - 1:
    now = Ind[i]
    after = Ind[i+1]
    if L2[now] > L1[after]:
        count += 1
        i += 1
    i += 1
print(N - count)

Submission status: Wrong Answer

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

ans = 0
last = float('inf')
for l, r in robot:
  if last >= r:
    ans += 1
    last = l
    
print(ans)

Submission status: Wrong Answer

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

ans = 0
last = -float('inf')
for l, r in robot:
  if last <= l:
    ans += 1
    last = r
    
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

N = int(input().strip())
XL_list = [list(map(int, input().rstrip().split())) for i in range(N)]
#-----

section = []

for X,L in XL_list:
    section.append( ( X - L , X + L ) )


section.sort()
prev_tail = -float("inf")
cnt = 0

for left,right in section:
    if prev_tail <= left:
        cnt += 1
        prev_tail = right
        

print(cnt)

Submission status: Wrong Answer

Solution code:
def m():
    N = int(input())
    XL = [list(map(int, input().split())) for _ in range(N)]
    ST = [[xl[0] - (xl[1] - 1), xl[0] + (xl[1] - 1)] for xl in XL]
    ST.sort(key=lambda x: x[1])
    ans = 1
    right = ST[0][1]
    for i in range(1, N):
        if right < ST[i][0]:
            right = ST[i][1]
            ans += 1
    return ans


print(m())

Submission status: Wrong Answer

Solution code:
def m():
    N = int(input())
    XL = [list(map(int, input().split())) for _ in range(N)]
    ST = [[max(xl[0] - (xl[1] - 1), 0), xl[0] + (xl[1] - 1)] for xl in XL]
    ST.sort(key=lambda x: x[1])
    ans = 1
    right = ST[0][1]
    for i in range(1, N):
        if right < ST[i][0]:
            right = ST[i][1]
            ans += 1
    return ans


print(m())

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 = sorted(l,key=lambda x:x[1])

start = l[0][1]
ans = 1
for i in range(1,N):
    if start <= l[i][0]:
        start = l[i][0]
        ans += 1

print(ans)

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 = sorted(l,key=lambda x:x[1])

start = l[0][1]
ans = 1
for i in range(1,N):
    if start <= l[i][0]:
        start = l[i][0]
        ans += 1
        
print(ans)

Submission status: Wrong Answer

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

sg = []

for i in range(n):
    x, l = map(int, input().split())
    sg.append([max(x - l + 1, 0), x + l - 1])

sg.sort()

prev = sg[0]

ans = 0
for i in range(1, n):
    if prev[1] >= sg[i][0]:
        ans += 1
    if prev[1] < sg[i][1]:
        prev = sg[i]

print(n - ans)

Submission status: Wrong Answer

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

sorted_lst = sorted(lst)
num = 0
ans = n
while True:
    tmp = sorted_lst[num][0]
    for i in range(num + 1, n):
        if tmp > sorted_lst[i][1]:
            ans -= 1
            print(num, i)
        else:
            num = i
            break
        if i == n - 1:
            num = i
            break
    if num == n - 1:
        break

print(ans)

Submission status: Wrong Answer

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


def test(array, index, last_position, count, min_count):
    # 除去数が多いパターンは破棄する
    if min_count[0] != -1 and count >= min_count[0]:
        return
    if index + 1 == len(array):
        # print("count:{}".format(count))
        min_count[0] = count if min_count[0] == - \
            1 or count < min_count[0] else min_count[0]
        return
    current = array[index]

    # 前のと手がぶつかる場合は取り除く
    if last_position >= current[2]:
        test(array, index + 1, last_position, count + 1, min_count)
    # 前のとぶつからない場合は取り除かないパターンも
    else:
        test(array, index + 1, index, count, min_count)


N = int(input())
array = [list(map(int, input().split())) for i in range(N)]
for line in array:
    line.append(line[0] - line[1])
    line.append(line[0] + line[1])
array = sorted(array, key=lambda x: x[3])

min_count = [-1]
test(array, 0, -1, 0, min_count)
print(len(array) - min_count[0])

Submission status: Wrong Answer

Solution code:
import sys,bisect

input=sys.stdin.readline

N=int(input())
robot=[]
for i in range(N):
    robot.append(tuple(map(int,input().split())))

robot.sort()
pos=[robot[i][0]+robot[i][1] for i in range(N)]
arm=[-1]*N
for i in range(0,N):
    index=bisect.bisect_right(pos,robot[i][0]-robot[i][1])
    arm[i]=index-1

dp=[0]*N
dp[0]=1
Max=[0]*N
Max[0]=1
for i in range(1,N):
    if arm[i]==-1:
        dp[i]=1
    else:
        dp[i]=1+Max[arm[i]]
    Max[i]=max(dp[i],Max[i-1])

print(max(dp))

Submission status: Wrong Answer

Solution code:
import sys,bisect

input=sys.stdin.readline

N=int(input())
robot=[]
for i in range(N):
    robot.append(tuple(map(int,input().split())))

robot.sort()
pos=[robot[i][0] for i in range(N)]
arm=[-1]*N
for i in range(0,N):
    index=bisect.bisect_right(pos,robot[i][0]-robot[i][1])
    arm[i]=index-1

dp=[0]*N
dp[0]=1
for i in range(1,N):
    if arm[i]==-1:
        dp[i]=1
    else:
        dp[i]=1+dp[arm[i]]

print(max(dp))

Submission status: Wrong Answer

Solution code:
n = int(input())

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

#print(Robo)
biggest_right = 2 * -10**9 - 1
counter = 0
for left, right in Robo:
    if biggest_right <= left:
        counter += 1
        biggest_right = max(right, biggest_right)
print(counter)

Submission status: Wrong Answer

Solution code:
n=int(input())
m=[]
for i in range(n):
  x,l=map(int,input().split())
  m.append([x-l,x+l])
m=sorted(m, key=lambda student: student[0])
right=m[0][1]
removed=0
for i in range(1,n):
  if m[i][0]<right:
    removed+=1
    if m[i][1]<right:
      right=m[i][1]
print(n-removed)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N=len(v)
    size=len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    s = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    l=[(s[i][0]+s[i][1]-1,s[i][0]-s[i][1]+1) for i in range(N)]
    l.sort()

    cur=l[0][0]
    ans=1
    for rob in l[1:]:
        if cur>=rob[1]:
            continue
        ans+=1
        cur=rob[0]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
XL=sorted(tuple(map(int,input().split())) for i in range(N))
count=0
left=-10**9
for x,l in XL:
    if left<=x-l:
        count+=1
        left=x+l
print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())

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

tmp=-(10**10)
ans=0
for i in range(N):
    end,start=robot[i]
    if tmp<start:
        tmp=end
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

robot=[]
for _ in range(N):
    x,l=map(int,input().split())
    robot.append((x+l-1,x-l+1))
robot.sort(reverse=True)

tmp=-(10**10)
ans=0
for i in range(N):
    end,start=robot[i]
    if tmp<start:
        tmp=end
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

robot=[]
for _ in range(N):
    x,l=map(int,input().split())
    robot.append((x+l-1,x-l+1))
robot.sort(reverse=True)

tmp=-10**10
ans=0
for i in range(N):
    end,start=robot[i]
    if tmp<start:
        tmp=end
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

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

tmp=-10**10
ans=0
for i in range(N):
    end,start=robot[i]
    if tmp<start:
        tmp=end
        ans+=1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N = int(input())
l = [list(map(int, input().split())) for _ in range(N)]
ans = []
for i in range(N):
  l[i].append(l[i][0] - l[i][1])
  l[i].append(l[i][0] + l[i][1])
  del l[i][:2]
l.sort(key = itemgetter(1))
cnt = 0
for i in range(1, N):
  for j in range(i, -N, -1):
    print(i,j,l)
    if l[j-1][0] == - 10 ** 9:
      continue
    if l[i][0] < l[j-1][1]:
        l[i][0] = - 10 ** 9
        l[i][1] = - 10 ** 9
        cnt += 1
    break
print(N-cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
XL = [list(map(int, input().split())) for _ in range(N)]
X, L = [list(i) for i in zip(*XL)]

robot_range = list(map(lambda xl: (xl[0]-xl[1], xl[0]+xl[1]), XL))
robot_range.sort(key=lambda x: x[1])

now_r = -10*100
cnt = 0
for v in robot_range:
    l, r = v
    if now_r <= l:
        cnt += 1
        now_r = r

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
XL = [list(map(int, input().split())) for _ in range(N)]
X, L = [list(i) for i in zip(*XL)]

robot_range = list(map(lambda xl: (xl[0]-xl[1], xl[0]+xl[1]), XL))
robot_range.sort()

now_r = -10*100
cnt = 0
for v in robot_range:
    l, r = v
    if now_r <= l:
        cnt += 1
        now_r = r

print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[]
for i in range(N):
    x,l=map(int,input().split())
    a,b=x-l,x+l
    L.append((a,b))
L.sort()
#print(L)
robot=1
b=L[0][1]
for i in range(1,N):
    A,B=L[i]
    if A>=b:
        robot+=1
        b=B
print(robot)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[]
for i in range(N):
    x,l=map(int,input().split())
    a,b=x-l,x+l
    L.append((a,b))
#print(L)
robot=1
b=L[0][1]
for i in range(1,N):
    A,B=L[i]
    if A>=b:
        robot+=1
        b=B
print(robot)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
XL = li2(N)
R = dp2(0, 2, N)

for i in range(N):
    R[i][0] = XL[i][0] - XL[i][1]
    R[i][1] = XL[i][1] - XL[i][0]

m = -float('inf')
cnt = 0
for i in range(N):
    if R[i][0] > m:
        cnt += 1
        m = R[i][1]

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    robots = {}
    for _ in range(N):
        x,l = [int(x) for x in input().split()]
        robots.update({x-l:x+l})

    # print(sorted(robots.items(), key=lambda x:x[1]))
    cnt = 0
    t = -float('inf')
    for start,end in sorted(robots.items(), key=lambda x:x[1]):
        # print(t,start)
        if t <= start:
            # print('append')
            cnt += 1
            t = end
    print(cnt)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    robots = {}
    for _ in range(N):
        x,l = [int(x) for x in input().split()]
        robots.update({x-l:x+l})

    print(sorted(robots.items(), key=lambda x:x[1]))
    cnt = 0
    t = -float('inf')
    for start,end in sorted(robots.items(), key=lambda x:x[1]):
        print(t,start)
        if t <= start:
            print('append')
            cnt += 1
            t = end
    print(cnt)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    robots = {}
    for _ in range(N):
        x,l = [int(x) for x in input().split()]
        robots.update({x-l:x+l})

    # print(sorted(robots.items(), key=lambda x:x[1]))
    cnt = 0
    t = -10**10
    for start,end in sorted(robots.items(), key=lambda x:x[1]):
        if t <= start:
           cnt += 1
           t = end
    print(cnt)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    robots = {}
    for _ in range(N):
        x,l = [int(x) for x in input().split()]
        robots.update({x-l:x+l})

    # print(sorted(robots.items(), key=lambda x:x[1]))
    cnt = 0
    t = -10**9
    for start,end in sorted(robots.items(), key=lambda x:x[1]):
        if t <= start:
           cnt += 1
           t = end
    print(cnt)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    robots = {}
    for _ in range(N):
        x,l = [int(x) for x in input().split()]
        robots.update({x-l+1:x+l-1})

    # print(sorted(robots.items(), key=lambda x:x[1]))
    cnt = 0
    t = -10**9
    for start,end in sorted(robots.items(), key=lambda x:x[1]):
        if t <= start:
           cnt += 1
           t = end
    print(cnt)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    robots = {}
    for _ in range(N):
        x,l = [int(x) for x in input().split()]
        robots.update({x:x+l})

    # print(sorted(robots.items(), key=lambda x:x[1]))
    append_robots = []
    for x,xl in sorted(robots.items(), key=lambda x:x[1]):
        if len(append_robots) == 0:
            append_robots.append((x,xl))
            continue
        ax,axl = append_robots[-1]
        if axl <= x-(xl-x):
            append_robots.append((x,l))
    print(len(append_robots))
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

xl.sort()

ans = N
rpre = xl[0][0] + xl[0][1]

for x, l in xl[1:]:
    ll = max(x - l, 0)
    rr = x + l
    if ll < rpre:
        ans -= 1
    else:
        rpre = rr

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl.sort(key=lambda x: x[0])
prev = 0
cnt = 0
for i in range(1, n):
    if xl[prev][0]+xl[prev][1] > xl[i][0] - xl[i][1]:
        cnt += 1
    else:
        prev = i
print(n-cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl.sort(key=lambda x: x[0])
prev = 0
cnt = 0
for i in range(1, n):
    if xl[prev][0]+xl[prev][1] > xl[i][0] - xl[i][1]:
        cnt += 1
    else:
        prev = 1
print(n-cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
R = sorted([list(map(int, input().split())) for i in range(N)])
T = []
for i in range(N):
    T.append([R[i][0] + R[i][1], i])
T.sort()

while len(T) - 1 > 0:
    t = T.pop(0)
    print(t[0], R[t[1] + 1][0], R[t[1] + 1][1])
    if t[0] > R[t[1] + 1][0] - R[t[1] + 1][1]:
        N -= 1
        R[t[1] + 1][1] = 0
        T.pop(0)
print(N)

Submission status: Wrong Answer

Solution code:
N = int(input())
R = sorted([list(map(int, input().split())) for i in range(N)])
n = N
for i in range(1, N - 1):
    if R[i + 1][0] - R[i][0] < R[i][1] + R[i + 1][1]:
        n -= 1
        R[i][1] = 0
if R[N - 1][0] - R[N - 2][0] < R[N - 2][1] + R[N - 1][1]:
        n -= 1
print(n)

Submission status: Wrong Answer

Solution code:
N = int(input())
R = sorted([list(map(int, input().split())) for i in range(N)])

for i in range(1, N - 1):
    if R[i + 1][0] - R[i][0] < R[i][1] + R[i + 1][1]:
        N -= 1
        R[i][1] = 0
if R[N - 1][0] - R[N - 2][0] < R[N - 2][1] + R[N - 1][1]:
        N -= 1
print(N)

Submission status: Wrong Answer

Solution code:
n = int(input())
xl = []
for i in range(n):
    x,l = map(int,input().split())
    xl.append([x,x+l])
xl.sort(key = lambda x: x[1])
ans = 0
arm = 0
for i in range(n):
    if arm<xl[i][0]:
        ans += 1
        arm = xl[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xl = []
for i in range(n):
    x,l = map(int,input().split())
    xl.append([x,l])
xl.sort(key = lambda x: x[1])
ans = 0
arm = 0
for i in range(n):
    if arm <= xl[i][0]:
        ans += 1
        arm = xl[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xl = []
for i in range(n):
    x,l = map(int,input().split())
    xl.append([x,l])
xl.sort(key = lambda x: x[1])
ans = 0
arm = 0
for i in range(n):
    if arm < xl[i][0]:
        ans += 1
        arm = xl[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:

n = int(input())
X = []
for _ in range(n):
    x, l = map(int, input().split())
    X.append((x, x + l))

count = 0
current = -1 * float('inf')
for x in sorted(X, key=lambda x: x[1]):
    if x[0] >= current:
        count += 1
        current = x[1]
print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=sorted([list(map(int,input().split())) for i in range(n)],key=sum,reverse=1)
now=float("INF")
ans=0
for i in l:
    if sum(i)<=now:
        now=i[0]-i[1]
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
import sys
l=[i.rstrip().split() for i in sys.stdin.readlines()]
l=[list(map(int,i)) for i in l]
l=[[i-j,i+j] for i,j in l]
from operator import itemgetter
l.sort(key=itemgetter(1))
ans=N
for i in range(N-1):
   end=l[i][1]
   if l[i+1][0] < end:
      ans-=1
   else:
      end=l[i+1][1]
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ST = []
for i in range(N):
    x, l = list(map(int, input().split()))
    ST.append([x-l, x+l])
ST.sort(key = lambda x :x[1])
startT = ST[0][1]
ans = 1
if N != 1:
    for i in range(1,N):
        if startT >= ST[i][0]:
            continue
        else:
            startT = ST[i][1]
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ST = []
for i in range(N):
    x, l = list(map(int, input().split()))
    ST.append([x-l+1, x+l-1])
ST.sort(key = lambda x :x[1])
startT = ST[0][1]
ans = 1
if N != 1:
    for i in range(1,N):
        if startT >= ST[i][0]:
            continue
        else:
            startT = ST[i][1]
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ST = []
for i in range(N):
    x, l = list(map(int, input().split()))
    ST.append([x-l+1, x+l-1])
ST.sort(key = lambda x :x[1])
startT = ST[0][1]
ans = 1
for i in range(1,N):
    if startT >= ST[i][0]:
        continue
    else:
        startT = ST[i][1]
        ans += 1
print(ans)

Submission status: Wrong Answer

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

n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl2 = sorted([[x + l - 1, x - l + 1] for x, l in xl])

ans = 0
mr = xl2[0][1] - 1
for r, l in xl2:
    if l > mr:
        ans += 1
        mr = r
print(ans)

Submission status: Wrong Answer

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

n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl2 = sorted([[x + l, x - l] for x, l in xl])

ans = 0
mr = xl2[0][0] - 1
for r, l in xl2:
    if l > mr:
        ans += 1
        mr = r
print(ans)

Submission status: Wrong Answer

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

n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl2 = sorted([[x - l, x + l] for x, l in xl])

ans = 0
mr = xl2[0][0] - 1
for l, r in xl2:
    if l > mr:
        ans += 1
        mr = r
print(ans)

Submission status: Wrong Answer

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

n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl2 = sorted([[x - l + 1, x + l - 1] for x, l in xl])

ans = 0
mr = xl2[0][0] - 1
for l, r in xl2:
    if l > mr:
        ans += 1
        mr = r
print(ans)

Submission status: Wrong Answer

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

n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
xl2 = sorted([[x - l + 1, x + l - 1] for x, l in xl])

ans = n
mr = xl2[0][0] - 1
for l, r in xl2:
    if l <= mr:
        ans -= 1
    else:
        mr = r

print(ans)