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: Accepted

Solution code:
n = int(input())
lis=[]
count=0
for i in range(n):
    li=[None]*2
    x, l = map(int, input().split())
    li[0] = x+l
    li[1] = x-l
    lis.append(li)
lis.sort()
kari_r = -(10 ** 18)
for r, l in lis:
        if kari_r > l:
            continue
        count+=1
        kari_r = r
            
print(count)

Submission status: Accepted

Solution code:
INF = float("inf")

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

    res = []
    cur = -INF
    for s, t in A:
        if cur <= s:
            cur = t
            res.append((s, t))

    return res

N, *XL = map(int, open(0).read().split())

A = [(x - l, x + l) for x, l in zip(*[iter(XL)] * 2)]
print(len(interval_scheduling(A)))

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数

N = iin()
XL = sorted([iln() for _ in range(N)], key=lambda x:x[0]+x[1])

prev_r = XL[0][0]+XL[0][1]
ans = 1
for i in range(1, N):
    if prev_r <= XL[i][0]-XL[i][1]:
        ans += 1
        prev_r = XL[i][0]+XL[i][1]
print(ans)

Submission status: Accepted

Solution code:
N, *XL = map(int, open(0).read().split())

A = sorted(((x + l, x - l) for x, l in zip(*[iter(XL)] * 2)), key=lambda x: x[0])

ans = 0
cur = -10 ** 9
for t, s in A:
    if cur <= s:
        cur = t
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, *XL = map(int, open(0).read().split())

A = sorted((x + l, x - l) for x, l in zip(*[iter(XL)] * 2))

ans = 0
cur = -10 ** 9
for t, s in A:
    if cur <= s:
        cur = t
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
robot = []
for _ in range(N):
  r = []
  x, l = map(int, input().split())
  a = x + l - 1
  b = x - l
  r += [a, b]
  robot.append(r)
Robot = sorted(robot)

robot_count = [Robot[0]]
for i in range(1, N):
  if Robot[i][1] > robot_count[-1][0]:
    robot_count.append(Robot[i])

print(len(robot_count))

Submission status: Accepted

Solution code:
n = int(input())
x = [0]*n
l = [0]*n
for i in range(n):
    x[i] , l[i] = map(int, input().split())
itv = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
    a = x[i]+l[i]
    b = x[i]-l[i]
    itv[i][0] = a
    itv[i][1] = b
itv.sort()

ans = 0
curx = -10000000000

for i in range(n):
    if curx <= itv[i][1]:
        curx = itv[i][0]
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

robots = []

# ロボットを設定する
for _ in range(N):
    x, l = map(int, input().split())
    robots.append([x-l, x+l])
    
# 手の届く最大値でソートする
robots = sorted(robots, key=lambda x: x[1])

# Maxが小さいもの優先で選択する
pos = robots[0][1]
cnt = 1
for i in range(1, len(robots)):
    robo = robots[i]
    if robo[0] >= pos:
        pos = robo[1]
        cnt += 1

print(cnt)

Submission status: Accepted

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

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

a.sort()

ans = 1
hold = a[0]

for i in range(1,n):
    temp = a[i]
    if(hold[0] <= temp[1]):
        hold = temp
        ans += 1
        
    
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
r=[]
cnt=1

for _ in range(n):
    x,l=map(int,input().split())
    s=x-l
    t=x+l
    r.append([s,t])
    
r=sorted(r,key=lambda x: x[1])
t0=r[0][1]

for s,t in r[1:]:
    if t0<=s:
        cnt+=1
        t0=t

print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    lis = []
    for _ in range(n):
        x, l = LI()
        lis.append((x + l, x - l))
    lis.sort()
    ans = 0
    now = -inf
    for r, l in lis:
        if now <= l:
            now = r
            ans += 1
    print(ans)
    return


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

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
    x, l = map(int, input().split())
    A.append([x+l, x-l])
A.sort()
ans = 1
check1 = A[0]
for i in range(1, N):
    check2 = A[i]
    if check1[0] <= check2[1]:
        ans += 1
        check1 = check2
print(ans)

Submission status: Accepted

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

ans = 1
bef = a[0]

for i in range(1,n):
    aft = a[i]
    if (bef[0] <= aft[1]):
        bef = aft
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
#import numpy as np

mod=int(10**9+7)
inf=int(10**20)

#main
N=int(input())
A=[]
for a in range(N):
    x,l=map(int,input().split())
    A.append([x-l,x+l])

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

ans=0
n=-inf
for a in range(len(A)):
    b=A[a]
    if n<=b[0]:
        n=b[1]
        ans+=1
print(ans)

Submission status: Accepted

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

robots.sort(key=lambda x: x[1])  # 終端を昇順ソート
# print(robots)
cnt = 0
last = -10**18  # 最初、最右のものははるか左側にあると考える
for left, right in robots:
    if left >= last:  # 残せるのであれば
        cnt += 1
        last = right
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
xl_lis = [list(map(int,input().split())) for i in range(n)]
tempx = -(10**10)
ans = 0
xl_lis.sort()
# print(xl_lis)
for i in xl_lis:
    a = i[0]
    b = i[1]
    if tempx > a - b and tempx < a + b:
        ans += 1
    
    elif tempx > a - b and tempx >= a + b:
        ans += 1
        tempx = a + b
    else:
        tempx = a + b
print(n-ans)

Submission status: Accepted

Solution code:
n = int(input())
xl_lis = [list(map(int,input().split())) for i in range(n)]
tempx = -(10**10)
ans = 0
xl_lis.sort()
# print(xl_lis)
for i in xl_lis:
    if tempx > i[0] - i[1] and tempx < i[0] + i[1]:
        ans += 1
    
    elif tempx > i[0] - i[1] and tempx >= i[0] + i[1]:
        ans += 1
        tempx = i[0] + i[1]
    else:
        tempx = i[0] + i[1]
print(n-ans)

Submission status: Accepted

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

for i in range(1,n):
    if ls[i][0] < ls[i-1][1]:
      ls[i][1] = ls[i-1][1]
      ans -=1
        
print(ans)

Submission status: Accepted

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

for _ in range(N):
    x, l = map(int, input().split())
    s = x - l
    t = x + l
    R.append((s, t))
    
R.sort(key=lambda r:r[1])

cnt = 1
t0 = R[0][1]

for s, t in R[1:]:
    if t0 <= s:
        cnt += 1
        t0 = t

print(cnt)

Submission status: Accepted

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

def main():
    N = int(input())
    LR = [[int(i) for i in input().split()] for _ in range(N)]

    # 区間を右端の小さい順にソート
    LR = sorted([(x-l, x+l) for x,l in LR],key=lambda x: x[1])

    ans = 0
    # 現在選んでいる区間の内、最も右にある区間の右端
    cur_R = -float("inf")

    for i in range(N):
        # 区間が被るとき
        if cur_R > LR[i][0]:
            continue
        ans += 1
        cur_R = LR[i][1]

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
LR = [[int(i) for i in input().split()] for _ in range(N)]

# 区間を右端の小さい順にソート
LR = sorted([(x-l, x+l) for x,l in LR],key=lambda x: x[1])

ans = 0
# 現在選んでいる区間の内、最も右にある区間の右端
cur_R = -float("inf")

for i in range(N):
    # 区間が被るとき
    if cur_R > LR[i][0]:
        continue
    ans += 1
    cur_R = LR[i][1]

print(ans)

Submission status: Accepted

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

    ans = 1
    min_value = data[0][1]
    for i in range(1, n):
        if min_value <= data[i][0]:
            ans += 1
            min_value = data[i][1]

    print(ans)


main()

Submission status: Accepted

Solution code:
n=int(input())
points = []
for _ in range(n):
  X,L = map(int,input().split())
  points.append([X+L, X -L])
points.sort(key = lambda x: x[0])
cur = -10**9
answer = 0
for point in points:
  if point[1] >= cur:
    answer += 1
    cur = point[0]
print(answer)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
    
n = int(input())
arm_range = []
for i in range(n):
    x, l = map(int, input().split())
    arm_range.append([x-l, x+l])

arm_range.sort(key=lambda x: x[1])
high = -float('inf')
count = 0
for a in arm_range:
    if a[0] >= high:
        high = a[1]
        count += 1

print(count)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    xl = sorted([LI() for _ in range(n)], key=lambda x: [sum(x), x])
    r = 0
    c = -inf
    for x,l in xl:
        if x-l >= c:
            r += 1
            c = x+l

    return r


print(main())

Submission status: Accepted

Solution code:
# Keyence 2020 B
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
n=ni()
l=[]
for i in range(n):
    a,b=nm()
    l.append([a+b,a-b])
l.sort(key=lambda x:x[0])

cur=-10**9
ans=0
for ll in l:
    if ll[1]>=cur:
        ans+=1
        cur=ll[0]
print(ans)

Submission status: Accepted

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

robots = sorted(robots, key=lambda x: x[1])
robots.append([-2*10**9, 2*10**9])

cnt = 1
current_end = robots[0][1]
for i in range(1, n):
    if current_end <= robots[i][0]:
        cnt += 1
        current_end = robots[i][1]

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
A.sort(key=lambda x:x[0])
X = []
L = []
for l in A:
    X.append(l[0])
    L.append(l[1])

pl = X[0] + L[0]
k = 0
for i in range(1, N):
    pr = X[i] - L[i]
    if pl > pr:
        k += 1
        pl = min(pl, X[i] + L[i])
    else:
        pl = X[i] + L[i]


print(N - k)

Submission status: Accepted

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

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: Accepted

Solution code:
N = int(input())
XL = [tuple(map(int, input().split())) for _ in range(N)]
XL.sort(key=lambda x: x[0]+x[1])
cnt = 0
now = 10 ** 9 * -1
for x, l in XL:
    if now <= x - l:
        cnt += 1
        now = x + l

print(cnt)

Submission status: Accepted

Solution code:
# 2020/01/18
# キーエンス プログラミング コンテスト 2020 - B

from operator import itemgetter

# Input
n = int(input())

in_list = list()

for i in range(n):
    wl = list()
    x, l = map(int, input().split())
    xl = x - l
    xr = x + l
    wl.append(x)
    wl.append(l)
    wl.append(xl)
    wl.append(xr)
    in_list.append(wl)

in_list.sort(key=itemgetter(3))

# Calc
wkx_a = in_list[0][0]
wkl_a = in_list[0][1]
wkxr_a = in_list[0][3]
ans = 1

for i in range(1, n):
    x = in_list[i][0]
    l = in_list[i][1]
    if wkxr_a <= in_list[i][2]:
        wkx_a = x
        wkl_a = l
        wkxr_a = in_list[i][3]
        ans = ans + 1

# Output
print(ans)

Submission status: Accepted

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

for i in range(n):
    a[i].append(a[i][0]-a[i][1])
    a[i].append(a[i][0]+a[i][1])

a.sort(key=lambda x: x[3])

left=-float('inf')
count=0
for i in range(n):
    if a[i][2]>=left:
        count+=1
        left=a[i][3]

print(count)

Submission status: Accepted

Solution code:

a = int(input())
A = []
for i in range(a):
    x,L = map(int,input().split())
    A.append([x+L,x,L])
A.sort()
# print(l)
res = 1
t = A[0]
for i in range(1,a):
    l = A[i]
    # print(t,l)
    if t[0] < l[0] :
        if l[1]-l[2]<t[0]<l[0]:continue
        else:
            res+=1
            t = l
    elif t[0] > l[0]: 
        if l[1]-l[2]<t[1]-t[2]<l[0]:continue
        else:
            res+=1
            t = l
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
sec=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    sec[i][0]+=sec[i][1]
    sec[i][1]*=-2
    sec[i][1]+=sec[i][0]
sec.sort()

ans=0
#-inf
t=-10000000000
for i in range(n):
    #=をつけるのを忘れずに
    if t<=sec[i][1]:#スタートがロボットアームのある最大の座標以上でなければならない
        ans+=1#以上なら+1
        t=sec[i][0]#ロボットアームのある最大の座標を更新
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, X: "List[int]", L: "List[int]"):

    # 区間に変換する
    segs = [(x-l, x+l) for x, l in zip(X, L)]
    segs.sort(key=lambda x: x[1])  # 尻でソート

    last = -INF
    count = 0
    for i in range(N):
        if last <= segs[i][0]:
            last = segs[i][1]
            count += 1
    print(count)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    L = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        L[i] = int(next(tokens))
    solve(N, X, L)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
I = []
for i in range(N):
  X, L = map(int, input().split())
  I.append((X - L, X + L))

I.sort(key=lambda a: (a[1], a[0]))

x = -10**100
ans = 0
for l, r in I:
  if l >= x:
    ans += 1
    x = r

print(ans)

Submission status: Accepted

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()

machines = []

for i in range(N):
    X,L=two_int()
    minL=max(1,X-L)
    maxL=X+L
    machines.append([X,L, minL, maxL])



machines = sorted(machines,key=lambda x:x[3])

output=[[0,0,0,0]]
for m in machines:
    if output[-1][3] <= m[2]:
        output.append(m)

print(len(output)-1)

Submission status: Accepted

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

lr = []
for i in range(n):
    l = max(xl[i][0] - xl[i][1], 0)
    r = max(xl[i][0] + xl[i][1], 0)
    lr.append([l, r])

lr.sort(key=lambda x: x[1])
keep = [False] * n


cur = 0
for i in range(n):
    if cur <= lr[i][0]:
        keep[i] = True
        cur = lr[i][1]

ans = sum(keep)
print(ans)

Submission status: Accepted

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

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

ans = 0
tmp = -10**9

for s, t in ll:
  if s >= tmp:
    ans += 1
    tmp = t

print(ans)

Submission status: Accepted

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

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

ans = 0
tmp = -10**9

for l in ll:
  if l[0] >= tmp:
    ans += 1
    tmp = l[1]

print(ans)

Submission status: Accepted

Solution code:
import sys
n = int(input())
xl = []
for _ in range(n):
    x, l = map(int, input().split())
    xl.append((x, l))
xl.sort(key=lambda x:x[0])
if n==1:
    print(1)
    sys.exit(0)
i=0
j=1
ans=n
while j<len(xl):
    if xl[i][0]+xl[i][1] <= xl[j][0]-xl[j][1]:
        i = j
        j = i+1
    else:
        ans -= 1
        if xl[i][0]+xl[i][1] < xl[j][0]+xl[j][1]:
            j += 1
        else:
            i = j
            j = i+1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

n = int(input())
arm = []

for n in range(n):
    X,L = [ int(i) for i in input().split() ]
    arm.append((X+L,X-L))

arm.sort()
# print(arm)
lowest = float("-inf")
cnt = 0

for x,l in arm:
    if l>=lowest:
        lowest = x
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys


def main():
    input = sys.stdin.readline
    N = int(input())

    robots = list()

    for i in range(N):
        x, arm = map(int, input().split())
        right = x+arm
        robots.append([x, right])

    robots.sort(key=lambda x: x[1])
    count = 0
    last_r = -10**10
    for x, r in robots:
        l = x - (r - x)
        if l < last_r:
            count += 1
        else:
            last_r = r

    print(N - count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)

def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max,mod=DIV):
    fac,finv,inv = [0]*max, [0]*max, [0]*max
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod -inv[mod%i] * (mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
    class CONV:
        def __init__(self):
            pass
        def ncr(self,n,k):
            if(n<k):
                return 0
            if(n<0 or k<0 ):
                return 0
            return fac[n]*(finv[k]*finv[n-k]%mod)%mod
    return CONV()



def main():
    N = iRaw()
    XLs = [isRaw() for _ in range(N)]
    XLs.sort(key = lambda xl:xl[0]+xl[1])
    curX = -(10**10)
    curL = 0
    ans = 0
    for X,L in XLs:
        if curX+curL <= X-L:
            ans+=1
            curX = X
            curL = L
    return ans


if __name__ == "__main__":
    print(main())

Submission status: Accepted

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(key=lambda x: x[1])
ans=1
nl=l[0][0]
nr=l[0][1]
for i in range(1,n):
    if l[i][0]<nr:
        continue
    else:
        nr=l[i][1]
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,*t=map(int,open(0).read().split())
*z,=sorted(zip(*[iter(t)]*2))
s=set()
for i in range(n-1):
    if i in s:
        continue
    x,l=z[i]
    j=i+1
    while 1:
        y,r=z[j]
        if x+l>y-r:
            if y+r<x+l:
                s|={i}
                break
            else:
                s|={j}
        else:
            break
        j+=1
        if j==n:break
print(n-len(s))

Submission status: Accepted

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

ans = 0
tmp = -10**9

for l in ll:
  if l[0] >= tmp:
    ans += 1
    tmp = l[1]

print(ans)

Submission status: Accepted

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

lr = []
for i in range(n):
    l = max(xl[i][0] - xl[i][1], 0)
    r = max(xl[i][0] + xl[i][1], 0)
    lr.append([r, l])

lr = sorted(lr)
keep = [False] * n
# print(lr)

cur = 0
for i in range(n):
    if cur <= lr[i][1]:
        keep[i] = True
        cur = lr[i][0]
'''
for j in range(n - 1):
    if keep[j]:
        if lr[j][0] == lr[j + 1][0]:
            keep[j + 1] = False
        elif lr[j][0] < lr[j + 1][0]:# < lr[j][1]:
            keep[j + 1] = False
'''
#print(keep)
ans = sum(1 for x in range(n) if keep[x])
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
def main():
    n = int(input())
    inputs = [input().split() for i in range(n)]
    inputs_list = []
    for i in inputs:
        if int(i[0]) - int(i[1]) < 0:
            inputs_list.append([0, int(i[0]) + int(i[1])])
        else:
            inputs_list.append([int(i[0]) - int(i[1]), int(i[0]) + int(i[1])])
    sorted_data = sorted(inputs_list, key=lambda x: (x[1]))

    ans = [sorted_data[0]]
    cur = ans[0][1]
    for i in range(len(sorted_data) - 1):
        if cur <= sorted_data[i + 1][0]:
                ans.append(sorted_data[i + 1])
                cur = sorted_data[i + 1][1]
    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
tmp = -10**9

for s, t in ll:
  if s >= tmp:
    ans += 1
    tmp = t

print(ans)

Submission status: Accepted

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

ans = 0
tmp = -10**9

for s, t in ll:
  if s >= tmp:
    ans += 1
    tmp = t

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

LR = []
for i in range(N):
    x, l = map(int, input().split())
    LR.append([x-l, x+l])

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

cur_r = LR[0][1]
c = 1
for l, r in LR[1:]:
    if cur_r <= l:
        c += 1
        cur_r = r
print(c)

Submission status: Accepted

Solution code:
N = int(input())
r = [list(map(int, input().split())) for _ in range(N)]
a = []
for i in r:
    a.append((i[0]-i[1],i[0]+i[1]))
a.sort(key=lambda x:x[1])
ans = 0
cur = -float('inf')
for i in a:
    if i[0] < cur:
        continue
    ans += 1
    cur = i[1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    robo = []

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

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

    ans = 0
    max = -10**9

    for r in robo:
        if r[0] >= max:
            ans += 1
            max = r[1]
    print(ans)
    return 0

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
r = [list(map(int, input().split())) for _ in range(N)]
a = []
for i in r:
    a.append((i[0]+i[1],i[0]-i[1]))
a.sort()
ans = 0
cur = -float('inf')
for i in a:
    if i[1] < cur:
        continue
    ans += 1
    cur = i[0]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
lists=[]
for i  in range(n):
    x,y=map(int,input().split())
    lists.append((x-y,x+y))
lists=sorted(lists,key=lambda x:(x[1]))
A=1
P=lists[0]
for i in range(1,len(lists)):
    if lists[i][0]>=P[1]:
        A+=1
        P=lists[i]
print(A)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

n = int(input())
lo = []
sh = []

result = 0

MAX = -(10**20)

for i in range(n):
    a,b =map(int, input().split())
    lo.append(a-b)
    sh.append(a+b)
    
c=zip(lo,sh)
d = sorted(c, key=lambda x:x[1])

for i in range(n):
    if MAX <= d[i][0]:
        result += 1
        MAX=d[i][1]

print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
lo=[]
sh=[]

result=0

MAX = -(10**20)

for i  in range(n):
    xx,ll=map(int, input().split())
    lo.append(xx+ll)
    sh.append(xx-ll)
    

c=zip(sh,lo)
d=sorted(c,key=lambda x:x[1])

for i in range(n):
    if MAX <= d[i][0]:
        result+=1
        MAX=d[i][1]

print(result)

Submission status: Accepted

Solution code:
N = int(input())
XL = [tuple(map(int,input().split())) for i in range(N)]
XL.sort(key=lambda x: x[0]+x[1])
right = -float('inf')
ans = 0
for x,l in XL:
    s,t = x-l, x+l
    if s >= right:
        right = t
        ans += 1
print(ans)

Submission status: Accepted

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

ra.sort(key=lambda x:x[1])
t = ra[0][1]
ans = 1
for i in range(1,n):
    if ra[i][0] >= t:
        ans += 1
        t = ra[i][1]

print(ans)

Submission status: Accepted

Solution code:
# 2020/01/19

import sys
input=sys.stdin.readline

n=int(input())

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

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

pre_x=xl[0][1]

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

Submission status: Accepted

Solution code:
from operator import itemgetter

N=int(input())
grid=[]
for i in range(N):
    xi,li=map(int,input().split())
    grid.append((xi-li,xi+li))
grid = sorted(grid, key=itemgetter(1))
res=1
cur=grid[0]

for i, a in enumerate(grid):
    if i==0:
        continue
    if a[0]>=cur[1]:
        res+=1
        cur=a
print(res)

Submission status: Accepted

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

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

leave = [P[0]]
for i in range(1, N):
    # leaveの最大を取得
    leave_max = leave[-1][0] + leave[-1][1]
    p_min = P[i][0] - P[i][1]
    if leave_max <= p_min:
        leave.append(P[i])
    else:
        continue
        
print(len(leave))

Submission status: Accepted

Solution code:
def resolve():
    import sys
    from operator import itemgetter
    readline = sys.stdin.readline
    N = int(readline())
    LR = [None] * N
    for i in range(N):
        p, l = map(int, input().split())
        LR[i] = [p-l, p+l]
    LR.sort(key=itemgetter(1))

    pre_r = -(10**18)
    count = 0
    for l, r in LR:
        if pre_r <= l:
            count += 1
            pre_r = r
    print(count)

resolve()

Submission status: Accepted

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


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def f(A):
    min_num = A[0] + A[-1]


def main():
    N = int(input())
    R = []
    for _ in range(N):
        X, L = map(int, input().split())
        R.append((X - L, X + L))
    
    R.sort(key=lambda l: l[1])

    res = 0
    T = None    
    for r in R:
        if T is None or r[0] >= T:
            T = r[1]
            res += 1

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
current = float('-inf')
for x, l in XL:
    if current <= x - l:
        current = x + l
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
rs = [list(map(int, input().split())) for _ in range(n)]
lr = [[x-l, x+l] for x, l in rs]
lr.sort(key=lambda x: x[1])

cnt = 0
reach = None
for l, r in lr:
    if reach is not None and l < reach:
        continue
    reach = r
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
XL = [tuple(map(int,input().split())) for i in range(N)]
XL.sort(key=lambda x: x[0]+x[1])
right = -float('inf')
ans = 0
for x,l in XL:
    s,t = x-l, x+l-1
    if s > right:
        right = t
        ans += 1
print(ans)

Submission status: Accepted

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

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

ans = 1
right = XL[0][0] + XL[0][1]

for i in range(1, N):
    if right <= XL[i][0] - XL[i][1]:
        right = XL[i][0] + XL[i][1]
        ans += 1

print(ans)