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:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
xl = [LI() for _ in range(n)]
xl.sort()
ans = 0
h = []
for x,l in xl:
    heappush(h,(x+l,x-l))
ans = 0
now = -inf
while h:
    r,l = heappop(h)
    if now <= l:
        now = r
    else:
        ans += 1
print(n-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])
i = 0
if n==1:
    print(1)
    sys.exit(0)
while i<len(xl)-1:
    if xl[i][0]+xl[i][1] <= xl[i+1][0]-xl[i+1][1]:
        i += 1
    else:
        if xl[i][0]+xl[i][1] < xl[i+1][0]+xl[i+1][1]:
            del xl[i+1]
        else:
            del xl[i]
print(len(xl))

Submission status: Accepted

Solution code:
N = int(input())
li = []
for i in range(N):
    hontai, ude = map(int, input().split())
    li.append([hontai, ude, hontai-ude, hontai+ude])
li.sort(key=lambda x:x[3])
#print(li)
count = 1
now = li[0][3]
for i in range(1, N):
    if now <= li[i][2]:
        count += 1
        now = li[i][3]
    #print(now, count)
print(count)

Submission status: Accepted

Solution code:
n = int(input())
xls = [list(map(int, input().split()))for i in range(n)]
xls.sort(key=lambda x:sum(x))

ans = 0
now = -1e11
for i in range(n):
    if now<=xls[i][0]-xls[i][1]:
        ans += 1
        now = xls[i][0]+xls[i][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()
now = -float("inf")
ans = 0
for i in range(N):
    if robots[i][1] >= now:
        now = robots[i][0]
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    li = []
    for _ in range(N):
        a,b = [int(n) for n in input().split()]
        li.append([a-b,a+b])
    # li.sort(key=lambda x:x[0])
    # last = (-10**10,-10**10)
    res = N
    # for a in li:
        
    #     if last[1] > a[1]:
    #         last = a
    #         res-=1
    #     elif last[1] > a[0]:
    #         last = last
    #         res-=1
    #     else:
    #         last = a
    li.sort(key=lambda x:-x[0])
    # print(li)
    last = (10**10,10**10)
    for a in li:
        
        if a[1] > last[0]:
            last = last
            res-=1
        else:
            last=a
    print(res)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def main():
    n = int(input().strip())
    x = [[0, 0] for  _ in range(n)]
    for i in range(n):
        p, q = list(map(int, input().strip().split()))
        x[i][0] = p-q
        x[i][1] = p+q
    x = sorted(x, key=itemgetter(1))
    m = x[0][1]
    ans = 1
    for mi, ma in x[1:]:
        if m <= mi:
            m = ma
            ans += 1

    # x = sorted(x, key=itemgetter(0))
    # M = x[0][0]
    # ans2 = 1
    # print('x: ', x)
    # for mi, ma in x[1:]:

    #     if M >= ma:
    #         print(M, mi, ma)
    #         M = mi
    #         ans2 += 1
    # print(ans, ans2)
    # print(max(ans, ans2))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

xl = []

for i in range(N):
    xl.append(list(map(int,input().split())))

itv = []

for i in range(N):
    right = xl[i][0] + xl[i][1] - 0.01 ##right
    left = xl[i][0] - xl[i][1] + 0.01 ##left   
    itv.append([right,left])
itv.sort()

ass = 0
tt = -1e10
for i in range(N):
    if tt < itv[i][1]:
        ass += 1
        tt = itv[i][0]
print(ass)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from operator import itemgetter

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

XL = sorted(XL, key=itemgetter(1))
i = 1
while i != len(XL):
    if XL[i][0] < XL[i-1][1]:
        XL.pop(i)
    else:
        i += 1

print(len(XL))

Submission status: Accepted

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

import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
LR = []
for i in range(N):
    x, l = MAP()
    LR.append((x-l, x+l-1))

LR.sort(key=itemgetter(1))
cur = -INF
cnt = 0
for l, r in LR:
    if cur < l:
        cur = r
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x = []
    l = []
    for i in range(n):
        tmp = list(map(int, input().split()))
        x.append(tmp[0] - tmp[1])
        l.append(tmp[0] + tmp[1])
    x, l = zip(*sorted(zip(x, l)))
    maxcount = 0
    preve = 0
    idx = 0
    while idx < n:
        tmps = x[idx]
        tmpe = l[idx]
        if preve == 0:
            maxcount += 1
            preve = tmpe
        elif tmps >= preve:
            maxcount += 1
            preve = tmpe
        elif tmpe < preve:
            preve = tmpe
        idx += 1
    print(maxcount)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = sorted([list(map(int, input().split())) for _ in range(n)])
r = a[0][0]+a[0][1]
l = 0
for j in range(1,n):
    i = a[j]
    l = i[0]-i[1]
    if r <= l:
        r = i[0]+i[1]
    else:
        n -= 1
        r = min(r,i[0]+i[1])
print(n)

Submission status: Accepted

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

ls = sorted([[i-j, i+j] for i, j in xl], key=lambda x: x[1])

i, dr = 0, 0
while True:
    if (len(ls)<=1) | (i+1 >= len(ls)):
        break
    a, b = ls[i], ls[i+1]
    if a[1]>b[0]:
        dr += 1
        ls.pop(i+1)
    else:
        i += 1

print(len(ls))

Submission status: Accepted

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

Submission status: Accepted

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

XL.sort(key=lambda x:(x[0],x[1]))
now=XL[0][0]+XL[0][1]
ans=0
for i in range(1,n):
  x,l=XL[i]
  if x-l<now:
    ans+=1
    if x+l<now:
      now=x+l
  else:
    now=x+l
print(n-ans)

Submission status: Accepted

Solution code:
N = int(input())
robot = {}

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

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

pre_arm = -10**10
cnt = 0
for key, val in s_robot:
  l_arm = key - val
  r_arm = key + val
  if pre_arm > l_arm:
    cnt += 1
    if pre_arm > r_arm:
      pre_arm = r_arm
  else:
    pre_arm = r_arm
    
print(N-cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter
N=int(input())
xl=[list(map(int, input().split())) for i in range(N)]
ab=[[xl[i][0]-xl[i][1], xl[i][0]+xl[i][1]] for i in range(N)]
ab=sorted(ab, key=itemgetter(0))
hiku=0
a=ab[0][0]
b=ab[0][1]
for i in range(1, N):
  if b>ab[i][0]:
    hiku+=1
    b=min(b, ab[i][1])
  else:
    b=ab[i][1]
      
print(N-hiku)

Submission status: Accepted

Solution code:
import sys

N=input()

X=[]
for _ in range(N):
    x,l=map(int, sys.stdin.readline().split())
    X.append((x-l,x+l))

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

ans=0
end=float("-inf")
for l,r in X:
    if end<=l and end<r:
        ans+=1
        end=r

print ans

Submission status: Accepted

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

i, j = 0, 1
count = N
while j < N:
  if XL[i][0] + XL[i][1] > XL[j][0] - XL[j][1]:
    if XL[i][0] + XL[i][1] < XL[j][0] + XL[j][1]:
      j += 1
    else:
      i, j = j, j + 1
    count -= 1
  else:
    i, j = j, j + 1
print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)
from functools import lru_cache


def resolve():
    global N, grid

    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    grid = [[int(x) for x in sys.stdin.readline().split()]
            for _ in range(N)]  # int grid

    logger.debug('{}'.format([]))

    grid = [(x + l, x - l) for x, l in grid]

    grid = sorted(grid)

    ans = 0
    t = - 10**10

    for right, left,  in grid:
        if t <= left:
            ans += 1
            t = right

    print(ans)

if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4
2 4
4 3
9 3
100 5"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2
8 20
1 10"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5
10 1
2 1
4 1
6 1
8 1"""
        output = """5"""
        self.assertIO(input, output)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = []
    for _ in range(N):
        X, L = map(int, input().split())
        A.append((X, L))
 
    A.sort()
    cnt = 0
    right = 0
    left = 0
    for i in range(N):
        if i == 0:
            left = A[i][0] - A[i][1]
            right = A[i][0] + A[i][1]
        else:
            tmp_left = A[i][0] - A[i][1]
            tmp_right = A[i][0] + A[i][1]
            if tmp_right < right:
                left = tmp_left
                right = tmp_right
                cnt += 1
            elif tmp_left < right:
                cnt += 1
            else:
                left = A[i][0] - A[i][1]
                right = A[i][0] + A[i][1]
 
    print(N - cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
X = []
x_wid = []
counter = 0
Min = 0
Max = 0

for i in range(n):
  X.append(list(map(int,input().split())))
  
X = sorted(X)

for i in range(n):
  if i == 0:
    Min = X[i][0] - X[i][1]
    Max = X[i][0] + X[i][1]
  else:
    if (X[i][0] - X[i][1]) < Max:
      counter += 1
      Max = min(Max, X[i][0] + X[i][1])
    else:
      Max = X[i][0] + X[i][1]
#  print("Max:", Max)

print(n - counter)

Submission status: Accepted

Solution code:
N = int(input())
kukan = [[] for _ in range(N)]
for i in range(N):
    X, Len = map(int, input().split())
    kukan[i] = [X - Len, X + Len]

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

p = -10 ** 9
ans = 0
for k in kukan:
    if p <= k[0]:
        # ok
        ans += 1
        p = k[1]
        pass
    else:
        # ng
        pass
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
robots = [[int(x) for x in input().split()] for _ in range(N)]
robots = [(x - l,  x + l) for x, l in robots]
robots.sort(key=lambda x: x[1])
cur = float('-inf')
count = 0
for left, right in robots:
    if cur <= left:
        cur = right
        count += 1
print(count)

Submission status: Accepted

Solution code:
N = int(input())
ROB = [list(map(int, input().split())) for _ in range(N)]
ROB = sorted(ROB, key=lambda x:x[0])
right = ROB[0][0] + ROB[0][1]
ans = 1
for i in range(N-1):
  if(right <= ROB[i+1][0] - ROB[i+1][1]):
    ans += 1
    right = ROB[i+1][0] + ROB[i+1][1]
  else:
    right = min(right, ROB[i+1][0] + ROB[i+1][1])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n=int(input())

Z=np.zeros((n,4))
for i in range(n):
    Z[i][0],Z[i][1]=map(int, input().split())
    Z[i][2]=Z[i][0]+Z[i][1]
    Z[i][3]=Z[i][0]-Z[i][1]
Z2=Z[np.argsort(Z[:,2])]

ans=1
border=Z2[0][2]
for i in range(1,n):
    if Z2[i][3]>=border:
        ans+=1
        border=Z2[i][2]

print(ans)

Submission status: Accepted

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

r = - 10 ** 9 - 1
cnt = 0
for i in range(n):
    if r <= robots[i][1]:
        cnt += 1
        r = robots[i][0]
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

list_ = list()

for i in range(N):
  X,L = map(int,input().split())
  max_ = min(10**9,X+L-0.1)
  min_ = max(0,X-L+0.1)
  list_.append((X,min_,max_))
list_.sort()

d = 0
nowmax = -1
nowmin = -1

for x, min_, max_ in list_:
  if nowmax > min_:
    d += 1
    nowmax = min(nowmax,max_)
  else:
    nowmin = min_
    nowmax = max_
  
print(N-d)

Submission status: Accepted

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

target = 0
sum = N
for i in range(N-1):
  if (XL[target][0] + XL[target][1]) > (XL[i+1][0] - XL[i+1][1]):
    if (XL[target][0] + XL[target][1]) >= (XL[i+1][0] + XL[i+1][1]):
      target = i + 1
    sum = sum-1
  else:
    target = i + 1
    
print(sum)

Submission status: Accepted

Solution code:
N = int(input())
X = []
p = 0
for i in range(N):
    X.append(tuple([int(n) for n in input().split()]))
a = sorted(X)
while p<len(a)-1:
    if a[p][0]+a[p][1] > a[p+1][0]+a[p+1][1]:
        a.pop(p)
    elif  a[p][0]+a[p][1] > a[p+1][0]-a[p+1][1]:
        a.pop(p+1)
    else:
        p += 1
print(len(a))

Submission status: Accepted

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

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

temp_max = num_list2[0][1]
cnt = 1

for l, h in num_list2:
    if l >= temp_max:
        cnt += 1
        temp_max = h

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
dic = {}

for i in range(n):
    inp = list(map(int, input().split()))
    dic[inp[0]] = inp[1]

dic = sorted(dic.items())
ans = 1
pre = dic[0][0]+dic[0][1]
fidx = 0
for i in range(1, n):
    n_s = dic[i][0]+dic[i][1]
    if pre > n_s:
        pre = n_s
        fidx = i
idx = fidx

for i in range(fidx+1, n):
    if dic[idx][0]+dic[idx][1] > dic[i][0]-dic[i][1]:
        if dic[idx][0]+dic[idx][1] > dic[i][0]+dic[i][1]:
            idx = i
    else:
        ans += 1
        idx = i


print(ans)

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])
maxi = -10**9-7
ans = n
for i in range(n):
  if maxi <= xl[i][0]-xl[i][1]:
    maxi = xl[i][0]+xl[i][1]
  else:
    ans -= 1
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XL = []
for n in range(N):
    XL.append([int(x) for x in input().split()])
XL = sorted(XL, key=lambda x:x[0]+x[1])
m = -float("inf")
ans = 0
for n in range(N):
    if XL[n][0]-XL[n][1] >= m:
        ans += 1
        m = XL[n][0]+XL[n][1]
print(ans)

Submission status: Accepted

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

N = int(readline())
XL = [list(map(int, readline().split())) for i in range(N)]
XL.sort()
X, L = zip(*XL)

rm = -10000000
dropc = 0
for i in range(N):
    if X[i] - L[i] < rm:
        if rm > X[i] + L[i]:
            rm = X[i] + L[i]
        dropc += 1
    else:
        rm = X[i] + L[i]

print(N - dropc)

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
cnt = 0
L = []
for i in range(N):
    x, l = map(int, input().split())
    L.append([x, l])

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

for i in range(N):
    x, l = L[i]
    if i == 0:
        px, pl = x, l
    else:
        if px + pl >  x - l:
            cnt += 1
            if px + pl > x + l:
                px, pl = x, l
        else:
            px, pl = x, l
print(N - cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jan 18 21:45:18 2020

@author: masat
"""

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

end_start_list.sort()

#print(start_end_list)

e_s_0 = end_start_list[0]
latest_end = e_s_0[0]
counter = 1
for i in end_start_list:
    if i[1] >= latest_end:
        counter += 1
        latest_end = i[0]
    else:
        pass

print(counter)

Submission status: Accepted

Solution code:
N = int(input())

a_list = []
for i in range(N):
  x, l = map(int, input().split())
  a_list.append([x - l, x + l])
  
b_list = sorted(a_list, key=lambda x:x[0])
cnt = N
start, end = map(int, b_list[0])
for i in range(1,N):
  start_, end_ = map(int, b_list[i])
  if start_ < end:
    if end_ <= end:
      cnt -= 1
      start = start_
      end = end_
      continue
    else:
      cnt -= 1
      continue
  else:
    start = start_
    end = end_
      
      
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
r=[]
cnt=1
for i in range(n):
  x,l=map(int,input().split())
  r.append([x+l,x-l])
r.sort()
#print(r)
migi=r[0][0]
for i in range(1,n):
  if r[i][1]>=migi:
    #print("i,migi",i,migi)
    cnt+=1
    migi=r[i][0]
print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter
n =int(input())
x =[]
l =[]

for i in range(n):
    x1,l1 = [int(i) for i in input().split()]
    x.append(x1)
    l.append(l1)

min = []
max = []
for i in range(n):
    min1, max1 = (x[i]-l[i],x[i]+l[i])
    min.append(min1)
    max.append(max1)

minmax= sorted([(min[i],max[i])for i in range(n)], key=itemgetter(1))
ans = 0
T = -1000000000
for i in range(n):
    if T<=minmax[i][0]:
        ans +=1
        T = minmax[i][1]
print(ans)

Submission status: Accepted

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

robos.sort(key= lambda x:x[1])
# print(robos)
edge = -10000000000000
out = 0
for i in range(n):
    if robos[i][0] >= edge:
        out += 1
        edge = robos[i][1]
    else:
        continue

print(out)

Submission status: Accepted

Solution code:
import math

N = int(input())

li = []

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

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

ans = 0
t = 0 - 10**9 + 99
for i in range(N):
    if t <= li[i][0]:
        ans += 1
        t = li[i][1]

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ans = 0
x = [0] * n
for i in range(n):
    x[i] = tuple([int(x) for x in input().strip().split()])

x.sort()
pre = -float('inf')
for xx in x:
    if pre > xx[0] - xx[1]:
        if pre < xx[0] + xx[1]:
            continue
        else:
            pre = xx[0] + xx[1]
            continue
    
    ans += 1
    pre = xx[0] + xx[1]
print(ans)

Submission status: Accepted

Solution code:
# B - Robot Arms
N = int(input())
a =[list(map(int, input().split())) for i in range(N)]
#print(a)
count  = 0

a.sort()
#print(a)
for i in range(N-1):
    right = a[i][0] + a[i][1]
    left = a[i+1][0] - a[i+1][1]
    if right <= left:
        pass
    else:
        count += 1
        if a[i][0] + a[i][1] >= a[i+1][0] + a[i+1][1] and a[i][0] + a[i][1] > a[i+1][0]:
            pass
        else:
            a[i+1][0] = a[i][0]
            a[i+1][1] = a[i][1]
print(N -count)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n = int(input())

itv = []
for i in range(n):
  tx,tl = map(int,input().split())  
  itv.append([tx+tl,tx-tl] )

itv = sorted(itv)

ans = 0
right = float('-inf')

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

Submission status: Accepted

Solution code:
n = int(input())

arm_list = []
for i in range(n):
    array = list(map(int, input().split()))
    a = array[0] - array[1]
    b = array[0] + array[1] - 1
    arm_list.append([a, b])

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

if n == 1:
    print(1)
    exit()
count = 1
a = arm_list[0][1]
b = arm_list[1][0]
for i in range(1, n-1):
    if a < b:
        count += 1
        a = arm_list[i][1]
        b = arm_list[i+1][0]
    else:
        b = arm_list[i+1][0]

if a < b:
    count += 1



print(count)

Submission status: Accepted

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

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

l = -2000000000
ans=0
for i in range(n):
    if l<=lr[i][0]:
        l=lr[i][1]
        ans+=1

print(ans)

Submission status: Accepted

Solution code:

N=int(input())
P=[[int(i) for i in input().split()] for  _ in range(N)]
arm=[[p[0]-p[1], p[0]+p[1]] for p in P]
s_arm=sorted(arm, key=lambda x: x[1])

#tは最後に選んだ仕事の終了時間
ans = 0
t = -10**9
for i in range(N):
    if (t <= s_arm[i][0]):
        ans+=1
        t = s_arm[i][1]
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

log=[]
for _ in range(N):
    X,L=map(int,input().split())
    log.append([X,X-L,X+L])
    
log.sort(key=lambda x:x[2])

ans=N
pre=log[0][2]
for i in range(N-1):
    if log[i+1][1]-pre<0:
        #print(pre,log[i+1][2])
        if log[i+1][2]<pre:#前の方が幅取る場合
            pre=log[i+1][2]
        ans-=1
    else:#ぶつからない場合
        pre=log[i+1][2]
    
print(ans)

Submission status: Accepted

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

from operator import itemgetter
li=sorted(li, key=itemgetter(3))

ans=0
now=0

for i in range(n-1):
  if li[now][3]>=li[i+1][3]: #今調査してるやつが、次のやつを覆ってしまってる場合
    ans+=1
    now=i+1
  elif li[now][3]>li[i+1][2]:
    ans+=1
  else:
    now=i+1

print(n-ans)

Submission status: Accepted

Solution code:
n = int(input());

sf = [ [0]*2 for i in range(n) ];
for i in range(n) :
	xl = input().split(' ');
	sf[i][0] = int(xl[0]) - int(xl[1]);
	sf[i][1] = int(xl[0]) + int(xl[1]);
	

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

ans = 1;
end = sf[0][1];
for i in range(1,n) :
	if end <=  sf[i][0] :
		end = sf[i][1];
		ans += 1;

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:
import sys
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7
n=int(input())
xl=[list(map(int,input().split())) for i in range(n)]
from collections import deque
# for i in range(n):
#     right.append(xl[i][0]+xl[i][1])
#     left.append(xl[i][0]-xl[i][1])
ans=0
xl.sort()
# right.sort()
# left.sort()
d=deque(xl)
while d:
    tmp=d.popleft()
    while d:
        if tmp[0]+tmp[1]>d[0][0]-d[0][1]:
            ans+=1
            if tmp[0]+tmp[1]>d[0][0]+d[0][1]:
                # d.popleft()
                break
            elif tmp[0]-tmp[1]>d[0][0]-d[0][1]:
                d.popleft()
            else:
                d.popleft()
        else:
            break
if n==1:
    print(1)
    quit()

print(n-ans)

Submission status: Accepted

Solution code:
f = lambda x, y: (x + y, x - y)
n = int(input())
a = sorted(f(*map(int, input().split())) for _ in range(n))
r = 0
p = -10**9
for x, y in a:
  if y >= p:
    r += 1
    p = x
print(r)

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[0])
ans = 1
t = ra[0][1]
for i in range(n):
    if ra[i][0] >= t:
        ans += 1
        t = ra[i][1]
    else:
        t = min(t,ra[i][1])

print(ans)

Submission status: Accepted

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

for i in range(N):
    A, B = map(int, input().split())
    left = max(A - B, 0)
    right = min(A + B, 1000000000)
    zahyo.append([left,right])
zahyo.sort()

count = 0
prev = [-2,-1]
for now in zahyo:
    if prev[1] >= now[1]:
        prev = now
    elif prev[1] <= now[0]:
        prev = now
        count += 1
print(count)

Submission status: Accepted

Solution code:
N = int(input())
xl = []
for i in range(N):
  x,l =[int(x) for x in input().split()]
  a = max(x-l,0)
  xl.append([a,x+l])
xl = sorted(xl,key = lambda x:x[1])
#print(xl)
minx=xl[0][0]
maxx=xl[0][1]
cnt=0
for i in range(1,N):
  if maxx<=xl[i][0]:
    maxx=xl[i][1]
  else:
    cnt+=1
print(N-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])

hold = [XL[0]]

ans = 1
for i in range(1, N):
    if hold[-1][0] + hold[-1][1] > XL[i][0] - XL[i][1]:
        if hold[-1][0] + hold[-1][1] < XL[i][0] + XL[i][1]:
            continue
        else:
            hold.append(XL[i])
    else:
        ans += 1
        hold.append(XL[i])

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
robo = []
for _ in range(N):
    X, L = map(int, input().split())
    left = X - L
    right = X + L
    robo.append((left, right))

robo.sort(key=lambda x: x[1])
right = -10 ** 18
ans = N

for l, r in robo:
    if l < right:
        ans -= 1
        continue
    right = r

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

robots = []

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

robots.sort()

count = 0
now = -float('INF')

for left, right in robots:
    if left >= now:
        count += 1
        now = right

    else:
        if right < now:
            now = right
        else:
            continue

print(count)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
p=[[0,0] for i in range(n)]
p[0]=[0,1]
x,l=[],[]
y=[]
for i in range(n):
    tmpx,tmpl=list(map(int,input().split()))
    y.append([tmpx+tmpl,tmpx])
y.sort()
x=[y[i][1] for i in range(n)]
l=[y[i][0]-y[i][1] for i in range(n)]

a=[x[i]+l[i] for i in range(n)]
for i in range(1,n):
    s=bisect.bisect_right(a,x[i]-l[i])
    if s>0:
        p[i]=[max(p[i-1]),max(p[s-1])+1]
    else:
        p[i]=[max(p[i-1]),1]

print(max(p[n-1]))

Submission status: Accepted

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

for i in range(a):
    one = input().split()
    one = [int(i) for i in one]
    two = [one[0] - one[1], one[0] + one[1]]
    fanwei.append(two)

fanwei = sorted(fanwei, key=lambda student: student[0] + 100000000000000000000 * student[1])

now = -100000000000000000000
ans = 0
for i in fanwei[:]:
    down = i[0]
    if down >= now:
        ans += 1
        now = i[1]


print(ans)

Submission status: Accepted

Solution code:
N = int(input())

Sn, Tn = [0] * N, [0] * N
XLn = []
for i in range(N):
    x, l = map(int, input().split())
    Sn[i], Tn[i] = x-l, x+l

for i in range(N):
    XLn.append((Tn[i], Sn[i]))

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

res, t = 0, -float("inf")
for i in range(N):
    if t <= XLn[i][1]:
        res += 1
        t = XLn[i][0]

print(res)

Submission status: Accepted

Solution code:
import math
def A():
    H = int(input())
    W = int(input())
    N = int(input())
    print(int(min(math.ceil(N/H), math.ceil(N/W))))

def B():
    N = int(input())
    robots = []
    for i in range(N):
        temp = [int(n) for n in input().split()]
        robots.append([temp[0]-temp[1], temp[0]+temp[1]])
    robots.sort(key = lambda x:x[1])
    #print(robots)
    prev_end = robots[0][1]
    count = 1
    for i in range(1, len(robots)):
        cur_start = robots[i][0]
        cur_end = robots[i][1]

        if cur_start >= prev_end:
            #print(i)
            count += 1
            prev_end = cur_end

    print(count)

def C():
    temp = [int(n) for n in input().split()]
    N = temp[0]
    K = temp[1]
    S = temp[2]
    if S == 10**9:
        ans = [str(S)]*K + [str(S-1)]*(N-K)
    else:
        ans = [str(S)]*K + [str(S+1)]*(N-K)
    print(' '.join(ans))

B()

Submission status: Accepted

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