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:
import sys
from collections import deque

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())

sys.setrecursionlimit(10 ** 9)


def main():
    N = INT()
    l = []
    for _ in range(N):
        X, L = MAP()
        l.append([X-L, X+L])

    q = deque(sorted(l, key=lambda x: (x[0], x[1])))

    cnt = N
    xm, xl = q.popleft()
    for i in range(N-1):
        nm, nl = q.popleft()
        if nm < xl:
            cnt -= 1
            if nl < xl:
                xm = nm
                xl = nl
        else:
            xm = nm
            xl = nl

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

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

point.sort()

dp = []
dp.append([1,point[0][1]+point[0][0]])
for i in range(1,N):
    x = point[i][0]
    l = point[i][1]
    n = dp[i-1][0]
    if dp[i-1][1]<=x-l:
        dp.append([n+1, x+l])
    else:
        dp.append([n,min(dp[i-1][1],x+l)])

ans = dp[-1][0]
print(ans)

Submission status: Accepted

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

length = []
for i in range(N):
    s = XL[i][0] - XL[i][1]
    f = XL[i][0] + XL[i][1]
    length.append([s, f])

length = sorted(length, key=lambda x:x[1])
ans = 0
f = - (10**9+7)
for i in range(N):
    if f <= length[i][0]:
        ans += 1
        f = length[i][1] - 0.5

print(ans)

Submission status: Accepted

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

li2 = []
for i in range(n):
    li2.append([li[i][0]-li[i][1],li[i][0]+li[i][1]])

li2.sort()

nw = li2[0][1]
ans = 1
for i in range(1,n):
    if li2[i][0] >= nw:
        ans += 1
        nw = li2[i][1]
    elif li2[i][1] < nw:
        nw = li2[i][1]


print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

N = int(input())
X = []
L = []
for _ in range(N):
    row = list(map(int,input().split()))
    X.append(row[0])
    L.append(row[1])

# Xでソート
c = list(zip(X, L))
c.sort(key=itemgetter(0))
X, L = zip(*c)

# stack
stack = []
stack.append(0)
# 2~N番を，それ以前と重複しなければpush
for i in range(1,N):
    X1 = X[stack[-1]]
    L1 = L[stack[-1]]
    X2 = X[i]
    L2 = L[i]
    # 重複しなければ
    # print(X1+L1,X2-L2)
    if X1+L1 <= X2-L2:
        stack.append(i)
    else:
        # 重複していて，新しく追加する腕のほうが→にあれば
        if X1+L1 <= X2+L2:
            # なにもしない
            continue
        else:
            # 前のロボットを消して，追加する
            stack.pop()
            stack.append(i)


print(len(stack))

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())

left = np.zeros(n)
right = np.zeros(n)
for i in range(n):
    x, l = map(int, input().split())
    left[i] = int(x-l)
    right[i] = int(x+l)

sort_ind = np.argsort(right)
left = left[sort_ind]
right = right[sort_ind]

ans = 0
right_now = -1 * 10**10
for i in range(n):
    if(left[i] >= right_now):
        ans += 1
        right_now = right[i]

print(ans)

Submission status: Accepted

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

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

ans = n
pos = 0
tmp_l,tmp_r = 0,0
for i in range(n):
    x,l,r = lst[i]
    if i==0:
        pos = x
        tmp_l, tmp_r = l,r
    else:
        #かぶりなし
        if tmp_r <= l:
            pos = x
            tmp_l = l
            tmp_r = r
        #かぶりあり
        else:
            ans -= 1
            if tmp_r <= r:
                continue
            else:
                pos = x
                tmp_l = l
                tmp_r = r
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

for i in range(n):
    a, b = map(int, input().split())
    T.append( (a-b, a+b) )

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

ans = 1
cur = T[0]

for k, v in enumerate(T):
    if k == 0: continue
    if v[0] >= cur[1]:
        ans += 1
        cur = v

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
x=[]
for i in range(n):
  x1,l1=map(int,input().split())
  x.append([x1+l1,l1])
x.sort()
s=1
m=x[0][0]
for i in range(n):
  if m<=x[i][0]-2*x[i][1]:
    s+=1
    m=x[i][0]
print(s)

Submission status: Accepted

Solution code:
import copy

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

for i in range(n):
    a = [int(x) for x in input().split()]
    a.append(a[0]+a[1])
    A.append(a)

A.sort(key=lambda x: x[2])
#print(A)

count = 0
max_l = -10000000000
for i in A:
    if i[0]-i[1] >= max_l:
        count += 1
        max_l = i[2]

print(count)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())

XL = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]
R = []
for i in range(N):
    R.append([XL[i][0] - XL[i][1], XL[i][0] + XL[i][1]])
R.sort(key=lambda x:x[1])
ans = [R[0]]

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

print(len(ans))

Submission status: Accepted

Solution code:
N = int(input())
robots = []
for _ in range(N):
    X,L = map(int,input().split(' '))
    x = X-L
    l = 2*L
    robots.append([x,l+x])
robots.sort()
#print(robots)

cnt = 0
start = robots[0][0]
end = robots[0][1]
result = []
for i in range(1,N):
    x = robots[i][0]
    l = robots[i][1]
    if x < end:
        if end < l:
            continue
        else:
            start = x
            end = l
    else:
        result.append([start,end])
        start = x
        end = l
print(len(result)+1)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


#mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np


def main():
	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])
	
	b=li[0][1]
	ans=n
	
	for i in range(1,n):
		if li[i][0]<b:
			b=min(b,li[i][1])
			ans-=1
		else:
			b=li[i][1]
	print(ans)




if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
N = int(input())
#key:いる位置, value:右手の位置
range_dct = {}
for i in range(N):
    x, l = map(int, input().split())
    range_dct[x] = x + l

range_dct_sorted = sorted(range_dct.items(), key=lambda x:x[1])

counter = 0
right = -100000000000

for key, value in range_dct_sorted:
    if right <= key * 2 - value:
        right = value
        counter += 1

print(counter)

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]])
C=sorted(B, key=lambda x: x[1])
cnt=0
r=-1*10**9
for i in range(N):
  if r<=C[i][0]:
    cnt+=1
    r=C[i][1]
print(cnt)

Submission status: Accepted

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

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

lr.sort()
r_max=lr[0][1]

ans=N
for i in range(1,N):
    if lr[i][0]<r_max:#被り
        ans-=1
        r_max=min(r_max,lr[i][1])
    else:
        r_max=max(r_max,lr[i][1])
    
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
s = [i[0]-i[1] for i in a]
t = [i[0]+i[1] for i in a]

st = sorted([(s[i], t[i]) for i in range(n)], key=itemgetter(1))
ans = 0
last = -10**10

for i in range(n):
    if last <= st[i][0]:
        ans += 1
        last = st[i][1]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

xl = (map(int, input().split()) for _ in range(n))
w = [(x - l, x + l) for x, l in xl]
w = sorted(w, key=lambda x: x[1])
cur = w[0][1]
res = 1
for l, r in w[1:]:
    if l >= cur:
        res += 1
        cur = r
print(res)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
  x,l=map(int,input().split())
  a.append((x+l,2*l))
a.sort()
ans=1
x,l=a[0]
for i in range(1,n):
  xx,ll=a[i]
  if x<=xx-ll:
    ans+=1
    x,l=xx,ll
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
xl = []
for i in range(N):
    tmp = list(map(int, input().split()))
    if tmp[0] - tmp[1] < 0:
        xl.append((tmp[0] + tmp[1], 0))
    else:
        # 終了範囲，開始範囲
        xl.append((tmp[0] + tmp[1], tmp[0] - tmp[1]))
        
xl_sorted = sorted(xl, key=lambda x: x[0])
#print(xl_sorted)
ans = 0
t = 0
# tは前のロボットの後ろの範囲
for i in range(N):
    if t <= xl_sorted[i][1]:
        ans += 1
        t = xl_sorted[i][0]
print(ans)

Submission status: Accepted

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

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

i=1
finish=c[0][1]
cnt=1
while i<n:
    if c[i][0]>=finish:
        finish=c[i][1]
        cnt+=1
    i+=1
print(cnt)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    R = [None] * N
    for i in range(N):
        x, l = map(int, input().split())
        R[i] = (x + l, x - l)
    R.sort()
    
    right_most = R[0][0]
    save = 1
    for i in range(1, N):
        if R[i][1] >= right_most:
            save += 1
            right_most = R[i][0]

    left_most = R[N-1][1]
    saver = 1
    for i in reversed(range(N-1)):
        if R[i][0] <= left_most:
            saver += 1
            left_most = R[i][1]


    print(max(save, saver))


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())
a = 0
ans = 0
rob = []
for i in range(N):
    x,l = map(int,input().split())
    rob.append((x-l,x+l,x,l))
rob.sort()
for i in range(N):
    a,b,c,d = rob[i]
    rob[i] = (b,a,c,d)
rob.sort()
for i in range(N):
    p,q,x,l = rob[i]
    if i == 0:
        a = x + l
        ans += 1
    if x - l >= a:
        a = x + l
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

N=int(input()) 
XL = [[int(i) for i in input().split()] for i in range(N)] 
rl = [[x[0]+x[1],x[0]-x[1]] for x in XL]
rl = sorted(rl)

p = rl[0][0]
cnt = 1
for x in rl:
  if x[1] >=p:
    cnt += 1
    p = x[0]
    
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

robots = []

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

    robots.append((x - l, x + l))

robots.sort()


def opt(robots):
    l = len(robots)
    count = 0
    i = 1
    robot1 = robots[0]
    while i < l:
        robot2 = robots[i]
        if robot1[1] > robot2[0]:
            if robot1[1] < robot2[1]:
                robot2 = robot1
            count += 1
        robot1 = robot2
        i += 1
    return l - count

print(opt(robots))

Submission status: Accepted

Solution code:
import heapq
n = int(input())
robots = []
for _ in range(n):
    robot = tuple(map(int, input().split()))
    heapq.heappush(robots, robot)

robot = heapq.heappop(robots)
max_right = robot[0] + robot[1]
del_count = 0
for i in range(len(robots)):
    robot = heapq.heappop(robots)
    if max_right > robot[0] - robot[1]:
        del_count += 1
        max_right = min(max_right, robot[0] + robot[1])
    else:
        max_right = robot[0] + robot[1]
print(n-del_count)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]
 
def main():
    n = inp()
    LR = []
    for _ in range(n):
        x,l = inpm()
        LR.append((x-l,x+l))
    LR.sort()
    ans = 1
    index = 1
    l,r = LR[0]
    while index < n:
        if LR[index][0] < r and l < LR[index][1]:
            r = min(r,LR[index][1])
            index += 1
        else:
            ans += 1
            [l,r] = LR[index]
            index += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import namedtuple


def solve(arms):
    arms = sorted(arms, key=lambda x: x.right)
    right = -float("inf")
    res = 0
    for arm in arms:
        if right <= arm.left:
            res += 1
            right = arm.right

    return res


Arm = namedtuple("Arm", ["center", "left", "right"])


arms = []
N = int(input())
for _ in range(N):
    x, length = [int(val) for val in input().split(" ")]
    arm = Arm(x, x - length, x + length)
    arms.append(arm)


ans = solve(arms)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
B = sorted([[A[i][0]-A[i][1],A[i][0]+A[i][1]] for i in range(N)],key=lambda x:x[1])
cur = 1
C = [B[0]]
while cur<N:
    if B[cur][0]>=C[-1][1]:
        C.append(B[cur])
    cur += 1
print(len(C))

Submission status: Accepted

Solution code:
import heapq
N = int(input())
robo = list(list(map(int,input().split()))for _ in range(N))
robo.sort(key=lambda x:x[0])
queue = []
for x,l in robo:
    heapq.heappush(queue,[x+l,x-l])
ans = 0
left = -float('inf')
while queue:
    q = heapq.heappop(queue)
    if q[1] >= left:
        left = q[0]
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx

N = int(readline())
XL = [tuple(map(int, readline().split())) for _ in range(N)]
LR = [(x-l, x+l) for x, l in XL]

M = 2*N+1
inf = 1<<31
S = set([-inf])
for l, r in LR:
    S.add(l)
    S.add(r)
_, Cs = compress(list(S))
LR = [(Cs[l], Cs[r]) for l, r in LR]


table = [-inf]*M
for l, r in LR:
    table[r] = max(table[r], l)
dp = Segtree([None]*M, -inf, initialize = False, segf = max)
dp.update(0, 0)
for r in range(1, M):
    if table[r] == -inf:
        continue
    l = table[r]
    k = dp.query(0, l+1)
    dp.update(r, 1+k)

print(dp.query(0, M))

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

ans1=0
r=-10**9-1
for X,L in XL:
    if X-L>=r:
        ans1+=1
        r=X+L
ans2=0
l=-10**9+1
for X,L in reversed(XL):
    if X+L<=l:
        ans2+=1
        l=X-L

print(max(ans1,ans2))

Submission status: Accepted

Solution code:
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
X = I[1::2]
L = I[2::2]
coord = [[x - l, x + l] for x, l in zip(X, L)]
x_i = collections.defaultdict(int)
for lr in coord:
    x_i[lr[0]] = x_i[lr[1]] = 0
for i, v in enumerate(sorted(x_i.keys())):
    x_i[v] = i
for i in range(N):
    coord[i][0] = x_i[coord[i][0]]
    coord[i][1] = x_i[coord[i][1]]


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res


array = [-1] * len(x_i)
#array[r]: 腕が動く範囲が[l, r) となるロボットが存在するlの最大値
for l, r in coord:
    array[r] = max(array[r], l)
now = 0
ans = 0
for i in range(len(array)):
    if array[i] != -1 and array[i] >= now:
        now = i
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    XL = []
    for i in range(N):
        x, l = map(int, input().split())
        XL.append((x, l))
    XL.sort(key=lambda p: p[1] + p[0])

    ans = 0
    prev = -10**10
    for i in range(N):
        x, l = XL[i]
        if x - l >= prev:
            ans += 1
            prev = x + l
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

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

Submission status: Accepted

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

r = XL[0][1]
cnt = 1
for i in range(1, N):
    if XL[i][0] >= r:
        r = XL[i][1]
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, X: "List[int]", L: "List[int]"):
    if N == 1:
        print(1)
        return

    schedule = []
    for i in range(N):
        schedule.append((X[i]-L[i],X[i]+L[i]))
    
    schedule.sort(key= lambda x: x[1])

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    L = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        L[i] = int(next(tokens))
    solve(N, X, L)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n = int(input())
    xl = [list(map(int,input().split())) for i in range(n)]
    s = [(xl[i][0]-xl[i][1],xl[i][0]+xl[i][1]) for i in range(n)]
    s.sort(key = lambda x:x[1])
    cnt = 1
    t = s[0][1]
    for i in range(1,n):
        if t <= s[i][0]:
            cnt += 1
            t = s[i][1]
    print(cnt)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
from operator import itemgetter
N = int(input())
q = []
ans = 0
for i in range(N):
    x,l = map(int,input().split())
    q.append([x-l,x+l])
q = sorted(q,key = itemgetter(1))
last = -10**18
for i in range(N):
    tmp = q[i]
    if tmp[0] >= last:
        ans += 1
        last = tmp[1]
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = str(args[0])

    RL = []
    for xl in args[1:]:
        x, l = map(int, xl.split())
        RL.append((x+l, x-l))

    RL.sort()

    count = 1
    cur, _ = RL[0]
    for r, l in RL[1:]:
        if cur <= l:
            cur = r
            count += 1

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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


print(ans)

Submission status: Accepted

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

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

now = 0
count = 0
for i in range(1,n):
    if XL[now][3] > XL[i][2]:
        count += 1
    else:
        now = i
ans = n - count

print(int(ans))

Submission status: Accepted

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

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

# 貪欲
heapq.heapify(query)

finish, start = heapq.heappop(query)
time = finish
count = 1
while len(query) > 0:
    finish, start = heapq.heappop(query)
    if start >= time:
        time = finish
        count += 1
    else:
        continue
print(count)

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))
d.sort()
ans=1
chk=d[0][1]
for i in d:
    if i[0]>=chk:
        ans+=1
        chk=i[1]
    else:
        chk=min(chk,i[1])
print(ans)

Submission status: Accepted

Solution code:
_, *d = [list(map(int, s.split())) for s in open(0)]

d = sorted(d)
dd = []
for x, l in d:
    dd.append([x-l, x+l])

max_ = dd[0][0]
n = 0
for r, l in dd:
    if max_ <= r:
        n += 1
        max_ = l
    elif max_ > l:
        max_ = l
print(n)

Submission status: Accepted

Solution code:
n = int(input())
xl = [list(map(int,input().split())) for _ in range(n)]
xl_two = sorted([[xl[i][0]+xl[i][1],xl[i][0]-xl[i][1]] for i in range(n)])
ans = 0
flag = -float("inf")
for i in range(n):
  if flag <= xl_two[i][1]:
    flag = xl_two[i][0]
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XL = sorted([list(map(int,input().split())) for i in range(N)],key = lambda x:x[0]+x[1])
count = 0
now = -float('inf')
for i in range(N):
    if now <= XL[i][0]-XL[i][1]:
        count += 1
        now = XL[i][0]+XL[i][1]
print(count)

Submission status: Accepted

Solution code:
n = int(input())
xl = []
for i in range(n):
    xl.append(list(map(int,input().split())))
    xl[i].append(xl[i][0]+xl[i][1])
xl = sorted(xl,key=lambda x:x[2])
ans = 1
s = xl[0][2]
for i in range(1,n):
    if s <= xl[i][0]-xl[i][1]:
        s = xl[i][2]
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
tt = -10**9
for i in range(n):
    if tt <=l2[i][1]:
        ans += 1
        tt = l2[i][0]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
robot = []
ans = 1
chk = [0]*N
for i in range(N):
    robot.append([int(i) for i in input().split()])
robot.sort()
max_left = robot[0][0] + robot[0][1]
for i in range(N-1):
    if max_left <= (robot[i+1][0] - robot[i+1][1]):
        ans += 1
        max_left = robot[i+1][0] + robot[i+1][1]
    else:
        if max_left > robot[i+1][0] + robot[i+1][1]:
            max_left = robot[i+1][0] + robot[i+1][1]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
R = []
for i in range(N):
	X,L = map(int,input().split())
	R.append((X+L,X-L))
R.sort()
ans = 0
right = None
for x in R:
	l,r = x[1], x[0]
	if right == None:
		ans += 1
		right = r
	else:
		if l >= right:
			ans += 1
			right = r

print(ans)

Submission status: Accepted

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

#a = list(map(int, input().split()))

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

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

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

ans=0
prev=-999999999999
for i in range(n):
    if(prev<=robos[i][0]-robos[i][1]):
        ans+=1
        prev = robos[i][0]+robos[i][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([max(x-l, 0), x+l])

robots.sort(key=lambda robot: robot[1])

ans = 0
t = 0
for i in range(n):
    if t <= robots[i][0]:
        ans += 1
        t = robots[i][1]

print(ans)

Submission status: Accepted

Solution code:
N=int(input())

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

X.sort()
Y=X[0][0]+X[0][1]

cnt=0
for i in range(1,N):
    if Y>X[i][0]-X[i][1]:
        cnt+=1
        if X[i][0]+X[i][1]<Y:
            Y=X[i][0]+X[i][1]
    else:
        Y=X[i][0]+X[i][1]

print(N-cnt)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    p = LIR(n)
    p = [[p[i][0]-p[i][1],p[i][0]+p[i][1]] for i in range(n)]
    p.sort(key = lambda x:x[1])
    t = p[0][1]
    ans = 1
    for l, r in p[1:]:
        if t <= l:
            ans += 1
            t = r
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()