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: Time Limit Exceeded

Solution code:
def main():
    import sys #追加
    sys.setrecursionlimit(500*500) #追加
    n = int(input())

    x = []
    l = []
    tls = []
    for i in range(n):
        tmp = list(map(int, input().split()))
        x.append(tmp[0])
        l.append(tmp[1])
    x, l = zip(*sorted(zip(x, l)))

    m = {}
    def solve(prev, idx):
        if idx == n:
            return 0
        key = (prev, idx)
        if key in m:
            return m[key]
        res_use = 0
        res_nouse = 0

        if x[idx] - l[idx] >= prev or prev == 0:
            res_use = 1
            res_use += solve(x[idx] + l[idx], idx + 1)
        res_nouse += solve(prev, idx + 1)

        ans = max(res_use, res_nouse)
        m[key] = ans
        return ans
    print(solve(0, 0))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
res = n
num_list = []
max_list = []
for i in range(n):
    a,b = map(int,input().split(" "))
    if i == 0:
        for i in range(a-b,a+b+1):
            num_list.append(i)
    elif (a or b) in num_list:
            res -= 1
    else:
        for i in range(a-b,a+b+1):
            num_list.append(i)
        sorted(num_list)
        
print(res)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
from bisect import bisect_right


class SegmentTree(object):

    def __init__(self, init_array, seg_func=min, seg_func_null=10 ** 9 + 7):

        self.seg_func = seg_func
        self.seg_func_null = seg_func_null
        self.n = 1
        while self.n < len(init_array):
            self.n *= 2
        self.dat = [0] * (2 * self.n - 1)
        for i in range(len(init_array)):
            self.dat[self.n - 1 + i] = init_array[i]
        for i in range(self.n - 2, -1, -1):
            self.dat[i] = self.seg_func(self.dat[2 * i + 1], self.dat[2 * i + 2])

    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.seg_func(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, p, q):
        # [p, q)
        if q <= p:
            return self.seg_func_null

        p += self.n - 1
        q += self.n - 2
        res = self.seg_func_null

        while q - p > 1:
            if p & 1 == 0:
                res = self.seg_func(res, self.dat[p])
            if q & 1 == 1:
                res = self.seg_func(res, self.dat[q])
                q -= 1
            p = p // 2
            q = (q-1) // 2
        if p == q:
            res = self.seg_func(res, self.dat[p])
        else:
            res = self.seg_func(self.seg_func(res, self.dat[p]), self.dat[q])

        return res


def solve(n, x_list, le_list):
    right_limits = dict()
    for i in range(n):
        right_limits[x_list[i] + le_list[i]] = 0
    right_limits_list = list(sorted(list(right_limits.keys())))
    s = SegmentTree([0] * len(right_limits_list), max, -1)

    h = []
    for i in range(n):
        heappush(h, (x_list[i] + le_list[i], i))

    for k in range(n):
        right, i = heappop(h)
        left = x_list[i] - le_list[i]
        ind_left = bisect_right(right_limits_list, left)
        ind_right = bisect_right(right_limits_list, right) - 1
        if ind_left == 0:
            r = s.query(ind_right, ind_right + 1)
            if r == 0:
                s.update(ind_right, 1)
        else:
            r = s.query(ind_right, ind_right + 1)
            l_max = s.query(0, ind_left)
            if r < l_max + 1:
                s.update(ind_right, l_max + 1)

    return s.query(0, n)


def main():
    n = int(input())
    x_list = [0] * n
    le_list = [0] * n
    for i in range(n):
        x, le = map(int, input().split())
        x_list[i] = x
        le_list[i] = le
    res = solve(n, x_list, le_list)
    print(res)


def test():
    assert solve(4, [2, 4, 9, 100], [4, 3, 3, 5]) == 3
    assert solve(2, [8, 1], [20, 10]) == 1
    assert solve(5, [10, 2, 4, 6, 8], [1, 1, 1, 1, 1]) == 5


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

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline

    N = int(input())
    XL = []
    for i in range(N):
        X, L = map(int, input().split())
        XL.append((X+L, X-L, X, L))
    memo = [None] * (N+1)
    memo[0] = 0
    memo[1] = 1
    XL = sorted(XL)
    #print(XL)
    print(solve(N, XL, memo))
    #print(memo)

def solve(N, XL, memo):
    if N < 2:
        if N == 0:
            return 0
        if N == 1:
            return 1
    if memo[N] is not None:
        return memo[N]


    R1, L1, X1, A1 = XL[N-2]
    R2, L2, X2, A2 = XL[N-1]

    # a1 X2 を残す
    a1 = 1
    for i in range(N-1)[::-1]:
        r, l, x, a = XL[i]
        if r <= L2:
            a1 = solve(i+1, XL, memo)+1
            break
    # a2
    a2 = solve(N-1, XL, memo)
    a = max(a1, a2)
    memo[N] = a
    #print("solve(%d)=%d, a1=%d, a2=%d"% (N, a, a1, a2))
    return a

main()

Submission status: Time Limit Exceeded

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

jamas = [[] for _ in range(n)]
jamas_count = [0 for _ in range(n)]

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

    for j in range(0, i):
        if xs[j] < x:
            x1 = xs[j]
            l1 = ls[j]
            x2 = x
            l2 = l
        else:
            x1 = x
            l1 = l
            x2 = xs[j]
            l2 = ls[j]
        if x1 + l1 - 1 < x2 - l2 + 1:
            pass
        else:
            jamas[i].append(j)
            jamas[j].append(i)
            jamas_count[i] += 1
            jamas_count[j] += 1

def find_max_jama():
    max_jama = max(jamas_count)
    if max_jama == 0:
        return None

    max_i = jamas_count.index(max_jama)
    return max_i

n_remove = 0
while True:
    max_i = find_max_jama()
    if max_i is None:
        break

    aites = jamas[max_i]
    for aite in aites:
        jamas[aite].remove(max_i)
        jamas_count[aite] -= 1

    jamas[max_i] = []
    jamas_count[max_i] = 0
    n_remove += 1

out = n - n_remove
print(out)

Submission status: Time Limit Exceeded

Solution code:
n,*xl=map(int,open(0).read().split())
l=[]
for i in range(2*n-1)[::2]:
  l.append([xl[i]-xl[i+1]+1,xl[i]+xl[i+1]-1])
  l.sort()
tf=[]
for i in range(n-1):
  if l[i][1]>=l[i+1][0]:
    tf.append(False)
  else:
    tf.append(True)
print(n-tf.count(False))

Submission status: Time Limit Exceeded

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

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

check = [0] * n
ans = 0

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

for i in robo:
    for j in range(2*i[1] - 1):
        if i[0] - i[1] + 1 + j >= 0 and i[0] - i[1] + 1 + j < n:    
            check[i[0] - i[1] + 1 + j] = 1
        
    ans += 1
    
    k = 0
    for s in check:
        k += s
    if k == n:
        break
    
print(ans)

Submission status: Time Limit Exceeded

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

def d_min(a,b):
    return a-b
def d_max(a,b):
    return a+b

for i in range(n-1):
    if x[i] != 0:
        continue
    for k in range(1,n-i):
        if d_max(*l[i]) > d_min(*l[i+k]):
            c+=1
            x[i+1]+=1
print(n-c)

Submission status: Time Limit Exceeded

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

ans = 0
for b in range(2**n):
    flag = True
    bounds = 0
    for i in range(n):
        if (b>>i)&1:
            if bounds != 0 and bounds > (xl[i][0]-xl[i][1]+1):
                flag = False
                break
            bounds = xl[i][0] + xl[i][1] - 1
    if flag:
        ans = max(ans, bin(b).count("1"))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
interval = set([])

times = 0

for i in range(N):
    [X, L] = [int(i) for i in input().split()]
    newinterval = set(range(X-(L-1), X+(L-1)+1))
    if len(interval & newinterval) == 0:
        times += 1
    interval = interval | newinterval

print(times)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

line = []
ans = 0

for i in range(n):
  x, l = map(int, input().split())
  keep = True
  for j in range(x-l+1, x+l):
    if j in line:
      keep = False
    else:
      line.append(j)
  # print(keep)
  if keep == True:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = []
l = []
ans = [0 for i in range(n)]
for i in range(n):
  xx, ll = map(int, input().split())
  x.append(xx)
  l.append(ll)
  
for i in range(n):
  for j in range(n):
    if i != j:
      if (x[j]-l[j] < x[i]-l[i] < x[j]+l[j]) or (x[j]-l[j] < x[i]+l[i] < x[j]+l[j]):
        ans[j]+=1
m = max(ans)
if m == 0:
  print(len(ans))
else:
  aa = [e for e in ans if e != m]
  print(len(aa))

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

N = 1
X = []
L = []

N = int(input())
for i in range(N):
    temp1, temp2 = input().split()
    X.append(int(temp1))
    L.append(int(temp2))

ans = N
ansFlag = True
ansTemp = 0
while True:
    if ans == 1:
        if ansTemp < ans:
            ansTemp = ans
        break
    for sets in list(itertools.combinations(range(N),ans)):
        ansFlag = True
        for pair in itertools.combinations(sets,2):
            if X[pair[0]] <= X[pair[1]]:
                if X[pair[0]] + L[pair[0]] > X[pair[1]] - L[pair[1]]:
                    ansFlag = False
            if X[pair[0]] >= X[pair[1]]:
                if X[pair[0]] - L[pair[0]] < X[pair[1]] + L[pair[1]]:
                    ansFlag = False
        if ansFlag:
            if ansTemp < ans:
                ansTemp = ans
            break
    ans = ans-1
print(ansTemp)

Submission status: Time Limit Exceeded

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]]
for i in range(N):
  for j in range(i+1,N):
    if F[i]:
      if P[i][1] > P[j][0]:
        F[j] = False
      elif P[i][1] <= P[j][0]:
        break
print(F.count(True))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

ll = [[0]*i for i in range(n)]
for i in range(n):
  x, l =map(int, input().split())
  ll[i] = [x-l, x+l]
ll = sorted(ll)

l = [1] * n

for i in range(n-1):
  for j in range(i+1, n):
    if l[i] == 0:
      continue
    elif ll[i][1] > ll[j][0]:
      l[j] = 0
    else:
      break

print(sum(l))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lis = []
for i in range(n):
    a,b =map(int,input().split())
    lis.append([a-b,a+b])
lis.sort(key = lambda x:x[1])
dp = {(-2 * 10 ** 9,0)}
for aa,bb in lis:
    now = set()
    for nowa,ans in dp:
        if nowa <= aa:
            now.add((bb,ans+1))
        now.add((nowa,ans))
    dp = now
an = 0
for aaa,ans in dp:
    an = max(an,ans)
print(an)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n):
  count = 1
  right = xl[i][0] + xl[i][1]
  for j in range(i+1,n):
    if right <= xl[j][0] - xl[j][1] :
      count += 1
      right = xl[j][0] + xl[j][1] 
  ans = max(ans,count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    X = []
    L = []
    for i in range(N):
        x, l = [int(s) for s in input().split()]
        X.append(x)
        L.append(l)

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

    while True:
        dup = [0 for i in range(len(ranges))]
        for i in range(len(ranges) - 1):
            if ranges[i][1] > ranges[i + 1][0]:
                dup[i] += 1
                dup[i + 1] += 1

        remove_index = [(i, dup[i]) for i in range(len(dup))]
        remove_index.sort(key=lambda x: x[1], reverse=True)
        if remove_index[0][1] == 0:
            break
        ranges.pop(remove_index[0][0])
    print(len(ranges))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
XL=[]
for i in range(N):
    a,b=map(int,input().split())
    XL.append([a-b,a+b])
    #XL.append(list(map(int,input().split())))
XL=np.array(XL)

ans=0
end=-10**(19)
for i in range(N):
    x=XL[XL[:,0]>=end][:,1]
    if x.size!=0:
        end=min(x)
        ans+=1
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = []
l = []
ans = [0 for i in range(n)]
for i in range(n):
  xx, ll = map(int, input().split())
  x.append(xx)
  l.append(ll)
  
for i in range(n):
  for j in range(n):
    if i != j:
      if (x[j]-l[j] < x[i]-l[i] < x[j]+l[j]) or (x[j]-l[j] < x[i]+l[i] < x[j]+l[j]):
        ans[i]+=1
        
m = max(ans)

if m == 0:
  print(len(ans))
else:
  aa = [e for e in ans if e != m]
  print(len(aa))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
XL = []
for i in range(n):
  XL.append(list(map(int, input().split())))
XL.sort()
r = 0
cnt = 0
for i in range(n):
  xl = XL.pop(0)
  tmp = xl[0]+xl[1]
  #print('xl[0]',xl[0], 'and r', r)
  if xl[0]> r:
    r = tmp
    cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	tmp = []
	ans = []
	for i in range(N):
		X,L = inputMap()
		tmp1 = X-L
		tmp2 = X+L
		tmp.append((tmp1,tmp2))

	anstmp = 0
	for i,val in enumerate(tmp):
		kizyunX1, kizyunX2 = val
		for j in range(i+1,len(tmp)):
			taiX1, taiX2 = tmp[j]

			if kizyunX2 <= taiX1 or kizyunX1 >= taiX2:
				anstmp += 1

		ans.append(anstmp)

	aa = min(ans)
	#print(tmp)
	print(aa+1)
	#print(aa)


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

ll = [[0]*i for i in range(n)]
for i in range(n):
  x, l =map(int, input().split())
  ll[i] = [x-l, x+l]
ll = sorted(ll)

l = [1] * n

for i in range(n-1):
  for j in range(i+1, n):
    if l[i] == 1 and ll[i][1] > ll[j][0]:
      l[j] = 0

print(sum(l))

Submission status: Time Limit Exceeded

Solution code:

def Key2():
    N = int(input())
    cnt = 0
    plt = []
    for i in range(N):
        x, l = map(int, input().split())
        Lmin = x - l + 1
        Lmax = x + 1 - 1
        if Lmin in plt or Lmax in plt:
            cnt += 1
        else:
            tmplist = [x - l for l in range(-1 * l + 1, l)]
            plt += tmplist


    print(N - cnt)

Key2()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
r = []
for _ in range(n):
    r.append(list(map(int,input().split())))
r.sort()
i = 0
while i <= len(r)-2:
    if r[i][0] + r[i][1] > r[i+1][0] - r[i+1][1]:
        r = r[:i+1] + r[i+2:]
    else:
        i += 1
print(len(r))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
dict_area = {}
max_count = 0
for i in range(0, n):
    x, l = map(int, input().split())
    for j in range(x - l + 1, x + l):
        if j in dict_area:
            dict_area[j] += 1
            if max_count < dict_area[j] - 1:
                max_count = dict_area[j] - 1
        else:
            dict_area[j] = 1
print(n - max_count)

Submission status: Time Limit Exceeded

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

    inf = 10**10
    dp = [[inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = -inf
    for i in range(N):
        x, l = XL[i]
        for j in range(N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j < N:
                if dp[i][j] <= x - l:
                    dp[i+1][j+1] = min(dp[i+1][j+1], x + l)
    for i in range(N, -1, -1):
        if dp[-1][i] < 10**10:
            print(i)
            exit()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
xl=sorted([[int(i) for i in input().split()] for _ in range(n)],key=lambda x:x[0])
i=1
while(i<len(xl)):
    if xl[i-1][0]-xl[i-1][1]<xl[i][0]<xl[i-1][0]+xl[i-1][1]:
        xl.remove(xl[i])
    i+=1

print(len(xl))

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline

    N = int(input())
    XL = []
    for i in range(N):
        X, L = map(int, input().split())
        XL.append((X, L))
    print(solve(N, sorted(XL)))

def solve(N, XL):
    if N < 2:
        return N

    X2, L2 = XL[N-1]
    X1, L1 = XL[N-2]

    if X1+L1 <= X2-L2: # とりのぞかなくていい
        return 1 + solve(N-1, XL)

    # N-1 を残して N-2 を取り除く
    a1 = solve(N-2, XL) + 1
    a2 = solve(N-1, XL)
    return max(a1, a2)

main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
xl=sorted([[int(i) for i in input().split()] for _ in range(n)],key=lambda x:x[1])[::-1]
count=[0]*n
for j in range(n):
    for i in range(n):
        if(i!=j and xl[j][0]-xl[j][1] < xl[i][0] < xl[j][0]+xl[j][1] and count[i]==0):
            count[j]=1
            break
print(n-sum(count))

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    A = []
    for _ in range(int(input())):
        x, l = map(int, input().split())
        A.append((x - l, x + l))

    A.sort(key = lambda x : x[1])
    ans = 0
    now = -INF
    for l, r in A:
        if now <= l:
            now = r
            ans += 1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
from operator import itemgetter
N=int(input())
arms=[]
for _ in range(N):
    x,l=map(int,input().split())
    a,b=x-l,x+l
    arms.append([a,b])

arms.sort(key=itemgetter(1))

cnt=1
tmp=arms[0][1]
for arm in arms:
    if arm[0]<tmp: continue
    cnt+=1
    tmp=arm[1]

print(cnt)

Submission status: Accepted

Solution code:
import math , sys
N = int( input() )

X = []
for i in range(N):
    A , B = list(map(int, input().split()))
    X.append([i , A-B , A , A+B])


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

Y = X[0]
Ri = Y[-1]
ans = 1

j=0

for i in range(1,N):
    Y = X[i]
    if Y[1] >= Ri:
        ans+=1
        Ri = Y[-1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n=I()
    lis=[[0,0] for i in range(n)]
    for i in range(n):
        x,l=LI()
        lis[i][0]=x-l
        lis[i][1]=x+l
    lis.sort(key=lambda x:x[1])
    now=-inf
    ans=0
    for i in range(n):
        if lis[i][0]>=now:
            now=lis[i][1]
            ans+=1
    print(ans)
        
        
        
        



        
        
        
        
        
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
arm = []
for _ in range(n):
    x, l = map(int,input().split())
    arm.append([x-l, x+l])
arm.sort(key=lambda x: x[1])
cnt = 0
pr = -float('inf')
for a in arm:
    if pr <= a[0]:
        cnt += 1
        pr = a[1]
print(cnt)

Submission status: Accepted

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

tmpx = arms[0][1]
ans = 1
for i in range(1, len(arms)):
  if tmpx <= arms[i][0]:
    ans += 1
    tmpx = arms[i][1]

print(ans)

Submission status: Accepted

Solution code:

def resolve():
    N = int(input())

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

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

    cnt = 0
    pre = -(1 << 60)
    for (l, r) in P:
        if pre > l:
            continue
        cnt += 1
        pre = r

    print(cnt)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import math
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N = read_int()
    answer = 0
    INF = 10**10
    XL = []
    for i in range(N):
        XL.append(read_ints())
    XL.sort(key=lambda xl: xl[0]+xl[1])
    current = -INF
    for x, l in XL:
        if x-l >= current:
            answer += 1
            current = x+l
    return answer


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

Submission status: Accepted

Solution code:
N = int(input())

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

t = f[0][1]
ans = 1
for i in range(1, N):
    if f[i][0] < t:
        continue
    ans += 1
    t = f[i][1]
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    P = []
    for i in range(N):
        X, L = map(int, input().split())
        S, T = X-L, X+L
        P.append((S, T))
    P.sort(key=lambda x: x[1])

    ans = 0
    r = -float('inf')
    for s, t in P:
        if s >= r:
            ans += 1
            r = t
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

lis.sort()

m = -(10**9+7)
ans = 0

for i in range(n):
    a ,b = lis[i]
    if m <= b:
        ans += 1
        m = a
    
print(ans)

Submission status: Accepted

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

cur = 0
l_cur, r_cur = table[0]
ans = N
for i in range(1,N):
    l,r = table[i]
    if r_cur > l:
        ans -= 1
    else:
        l_cur, r_cur = l,r
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
import queue

def accept_input():
    N = int(input())
    xl = []
    ll = []
    for _ in range(N):
        x,l = map(int,input().split())
        xl.append(x)
        ll.append(l)
    return N,xl,ll


N,xl,ll = accept_input()
tl = [x+l for x,l in zip(xl,ll)]
argtl = np.argsort(tl)
robotl = []
for i in range(N):
    if robotl == []:
        robotl.append(argtl[i])
    else:
        curx = xl[robotl[-1]]
        curl = ll[robotl[-1]]
        if curx+curl <= xl[argtl[i]] - ll[argtl[i]]:
            robotl.append(argtl[i])
print(len(robotl))

Submission status: Accepted

Solution code:
n=int(input())
p=[]
for _ in range(n):
  a,b=map(int,input().split())
  p.append([a-b,a+b])
#print(p)
p.sort(key=lambda x:x[1])
#print(p)
ans=0
cur=(10**9)*-1
for i in range(n):
  if cur<=p[i][0]:
    #print("i:%d残す,cur:%d,p[i][1]:%d,p[i][0]:%d" % (i,cur,p[i][1],p[i][0]))
    ans+=1
    cur=p[i][1]
print(ans)

Submission status: Accepted

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

R=[]
for i in range(N):
    a=max(0,XL[i][0]-XL[i][1])
    b=XL[i][1]+XL[i][0]
    R.append([b,a])
R.sort()

ans=0
con_l=0
for i in range(N):
    if con_l <= R[i][1]:
        ans += 1
        con_l = R[i][0]
print(ans)

Submission status: Accepted

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

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

ans = 0
prev = -float("INF")
for l, r in LR:
    if prev <= l:
        ans += 1
        prev = r

print(ans)

Submission status: Accepted

Solution code:
n=int(input());M=sorted([[x+y,x-y]for x,y in [list(map(int,input().split()))for _ in "_"*n]]);a=1;X=M[0][0]
for x,y in M:X=max(X,x*(b:=X<=y));a+=b
print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

N=intput()
L=[]
for i in range(N):
    x,l=mint() 
    L.append([x+l,l])
L.sort()
tmp = -INF
ans = 0
for l in L:
    if l[0]-2*l[1]>=tmp:
        ans+=1
        tmp=l[0]
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
LR=[]
for i in range(N):
    X,L=map(int,input().split())
    LR.append([X-L,X+L])
LR.sort(key=lambda x:x[1])
nin=LR[0][1]
ans=1
for i in range(1,N):
    if nin<=LR[i][0]:
        nin=LR[i][1]
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

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

XL.sort(key=itemgetter(2))

cnt=1
choice=0

for i in range(n):
    if XL[choice][2]<=XL[i][0]-XL[i][1]:
        choice=i
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    arms = []
    # 区間スケジューリング
    for _ in range(n):
        x, l = input_int_list()
        arms.append((x - l, x + l))
    arms = sorted(arms, key=lambda x: x[1])
    prev_r = -float("inf")
    cnt = 0
    for left, right in arms:
        if prev_r > left:
            continue
        cnt += 1
        prev_r = right

    print(cnt)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

R=sorted(R,key=lambda x:x[1])
ans=n
for i in range(1,n):
  if R[i][0]<R[i-1][1]:
    ans-=1
    R[i][1]=R[i-1][1]
  
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

for i in range(n):
    temp = 0 if a[i][0] - a[i][1] < 0 else a[i][0] - a[i][1]
    a[i][1] = a[i][0]+a[i][1]
    a[i][0] = temp

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

ans = n
right = 0
for j in a:
    if right > j[0]:
        ans -= 1
    else:
        right = j[1]

print(ans)