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:
# -*- coding: utf-8 -*-
import sys
from itertools import product
from collections import Counter, defaultdict
from string import ascii_uppercase as ABC
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N = int(input())
R = []
for _ in range(N):
    x, l = inpl()
    R.append([x-l, x+l])

R = sorted(R, key=lambda x: x[1])
now = -10**10
ans = 0
for l, r in R:
    if l < now:
        continue
    ans += 1
    now = r
print(ans)

Submission status: Accepted

Solution code:
import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial

sys.setrecursionlimit(10**7)
N = int(input())
XL = [list(map(int, input().split())) for _ in range(N)]

itv = []
for xl in XL:
    itv.append([xl[0]-xl[1], xl[0]+xl[1]])
itv.sort(key=lambda x: x[1])

ans = 0
tt = -1 * (10**9 + 10)
for itvi in itv:
    if tt <= itvi[0]:
        ans += 1
        tt = itvi[1] 

print(ans)

Submission status: Accepted

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

lxrs = sorted(lxrs)
cur_l = lxrs[0][0]
cur_r = lxrs[0][2]
cnt = 0
for l, x, r in lxrs[1:]:
    if cur_r <= l:
        cur_l, cur_r = l, r
        cnt += 1
    elif r <= cur_r:
        cur_l, cur_r = l, r

print(cnt+1 )

Submission status: Accepted

Solution code:
n = int(input())
robots = [[int(s) for s in input().strip().split()] for _ in range(n)]
robots = sorted([(x - l, x + l) for x, l in robots], key=lambda x: x[1])
result = 0
reach = float("-inf")
for l, r in robots:
  if l >= reach:
    result += 1
    reach = r
print(result)

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:
import sys
input = sys.stdin.readline
N = int(input())
xl = []
for i in range(N):
    x, l = [int(i) for i in input().split()]
    xl.append((x, l, x+l))
xl.sort(key=lambda x: x[2])
n = xl[0][2]
ans = 1
for x, l, s in xl[1:]:
    if x-l >= n:
        ans += 1
        n = s
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n=II()
    hp=[]
    for _ in range(n):
        X,L=MI()
        heappush(hp,(X+L,X-L))
    ans=0
    pr=-10**10
    while hp:
        r,l=heappop(hp)
        if l<pr:continue
        ans+=1
        pr=r
    print(ans)

main()

Submission status: Accepted

Solution code:
N = int(input())
rm = 0
r = -float('inf')
robot = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: x[0] + x[1])

for x, l in robot:
    if x - l < r:
        rm += 1
    else:
        r = max(r, x + l)

print(N - rm)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

N = int(input())
LR = []
for _ in range(N):
    a, b = map(int, input().split())
    LR.append((a-b, a+b))

LR.sort(key=itemgetter(1))
now_max = -10**15
ans = N
for l,r in LR:
    if l < now_max:
        ans -= 1
    else:
        now_max = r

print(ans)

Submission status: Accepted

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


# 区間スケジューリングか？
N = read_a_int()
ST = []
for _ in range(N):
    x, l = read_ints()
    ST.append((x - l, x + l))

from operator import itemgetter
ST.sort(key=itemgetter(1))

# 区間スケジューリングを適応していく
pret = ST[0][1]
ans = 0
for s, t in ST:
    if s < pret:
        continue
    ans += 1
    pret = t
print(ans + 1)

Submission status: Accepted

Solution code:
N = int(input())
XL = [tuple(map(int,input().split())) for _ in range(N)]
#print(XL)
X = []
for x,l in XL:
  X.append((x-l,x+l))
X.sort(key=lambda x:x[1])
#print(X)
ans = 0
p = -(10**10)
for a,b in X:
  if p <= a:
    ans += 1
    p = b
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

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

ans = 0
t = 0
for r in rng:
    if t <= r[0]:
        ans += 1
        t = r[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()

kosuu = 0
maenomigi = -100000000000000000000000
for migi, hidari in robos:
    # ok
    if maenomigi <= hidari:
        maenomigi = migi
        kosuu += 1

print(kosuu)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
x=[]
for i in range(n):
    a,b=map(int, input().split())
    x.append([a+b, a-b])
x.sort()
count=1
last=x[0][0]
for a in x:
    if a[1]>=last:
        count+=1
        last=a[0]
print(count)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    XL = [[int(i) for i in input().split()] for j in range(N)]
    rs = [[xl[0] - xl[1], xl[0] + xl[1]] for xl in XL]
    rs.sort(key=lambda p: p[1])
    ans = 1
    pre = rs[0][1]
    for r in rs[1:]:
        if pre <= r[0]:
            ans += 1
        else:
            continue
        pre = r[1]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
X, L = [], []
for _ in range(N):
    tmp_x, tmp_l = map(int, input().split())
    X.append(tmp_x)
    L.append(tmp_l)

end = [[X[i], L[i], X[i] + L[i]] for i in range(N)]
end = sorted(end, key = lambda x: x[2])

ans = N
target = 0
for i in range(1,N):
    if end[target][0] + end[target][1] <= end[i][0] - end[i][1]:
        target = i
    else:
        ans -= 1

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])
B=sorted(A,key=lambda x: x[1])
s = B[0][1]
n = 1
for i in range(1,N):
    a = B[i][0]
    b = B[i][1]
    if a >= s:
        n += 1
        s = b
print(n)

Submission status: Accepted

Solution code:
import sys
n = int(input())
INF = 10**18
ls = []
for i in range(n):
    x, l = [int(i) for i in sys.stdin.readline().split()]
    ls.append([x - l, x + l])
ls.sort(key=lambda x:x[1])
cnt = 0
_min = -INF
for l in ls:
    if l[0] >= _min:
        cnt += 1
        _min = l[1]
print(cnt)

Submission status: Accepted

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

N = int(input())
l = []

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

l.sort(key=lambda k: k[1])
now = -10**18
ans = 0
i = 0

while i<N:
    if now<=l[i][0]:
        now = l[i][1]
        ans += 1
    
    i += 1

print(ans)

Submission status: Accepted

Solution code:
def main():

    N = int(input())
    interval = []
    for _ in range(N):
        X, L = map(int, input().split())
        interval.append([X-L, X+L])
    interval.sort()
    cnt = 0
    i = 0
    while i < N:
        a, b = interval[i]
        cnt += 1
        i += 1
        while i < N and interval[i][0] < b:
            if interval[i][1] < b:
                a, b = interval[i]
            i += 1
    return cnt


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

Submission status: Accepted

Solution code:
n = int(input())

dg = 10**10
xl = []

for i in range(n):
    x,l = map(int,input().split())
    xl.append((x+l)*dg+l)
xl.sort()


start = -10**20
res = 0

for e in xl:
    end,s = e//dg,e//dg-2*(e%dg)

    if s >= start:
        res += 1
        start = end

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


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

    # print(r)
    cnt, end = 0, float("-inf")
    r.sort(key=lambda x: x[1])
    for x, y in r:
        if x >= end:
            end = y
        else:
            cnt += 1

    print(n - cnt)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

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

itv = []
idx = 0
for x,l in xl:
    s = x-l
    t = x+l
    itv.append([t,s])
    
    idx += 1

itv.sort()
ass = 0
tt = -10**10
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())

arr=[]

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

#print(arr)

ans = 0
start=-100000
fin=-1000

start = arr[0][2]
fin=arr[0][3]

for a,b,c,d in arr[1:]:
    if c < fin:
        ans+=1
        pass
    elif c >= fin:
        start=c
        fin = d

print(n-ans)

Submission status: Accepted

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

L = [[0,0] for _ in range(N)]
for i in range(N):
    L[i][0] = robot[i][0]-robot[i][1]
    L[i][1] = robot[i][0]+robot[i][1]-1

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

a = 0
b = -float('inf')

for i in range(N):
    if b < L[i][0]:
        a += 1
        b = L[i][1]

print(a)

Submission status: Accepted

Solution code:

N=int(input())
x = [list(map(int,input().split())) for _ in range(N)]
y = []
for i in range(N):
    y.append((x[i][0]-x[i][1], x[i][0]+x[i][1]))
y.sort(key = lambda x:x[1])
res = 0
t = -10**9
for i in range(N):
    if t <= y[i][0]:
        res += 1
        t = y[i][1]
print(res)

Submission status: Accepted

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

li = []
for x,l in xl:
    li.append([x-l,x+l])

li.sort(key = lambda x: x[1], reverse = False)

ans = 0
now = li[0][1]

for i in range(1,n):
    if li[i][0] < now:
        ans += 1
    else:
        now = li[i][1]

print(n - ans)

Submission status: Accepted

Solution code:
N=int(input())
P=[None]*N
for i in range(N):
  x,l=map(int,input().split())
  P[i]=[x,x-l,x+l]
  
P=sorted(P,key=lambda x:x[2])

ans=N
curL=P[0][1]
curR=P[0][2]
for i in range(1,N):
  l=P[i][1]
  r=P[i][2]
  if l<curR:
    ans-=1
  else:
    curR=r

print(ans)

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], x[0] - x[1]))

myinf = 10 ** 9 + 7

saved = []
pos = -myinf
for i, (Xi, Li) in enumerate(XL):
    # print("#", Xi, Li, (Xi - Li, Xi + Li))
    if Xi - Li < pos: continue
    #
    saved.append(i)
    pos = Xi + Li

print(len(saved))

Submission status: Accepted

Solution code:
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 = 0
t = -10**10
for i in range(n):
    if t <= data[i][0]:
        ans += 1
        t = data[i][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):
    X,L=map(int,input().split())
    l[i]=(X-L,X+L)
l.sort(key=lambda x: x[1])
t=-10**12
a=0
for i in l:
    if t<=i[0]:
        a+=1
        t=i[1]
print(a)

Submission status: Accepted

Solution code:
n = int(input())
s = []
t = []
for i in range(n):
    xa,la = map(int,input().split())
    s.append(xa-la)
    t.append(xa+la)
#print(s)
#print(t)

itv = []
for i in range(n):
    itv.append([t[i],s[i]])
itv.sort()

#print(itv)
ass = 0
tt = -1000000000
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())
s=[]
t=[]
for i in range(n):
    x,l=map(int,input().split())
    s.append(x-l)
    t.append(x+l)
itv = []
for i in range(n):
    itv.append([t[i],s[i]])
itv.sort()

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

Submission status: Accepted

Solution code:
import sys
from bisect import bisect
from operator import itemgetter

n = int(input())
robots = []
for line in sys.stdin:
    X, L = map(int, line.split())
    l, r = X - L, X + L
    robots.append((l, r))
robots.sort(key=itemgetter(1))

dp = [-(10 ** 18)]
for l, r in robots:
    i = bisect(dp, l)
    if len(dp) == i:
        dp.append(r)
    else:
        dp[i] = min(dp[i], r)
print(len(dp) - 1)

Submission status: Accepted

Solution code:
N = int(input())

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [[0, 0] for _ in range(N)]
for i in range(N):
  X, L = map(int, input().split())
  A[i] = [X + L, X - L]
A.sort()
R = A[0][1]
cnt = 0
for r, l in A:
  if l < R:
    continue
  R = r
  cnt += 1
print(cnt)

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])

x_max = -10**10
ans = 0
for s, t in robots:
    if s < x_max:
        continue
    ans += 1
    x_max = t
print(ans)

Submission status: Accepted

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

A = sorted(A, key=lambda x:x[1])
p = -10**10
ans = 0
for l, r in A:
    if l>=p:
        ans += 1
        p = r
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
t = []
for i in range(N):
    Xi, Li = map(int,input().split())
    t.append((Xi - Li, Xi + Li))
t.sort(key = lambda x:x[1])
# print(t)

ans = 0; x = -10**9
for i in range(N):
    if x <= t[i][0]:
        ans += 1
        x = t[i][1]
        # print(t[i]) #DB

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])
A.sort()

t = -10**10
p = 0
for i,a in enumerate(A):
    if a[0]-a[1]>=t:
        t = a[0]+a[1]
        p += 1
    elif a[0]+a[1]<t:
        t = a[0]+a[1]

print(p)

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
XL = []
for _ in range(N):
    x, l = lr()
    XL.append((x+l, 2 * l))

XL.sort()
r = - 10 ** 10
answer = 0
for right, l in XL:
    if r <= right - l:
        answer += 1
        r = right

print(answer)

Submission status: Accepted

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

LR = [[0] * 2 for _ in range(N)]

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

LR.sort()
ans = N
k = LR[0][1]
for i in range(1, N):
  l, r = LR[i]
  if l < k:
    ans -= 1
    k = min(k, r)
  else:
    k = r

print(ans)

Submission status: Accepted

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

from operator import itemgetter

# 区間スケジューリング

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

LR = [(x-l,x+l) for x,l in XL]
LR.sort(key = itemgetter(1))

INF = 10 ** 18
prev_R = -INF
cnt = 0
for L,R in LR:
    if prev_R > L:
        continue
    cnt += 1
    prev_R = R

print(cnt)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    XL=LLIN(N)
    XL.sort(key=lambda x: x[0]+x[1])
    dp = [1]*N
    now = -inf
    ans = 0
    for i,(x,l) in enumerate(XL):
        if now <= x-l:
            now = x+l
            ans += 1

        idx = bisect_left(XL,[x-l,0])
        if idx:
            dp[i] = dp[idx-1] + 1
        if i:
            dp[i] = dp[i-1]

        # dp[i] = bisect_left(XL,x-l)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

d = sorted(s)
dd = {j:i for i,j in enumerate(d)}
#print(dd)
m = len(d)
q.sort(key=lambda x: x[1])
DP = [0]*(m+1)

cur = 0
for i in range(m):
    DP[i] = max(DP[i-1], DP[i])
    while cur < n and dd[q[cur][1]] == i:
        DP[i] = max(DP[i], DP[dd[q[cur][0]]]+1)
        cur += 1
    #print(DP)
print(DP[m-1])

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()
#print(L)
ans=0
X=-10**9
for i in range(N):
    if L[i][1]>=X:
        ans+=1
        X=L[i][0]
print(ans)

Submission status: Accepted

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

arr.sort()

prev = float('-inf')
ans = 0
for right, left in arr:
    if left < prev:
        ans += 1
    else:
        prev = right
print(N - ans)

Submission status: Accepted

Solution code:
N = int(input())
X = [0]*N
for i in range(N):
    X[i] = [0]*2
    x, l = map(int, input().split())
    X[i][1] = x - l
    X[i][0] = x + l
X = sorted(X)
nowplace = X[0][0]
ans = 1
for j in range(1, N):
    if nowplace <= X[j][1]:
        ans += 1
        nowplace = X[j][0]

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys

    input = sys.stdin.readline

    n = int(input())

    xl = [tuple(map(int, input().split())) for _ in range(n)]
    xl.sort(key=lambda xl: sum(xl))

    ret = 0
    prev_right_edge = - 10 ** 10

    for x, l in xl:
        if (x - l) < prev_right_edge:
            # remove
            pass
        else:
            ret += 1
            prev_right_edge = x + l

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = input()
X = [0]*N
L = [0]*N
for i in range(N):
  X[i], L[i] = map(int, raw_input().split())

XL = [(X[i], L[i]) for i in range(N)]
XL.sort()
for i in range(N):
  X[i], L[i] = XL[i]

ans = N
m = -10**20
for i in range(N):
  if X[i]-L[i]<m:
    ans -= 1
    m = min(m, X[i]+L[i])
  else:
    m = max(m, X[i]+L[i])
print ans

Submission status: Accepted

Solution code:
def main():
    import sys
    import math
    N=int(sys.stdin.readline())
    T=[]
    for i in range(N):
        x,l=map(int,sys.stdin.readline().split())
        s=max(x-l,0)
        e=x+l
        T.append((s,e))
    T.sort(key=lambda x:x[1])
    now=0
    count=0
    for s,e in T:
        if s<now:
            continue
        else:
            count+=1
            now=e
    print(count)
main()

Submission status: Accepted

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

data.sort()
cnt=1
R=data[0][0]
for i in range(1,N):
    r,l=data[i]
    if R<=l:
        R=r
        cnt+=1
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
robo = [None] * N
for i in range(N):
    x, l = map(int, input().split())
    robo[i] = (x - l, x + l)

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


t = robo[0][1]
cnt = 1

for i in range(1, N):
    j = robo[i]
    if j[0] >= t:
        t = j[1]
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
q = list()
for _ in range(int(input())):
  x,l = map(int, input().split())
  q.append((x-l,x+l))
q.sort(key=lambda x:x[1])
cur = -10**10
cnt = 0
for s,t in q:
  if cur <= s:
    cnt += 1
    cur = t
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))
A.sort(key=lambda x:x[0]+x[1])
ans = 0
b = -float("inf")
for a in A:
    if b<=(a[0]-a[1]):
        ans+=1
        b = (a[0]+a[1])
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))
robots.sort()

mx = -(10 ** 9)
n = 0
for x, l in robots:
    if x - l >= mx:
        n += 1
        mx = x + l
    else:
        mx = min(mx, x + l)

print(n)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	S = []
	for i in range(N):
		X, L = getlist()
		S.append([X + L, X - L])
	S = sorted(S)
	# print(S)
	ans = 1
	val = S[0][0]
	for i in range(1, N):
		if S[i][1] >= val:
			ans += 1
			val = S[i][0]
	print(ans)
	


if __name__ == '__main__':
	main()

Submission status: Accepted

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

lr = []
for x, l in xl:
    lr.append([x - l, x + l])

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

cnt = 1
left, right = lr[0]
for ll, rr in lr:
    if ll >= right:
        cnt += 1
        left = ll
        right = rr

print(cnt)

Submission status: Accepted

Solution code:

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

ans = 0
prev = -10**9 - 7

for i in range(n):
    if A[i][1] >= prev:
        prev = A[i][0]
        ans += 1
print(ans)

Submission status: Accepted

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

LR = [[x-l,x+l] for x,l in XL]
LR.sort(key= lambda x:(x[1],x[0]))

r_max = -10**10
ans = 0
for l,r in LR:
    if l >= r_max:
        r_max = r
        ans += 1
print(ans)

Submission status: Accepted

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

LR = [(x - l, x + l) for x, l in XL]
LR.sort(key = lambda x: x[1])
#print(LR)

right = LR[0][1]
answer = 1

for i in range(1, N):
  if right <= LR[i][0]:
    right = LR[i][1]
    answer += 1
print(answer)

Submission status: Accepted

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

S = [[x - l, x + l] for x, l in X]
S.sort(key=lambda x: x[1])

ans = 0
tmp = -10 ** 12
for x, y in S:
    if tmp <= x:
        ans += 1
        tmp = y
        
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))

INF = 1e10
last = -INF
    
robots.sort()

ans = 0
for (r, l) in robots:
    if l < last:continue
    ans += 1
    last = r

print(ans)

Submission status: Accepted

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

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

ans = 0
RNow = -float('inf')
for L, R in LRs:
    if RNow <= L:
        ans += 1
        RNow = R

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 2 * n))
    b = [(dat[i*2] + dat[i*2+1], dat[i*2] - dat[i*2+1]) for i in xrange(n)]
    b.sort()
    ans = 1
    c = b[0][0]
    for r, l in b:
        if l >= c:
            ans += 1
            c = r
    print ans
main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    xl = [list(map(int, input().split())) for _ in [0]*n]
    xy = [(x-l, x+l) for x, l in xl]
    xy.sort(key=lambda x: x[1])
    cnt = 0
    now = -10**10
    for x, y in xy:
        if x >= now:
            cnt += 1
            now = y
    print(cnt)


main()

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()
ans = 0
last_end = -10 ** 10
for end, start in robots:
    if last_end <= start:
        last_end = end
        ans += 1
print(ans)

Submission status: Accepted

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

for i in range(N):
    L[i] = [L[i][0]+L[i][1], L[i][0], L[i][1]]
    
L.sort()
ans = 0
x = -10**10
for i in range(N):
    if x <= L[i][1]-L[i][2]:
        ans += 1
        x = L[i][0]

print(ans)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
X, L = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))

# 右端が左にあるものからとる
X = np.array(X, dtype=int)
L = np.array(L, dtype=int)

R = X + L
L = X - L
I = R.argsort()
R = R[I].tolist()
L = L[I].tolist()

ans = 0
m = -INF
for l, r in zip(L, R):
    if m <= l:
        m = r
        ans += 1
print(ans)