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())
x = []
l = []
for i in range(N):
    x1,l1=[int(i) for i in input().split()]
    x.append(x1)
    l.append(l1)

Range = []

for i in range(N):
  max_i = x[i] + l[i]
  min_i = x[i] - l[i]
  Range.append((min_i,max_i))

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

a = 1
for i in range(N-1):
  if Range[a][0] >= Range[a-1][1]:
    a += 1
  else:
    Range.pop(a)

print(a)

Submission status: Accepted

Solution code:
s=int(input())
t=[]
for i in range(s):
    u,l=map(int,input().split())
    t.append((u-l,u+l-1))
t.sort(key=lambda x: x[1])
d=-10**10
ans=0
for i in range(s):
  if d<t[i][0]:
    ans+=1
    d=t[i][1]
print(ans)

Submission status: Accepted

Solution code:
def solve():
  n = int(input())
  query  =[]
  for i in range(n):
    x,l = (int(i) for i in input().split())
    query.append((x+l,max(0,x-l)))
  query.sort()
  nowr = 0
  ans = 0
  for i in range(n):
    r,l = query[i]
    #print(nowr)
    if nowr <= l:
      nowr = r
      ans += 1
  print(ans)
solve()

Submission status: Accepted

Solution code:
N = int(input())
X = []
X_L = []
X_L_dict = {}
for i in range(N):
    x, l = map(int, input().split())
    X_L.append([x-l, x+l])
    X.append(x-l)
X_L.sort(key=lambda x:x[1])
X.sort()

last = None

count = 0
# print(X_L)
for x_l in X_L:
    # print(x_l, last)
    if last is None or last <= x_l[0]:
        count += 1
        last = x_l[1]
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XL):
    s = []
    for x, l in XL:
        lp, rp = x-l, x+l
        s.append((lp, rp))

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

    ans = 0
    t = -INF
    for l, r in s:
        if t <= l:
            ans += 1
            t = r

    return ans

def main():
    N = read_int()
    XL = [read_int_n() for _ in range(N)]
    print(slv(N, XL))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = []
x = -float("inf")
res = 0
for _ in range(N):
  x, l = map(int, input().split())
  a.append((x - l, x + l))
a.sort(key = lambda x: x[1])
x = -float("inf")
#print(a)
for i in range(N):
  if x <= a[i][0]:
    x = a[i][1]
    res += 1
print(res)

Submission status: Accepted

Solution code:
N = int(input())
D = []
for i in range(N):
    x, l = map(int, input().split())
    D.append([x-l, x+l])
from operator import itemgetter
D = sorted(D, key = itemgetter(1))
u = -10**10 #最小値:x = 0, l = 10**10の時
cnt = 0
for a, b in D:
    if u <= a:
       cnt += 1
       u = b #つぎのロボットの範囲の下限に置きかえる
print(cnt)

Submission status: Accepted

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

Range = []

for i in range(N):
  max_i = x[i] + l[i]
  min_i = x[i] - l[i]
  Range.append((min_i,max_i,x[i], l[i]))

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

#print(Range)
a = 1

for i in range(N-1):
  #print(Range[a][0], end = ","),print(Range[a-1][1])
  if Range[a][0] >= Range[a-1][1]:
    a += 1
  else:
    #if Range[a][3] >= Range[a-1][3]:
      Range.pop(a)
    #else:
      #Range.pop(a-1)

#print(Range)
print(a)

Submission status: Accepted

Solution code:
n = int(input())
xl = [list(map(int, input().split())) for i in range(n)]
xl = sorted([[x-l,x+l] for x,l in xl], key = lambda x: x[1])
now = - 10 ** 10
ans = 0
for s,e in xl:
  if s >= now:
    ans += 1
    now = e
print(ans)

Submission status: Accepted

Solution code:
import sys
inputs = sys.stdin.readlines()

n = int(inputs[0])
Y = []
for s in inputs[1:]:
    x, l = map(int, s.split())
    Y.append((x-l, x+l))
Y.sort(key=lambda x: x[1])

cnt = 1
_, r0 = Y[0]
for i in range(1, n):
    l, r = Y[i]
    if r0 <= l:
        cnt += 1
        r0 = r
    
print(cnt)

Submission status: Accepted

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

#print(robots)
# 最大値と最小値を計算する
robots = [(x+l,x-l) for x,l in robots]
#print(robots)
# ソートする
robots.sort()
#print(robots)

cnt = 0
last = -float('inf')
for r,l in robots:
    #print(last, l, r)
    # 1個前の最大値を、今回の最小値が上回っていたらOK
    if last <= l:
        cnt += 1
        # 次の最大値を更新する
        last = r

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

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

RL.sort()
right = -10**9

ans = 0
for r, l in RL:
  if l >= right:
    right = r
    ans += 1
    
print(ans)

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]  ##right
    left = xl[i][0] - xl[i][1]  ##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())
pin = [[0, 0] for i in range(N)]
front = [0 for i in range(N)]
for i in range(N):
    X, L = map(int, input().split())
    pin[i][1] = X - L
    pin[i][0] = X + L
    front[i] = X - L
pin.sort()
ans = 1
i = 1
tmp = pin[0][0]
while i < N:
    if pin[i][1] < tmp:
        i += 1
    else:
        ans += 1
        tmp = pin[i][0]
        i += 1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
s=[list(map(int,input().split())) for i in range(N)]
A=N
c=0
s.sort(key=lambda x: x[0])

Check=[[s[i][0]-s[i][1],s[i][0]+s[i][1]] for i in range(N)]
tmp=Check[0][1]
for j in range(1,N):
    if tmp > Check[j][0]:
        c=c+1
        tmp=min(tmp, Check[j][1])
    else:
        tmp=Check[j][1]
    
print(A-c)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush,heappop
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    X,L=[0]*N,[0]*N
    l=[]
    for i in range(N):
        X[i],L[i]=map(int,input().split())
        l.append((X[i]+L[i]-1,X[i]-L[i]))
    l.sort()
    ans=0
    tmp=-INF
    for right,left in l:
        if tmp<left:
            ans+=1
            tmp=right
    print(ans)        
        

if __name__ == '__main__':
    main()

Submission status: Accepted

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

first_robot=ls.pop(0)
prev_right=first_robot[0]+first_robot[1]

for robot in ls:
    left=robot[0]-robot[1]
    right=robot[0]+robot[1]
    if left<prev_right:
        n-=1
        if right<prev_right:
            prev_right=right
    else:
        prev_right=right
print(n)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
X = []
for i in range(n):
  x, l = map(int, input().split())
  X.append([x-l, x+l])
X.sort()
temp = X[0][1]
count = n
for i in range(1,n):
  if temp>X[i][0]:
    count -= 1
    temp = min(temp, X[i][1])
  else:
    temp = X[i][1]
print(count)

Submission status: Accepted

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

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

ps.sort()

x = ps[0][0]
d = 0

for i in range(1, n):
  p = ps[i]
  
  if p[1] < x:
    d += 1
  else:
    x = p[0]

print(n - d)

Submission status: Accepted

Solution code:
n = int(input())
rob = []
for i in range(n):
    x,l = map(int,input().split())
    rob.append([x-l,x+l])
rob.sort()
ans  = n
right = rob[0][1]
for i,[l,r] in enumerate(rob):
    if i == 0:
        continue
    if l < right:
        ans -= 1
        right = min(right,r)
    else:
        right = r
print(ans)

Submission status: Accepted

Solution code:
def acinput():
    return list(map(int, input().split(" ")))

N=int(input())
bars=[]
for i in range(N):
    tmp = acinput()
    tmp.extend([tmp[0]-tmp[1],tmp[0]+tmp[1]])
    bars.append(tmp)

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

#print(bars)

count=0
R=-10000000000
for i in range(0,N):

    if R<=bars[i][2]:
        R=bars[i][3]
        count+=1


print(count)

Submission status: Accepted

Solution code:
N=int(input())
P=[(0,0) for i in range(N)]
for i in range(N):
    x,l=map(int,input().split())
    P[i]=(x-l,x+l)
P.sort(key=lambda y:y[1])
#print(P)
ans=1
t=P[0][1]
for i in range(1,N):
    if t<=P[i][0]:
        ans+=1
        t=P[i][1]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
X = []
for i in range(n):
  x, l = map(int, input().split())
  X.append([x-l, x+l])
X.sort()
temp = X[0][1]
count = n
for i in range(1,n):
  if temp>X[i][0]:
    count -= 1
    temp = min(temp, X[i][1])
  else:
    temp = X[i][1]
print(count)

Submission status: Accepted

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



for i in range(n):
    left.append((l[i][0]+l[i][1],l[i][0]-l[i][1]))
left.sort()   
count = 1
right = 10**10
right = left[0][0]
c = 0

while True:
    
    for i in range(c,n+1):
        if i == n:
            print(count)
            exit()
        if left[i][1] >= right:
            count += 1
            right = left[i][0]
            c = i
            
            
            
    if c == n-1:
        print(count)
        exit()

Submission status: Accepted

Solution code:
n=int(input())
x,l=[0]*n,[0]*n
xlr=[[0]*2 for i in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  x[i],l[i]=a,b
  xlr[i]=[a-b,a+b]
xlr.sort()
cnt=0
chk=xlr[n-1][0]
for i in range(2,n+1):
  if chk<xlr[n-i][1]:
    cnt+=1
  else:
    chk=xlr[n-i][0]
print(n-cnt)

Submission status: Accepted

Solution code:
n=int(input())

robot=[]

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



RR=robot[0][0]-1
cnt=0

for item in robot:
    if RR<=item[0]:
        cnt+=1
        RR=item[1]
    elif RR>=item[1]:
        RR=item[1]

print(cnt)

Submission status: Accepted

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

N = int(input())

table = []

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

table.sort(key=lambda x:x[0])
cur = table[0]
for i in range(1,N):
    if table[i][0] < cur[1]:
        N -= 1
        if cur[1] >= table[i][1]:
            cur = table[i]
    else:
        cur = table[i]

print(N)

Submission status: Accepted

Solution code:
n = int(input())
x_org = []
for i in range(n):
    x_org.append(input().split())

x = sorted(x_org, key=lambda z: int(z[0]))
removed = 0
for i in range(1, n):
    before = int(x[i][0]) - int(x[i][1])
    after = int(x[i-1][0]) + int(x[i-1][1]) 
    if before < after:
        removed += 1
        if (int(x[i][0]) + int(x[i][1])) > (int(x[i-1][0]) + int(x[i-1][1])):
            x[i] = x[i-1]

print(n - removed)

Submission status: Accepted

Solution code:
N = int(input())
XLlist = [tuple(map(int, input().split())) for _ in range(N)]
XLlist.sort(key=lambda x: x[0])
ans = 1
x, l = XLlist[0]
rl = x + (l - 1)
for x, l in XLlist:
    ll = x - l
    if ll <= rl:
        rl = min(rl, x + l - 1)
    else:
        ans += 1
        rl = x + l - 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def main():
    n = ri()
    robots = []
    for i in range(n):
        x, l = rli()
        robots.append([x+l, x-l])
    robots.sort()
    r = -1*pow(10, 10)
    ans = 0
    for ro in robots:
        if ro[1] < r:
            continue
        ans += 1
        r = ro[0]
    print(ans)


if __name__ == '__main__':
    main()

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+0.5, x+l-0.5))

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:
N = int(input())
X = []
for i in range(N):
    x,l = map(int, input().split())
    X.append([x-l, x+l])
X.sort()
#print(X)

count = N
temp = X[0][1]
for i in range(N-1):
    if X[i+1][0] < temp:
        count -= 1
        temp = min(temp, X[i+1][1])
    else:
        temp = X[i+1][1]
    #print(temp)

print(count)

Submission status: Accepted

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
nl=[]
for i in range(n):
  nl.append([l[i][0]+l[i][1],l[i][0]-l[i][1]])
nl.sort()
if n==1:
  print(1)
else:
  ans=1
  k=nl[0][0]
  for i in range(1,n):
    if k<=nl[i][1]:
      ans+=1
      k=nl[i][0]
  print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

N = int(input())
robot_number = 0
arm_ranges = []
for n in range(N):
    [x, l] = [int(i) for i in input().split()]
    minimum = x - l
    maximum = x + l
    arm_ranges.append((maximum, minimum))

# 腕の届く端が小さいもの順にソート
arm_ranges_sorted = sorted(arm_ranges)

(ma, mi) = arm_ranges_sorted[0]
now_max = ma
robot_number += 1
for arm_range in arm_ranges_sorted[1:]:
    (ma, mi) = arm_range
    if mi >= now_max:
        robot_number += 1
        now_max = ma

print(robot_number)

Submission status: Accepted

Solution code:
def main():
    N = int(input())

    X_L = tuple(tuple(int(j) for j in input().split()) for i in range(N))
    ranges = tuple((x - l, x + l) for x, l in X_L)
    sorted_X_L = sorted(X_L, key=lambda x: x[0])

    # sorted_ranges = sorted(ranges, key=lambda x: x[0])

    x_max = - 1e9
    x_min = 2e9

    allowed = []

    for i in range(N):
        i_min = sorted_X_L[i][0] - sorted_X_L[i][1]  # min
        i_max = sorted_X_L[i][0] + sorted_X_L[i][1]  # max

        if i_min >= x_max:
            allowed.append(sorted_X_L[i])
            x_max = max(x_max, i_max)
            x_min = min(x_min, i_min)
        elif i_max <= x_max:
            allowed[-1] = sorted_X_L[i]
            x_max = i_max

    print(len(allowed))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

N=int(input())
XL=[]
for i in range(N):
    XL.append(list(map(int,list(input().split()))))
XL=np.asarray(XL)
XLs=XL[np.argsort(XL[:,0])]
right=XLs[0][0]+XLs[0][1]
ans=1
for i in range(N-1):
    if right-(XLs[i+1][0]+XLs[i+1][1])>0:
        right=XLs[i+1][0]+XLs[i+1][1]
    elif XLs[i+1][0]-XLs[i+1][1]-right>=0:
        ans+=1
        right=XLs[i+1][0]+XLs[i+1][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
l = [None]*N
for i in range(N):
    l[i] = list(map(int, input().split()))
l.sort()

prek = l[0][0]
prea = l[0][1]
cnt = N

for i in range(1,N):
    k,a = l[i]
    pre_reach = prek+prea
    now_reach_m = k-a
    now_reach_p = k+a
    #前の範囲が今回Xのマイナス側の範囲と被ると問題
    if pre_reach>now_reach_m:
        #前の範囲が今回の範囲よりplusに長ければ前のアームを消す
        if pre_reach>now_reach_p:
            cnt -= 1
            prek = k
            prea = a
        else:
            cnt -= 1
    else:
        prek = k
        prea = a
print(cnt)

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from bisect import bisect_left

def resolve():
    N = int(input())
    #S = [list(iim()) for i in range(N)]
    MX = 10**9
    S = []
    for i in range(N):
        x, l = iim()
        i = x - l
        if i < 0:
            i = 0
        j = x + l
        if j > MX:
            j = MX

        a = [i, j]
        S.append(a)
    S.sort()

    ans = 0
    last = MX+1
    n = 1
    for x, y in S:
        if y < last:
            last = y
        elif last <= x:
            n += 1
            last = y

    print(n)






if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N = int(input())
robots = {}
for _ in range(N):
    pos,armlen = map(int,input().split())
    robots[pos] = armlen

robots = sorted(robots.items(),key=lambda x:x[0])
range_min = robots[0][0] + robots[0][1]
ans = 1
for robot in robots[1:]:
    pos,armlen = robot
    if range_min <= (pos-armlen):
        ans += 1
        range_min = pos+armlen
    else:
        if range_min > (pos+armlen):
            range_min = pos+armlen

print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if x[mid] >= n:
        rr = mid
    else:
        ll = mid+1


n = onem()
a = []
b = []
for i in range(n):
    x,c = m()
    a.append([x-c-1,x+c-1])
    b.append([x-c-1,x+c-1])

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

for i in range(n):
    if not aa:
        aa.append(a[0])
        bbb = a[0][1]
    else:
        if bbb <= a[i][0]:
            aa.append(a[i])
            bbb = a[i][1]
        else:
            continue

print(len(aa))

Submission status: Accepted

Solution code:
n = int(input())
from collections import defaultdict
d = defaultdict(list)
X = []
xl = [tuple(map(int,input().split())) for i in range(n)]
for x,l in xl:
    d[x].append(x-l)
    d[x].append(x+l)
    X.append(x)

X.sort()


n_remove = 0


for i in range(1,n):
    x_1 = X[i-1]
    x_2 = X[i]
    min_1 , max_1 = d[x_1]
    min_2 , max_2 = d[x_2]

    if max_1 > min_2:
        n_remove += 1
        if max_2 >= max_1:
            d[x_2] = d[x_1]
            X[i] = X[i-1]


ans = n - n_remove
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
x = []
l = []
c = []
d = {}
 
for i in range(n):
    xx,ll = map(int, input().split())
    x.append(xx)
    l.append(ll)
    d[xx] = ll
 
 
dct = sorted(d.items())
 
f = 0
ans = 0
f = dct[0][0] + dct[0][1]
for i in range(1,len(dct)):
    if f > dct[i][0] - dct[i][1]:
        ans += 1
        f = min(f,dct[i][0]+dct[i][1])
    else:
        f = dct[i][0]+dct[i][1]
 
 
print(n-ans)

Submission status: Accepted

Solution code:
n = int(input())
x_l = {}
for i in range(n):
    x,l = map(int, input().split())
    x_l[x] = l
if n ==1 :
    print(1)
    exit()
del_num = 0
sort_x = sorted(x_l.keys())
min_max = [max(0, sort_x[0] - x_l[sort_x[0]]), min(10**9, sort_x[0] + x_l[sort_x[0]])]
for i in sort_x[1:]:
    if min_max[1] >  (i - x_l[i]):
        del_num+=1
        min_max[1] = min(min_max[1], x_l[i] + i) 
    else:
        min_max[1] = (i + x_l[i])
print(n-del_num)

Submission status: Accepted

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

l = r[0]
ri = 1
ans = N
while ri < N:
    x1, l1 = l
    x2, l2 = r[ri]
    if (x1+l1) > (x2-l2):
        if (x1+l1) > (x2+l2):
            l = r[ri]
            ri += 1
        else:
            ri += 1
        ans -= 1
    else:
        l = r[ri]
        ri += 1
print(ans)

Submission status: Accepted

Solution code:

n = int(input())
rl = []
for i in range(n):
    x,l = map(int,input().split())
    rl.append([x+l,x-l])
rl.sort()
ans = 1
migihasi = rl[0][0]
hasikouho = []
for i in range(1,n):
    right = rl[i][0]
    left = rl[i][1]
    if left < migihasi:continue
    migihasi = right
    ans += 1

    
        
 
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
xs = []
r = 1
for i in range(N):
    x, l = map(int, input().split())
    a,b = x-l, x+l
    xs.append((a,b))
xs.sort()
xs = xs[::-1]
for i, (a, b) in enumerate(xs):
    if i == 0:
        ba, bb= a, b
        continue
    if ba<b:
        continue
    else:
         ba, bb = a, b
         r += 1
print(r)

Submission status: Accepted

Solution code:
n = int(input())
x_l = []
for i in range(n):
    x,l = map(int,input().split())
    x_l.append([x-l,x+l])
x_l = sorted(x_l, key=lambda x:x[0])
x_r = sorted(x_l, key=lambda x:x[1])
ans_l = n
ans_r = n
for i in range(n-1):
    if x_l[i][1] > x_l[i+1][0]:
        ans_l -= 1
        x_l[i+1] = x_l[i]
    if x_r[i][1] > x_r[i+1][0]:
        ans_r -= 1
        x_r[i+1] = x_r[i]
print(max(ans_l, ans_r))

Submission status: Accepted

Solution code:
n = int(input())
robo = []
for _ in range(n):
    robo.append(list(map(int, input().split())))
robo.sort()
#print(robo)
cnt = 0
i = 0
j = 0
#remove_robo = []
while i < n-1:
    j = i+1
    while j < n:
        if (robo[i][0]+robo[i][1]) > (robo[j][0] - robo[j][1]):
            #remove_robo.append(j)
            cnt+=1
            if (robo[i][0]+robo[i][1]) > (robo[j][0]+robo[j][1]):
                i = j
                j+=1
            else:
                j+=1
            if j == n:
                i = j
                break
        else:
            i=j
            break

print(n-cnt)

Submission status: Accepted

Solution code:
N = int(input())
arr = [list(map(int,input().split())) for i in range(N)]
arr = sorted(arr, key=lambda x: x[0])
F = [True]*N
P = [0]*N
for i in range(N):
  P[i] = [arr[i][0]-arr[i][1], arr[i][0]+arr[i][1]]
P = sorted(P,key=lambda x:x[1])
ind = 0
for i in range(1,N):
  if P[i][0] < P[ind][1]:
    F[i] = False
  else:
    ind = i
print(F.count(True))

Submission status: Accepted

Solution code:
import sys
bbn=1000000007
	
#+++++

		
def main():
	n = int(input())
	al=[]
	for i in range(n):
		b , c = map(int, input().split())
		al.append([b+c,b-c,b,c])
	al.sort()
	#pa(al)
	init=al[0]
	count=1
	for right,left,x,l in al[1:]:
		if left >= init[0]:
			count+=1
			init=[right,left,x,l]
	print(count)
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

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

robo_list = sorted(robo_dic.keys())

max_place = robo_list[0] + robo_dic[robo_list[0]]
ans = 1
for i in range(1, len(robo_list)):
    x = robo_list[i]
    l = robo_dic[x]
    if max_place <= x - l:
        ans += 1
        max_place = x + l
    else:
        max_place = min(max_place, x + l)
print(ans)

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N = int(input())
    X = []
    L = []
    LX = []
    for i in range(N):
        temp = list(map(int,input().split()))
        LX.append([temp[0]+temp[1],temp[0]-temp[1]])

    LX.sort()

    res = 0
    end = - 10 ** 9

    for i in range(N):
        if end <= LX[i][1]:
            res += 1
            end = LX[i][0]

    print(res)



main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
m=[]
for i in range(n):
    x,l=map(int,input().split())
    m.append((x+l,x-l))
m.sort()
ans=1
limit=m[0][0]
for i in range(1,n):
    if m[i][1]<limit:
        continue
    ans+=1
    limit=m[i][0]
print(ans)

Submission status: Accepted

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

tmp = sum(xl[0])

res = 0
for i in range(1, n):
    x, l = xl[i]
    if tmp > x-l:
        res += 1
        tmp = min(tmp, x+l)
    else:
        tmp = x+l

print(n-res)

Submission status: Accepted

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

n = int(input())
a = []
b = []
b2 = []
c = []
count = 0
max = 0

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

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

for i in a:
    if max != 0 and i[0]-i[1] < max:
        count += 1
    else:
        max = i[2]
    
print(n - count)

Submission status: Accepted

Solution code:
n=int(input())
xls=[list(map(int,input().split())) for _ in range(n)]
lrs=sorted((x-l,x+l) for x,l in xls)
res=0
most_r=lrs[0][0]
for l,r in lrs:
  if l>=most_r:
    res+=1
    most_r=r
  elif most_r>r:
    most_r=r
print(res)

Submission status: Accepted

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

a=[0]*n
b=[0]*n


for i in range(n):
    a[i],b[i]=x[i]-l[i],x[i]+l[i]


c=[[0]*2  for i in range(n)]


for j in range(n):
    c[j][0]=b[j]
    c[j][1]=a[j]


c.sort()


ans=0
z=c[0][1]
for i in range(n):
    if c[i][1]>=z:
        ans+=1
        z=c[i][0]

print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby
from operator import itemgetter
import numpy as np
N = int(input())
arm = []
for i in range(N):
  x, l = map(int, input().split())
  a = [x-l, x+l]
  arm.append(a)
arm = sorted(arm, key=lambda x: x[1])
now = arm[0][1]
count = 1
for i in range(1,N):
  if now <= arm[i][0]:
    count += 1
    now = arm[i][1]
print(count)

Submission status: Accepted

Solution code:
import numpy as np

stdin = np.fromstring(open(0).read(), np.int64, sep=' ')
N = stdin[0]
XL = stdin[1:].reshape(-1, 2).T
x = XL[0]
l = XL[1]
arg = np.argsort(x)
x = x[arg]
l = l[arg]
xleft = x - l
xright = x + l

count = 0
i = 0
while i < N - 1:
    for j in range(i + 1, N):
        if xright[i] > xright[j]:
            count += 1
            i = j
            break
        if xright[i] > xleft[j]:
            count += 1
            j = j + 1
        else:
            i = j
            break
    else:
        i = N - 1

print(N - count)

Submission status: Accepted

Solution code:
from operator import itemgetter
N= int(input())
ans = 1
a = []

for i in range(N):
    tmpa, tmpb = map(int,input().split())
    a.append([tmpa+tmpb, tmpa-tmpb])

a.sort()
    
tmp = a[0][0]
for i in range(1, N):
    if a[i][1] >= tmp:
        ans += 1
        tmp = a[i][0]
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

count = 1
arms = []
for i in range(len(xl)):
    a = xl[i][0] - xl[i][1]
    b = xl[i][0] + xl[i][1]
    arms.append([a, b])
arms.sort(key=lambda x: x[1])
min = arms[0][1]


for i in range(1, n):
    if min <= arms[i][0]:
        count += 1
        min = arms[i][1]

print(count)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

XL = []
for i in range(N):
    tmp = list(map(int, input().split()))
    XL.append(tmp)
    
XL = sorted(XL, key=lambda x:x[0])

i = 0
now = 0
count = 0
while i <= len(XL)-2:
    now_arm = XL[now][0] + XL[now][1]
    if now_arm > XL[i+1][0] - XL[i+1][1]:
        count += 1
        if XL[i+1][0] + XL[i+1][1] < now_arm:
            now = i+1
        else:
            pass
    else:
        now = i+1
    i += 1    


#print(XL)
print(len(XL) - count)

Submission status: Accepted

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


N = int(input())
start = []
end = []
itv = []
for i in range(N):
    X, L = (int(i) for i in input().split())
    itv.append([X+L, X-L])
    #start.append(X-L)
    #end.append(X+L)

#XL = [[int(i) for i in input().split()] for i in range(N)] 

#line = [0] * (2*(10**9) +1)

itv.sort()

#print(itv)

ass = 0
tt = 0-10**9
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())
A=[list(map(int,input().split())) for i in range(n)]
B=[]
for i in range(n):
    B.append([A[i][0]-A[i][1],A[i][0]+A[i][1]])
B=sorted(B)
point=B[0][1]
a,b=1,1
for i in range(1,n):
    if B[i][0]>=point:
        point=B[i][1]
        a +=1

point=B[-1][0]
for i in reversed(range(0,n-1)):
    if B[i][1]<=point:
        point=B[i][0]
        b +=1

print(max(a,b))