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: Runtime Error

Solution code:
import math
import pandas as pd
n=int(input())
x=[0]*n
l=[0]*n
start=[0]*n
end=[0]*n

for i in range(0,n):
    [tmp_x,tmp_l]=input().split()
    x[i]=int(tmp_x)
    l[i]=int(tmp_l)


df =  pd.DataFrame({'X':x,'Length':l})
df=df.sort_values(by=['X'])
df = df.reset_index(drop=True)

k =n
check = 0
while check ==0:
    before=[0]*k
    after=[0]*k
    both=[0]*k
    for i in range(0,k):
        if i == 0:
            if df['X'][i]+df['Length'][i]>(df['X'][i+1]-df['Length'][i+1]):
                after[i] = 1
                both[i] = 1
        elif i==k-1:
            if df['X'][i-1]+df['Length'][i-1] > df['X'][i]-df['Length'][i]:
                before[i]=1
                both[i] = 1
        else:
            if df['X'][i-1]+df['Length'][i-1] > df['X'][i]-df['Length'][i]:
                before[i]=1
                both[i]=both[i]+1
            if df['X'][i]+df['Length'][i]>(df['X'][i+1]-df['Length'][i+1]):
                after[i] = 1
                both[i]=both[i]+1
                
    try:
        rm_idx=both.index(2)
        df = df.drop([rm_idx])
        df = df.reset_index(drop=True)
        k = k-1
    except ValueError:
        check =1

print(df.shape[0])

Submission status: Runtime Error

Solution code:
from operator import itemgetter

n = int(input())
xl = sorted([[int(i) for i in input().split()] for i in range(n)],key=itemgetter(1))

ans = n
s = [False for _ in range(10 ** 5 + 1)]
for x,l in xl:
    x -= 1
    L,R = x-l if x-l >= 0 else -1, x+l
    if s[L+1] == False and s[R-1] == False:
        for i in range(L+1,R):
            s[i] = True
    else:
        ans -= 1

print(ans)

Submission status: Runtime Error

Solution code:
import copy

n=int(input())

robot=[] #[0]:x, [1]:l

for i in range(n):
    tmp_x,tmp_l=map(int,input().split())
    robot.append([tmp_x,tmp_l])

robot.sort()
robot2=copy.deepcopy(robot)
count_not_touch=0
list_touch=[]
for i in range(n):
    count=0
    j=i+1
    k=i-1
    if j<n:
        p_flag=True
    else:
        p_flag=False
    if k>=0:        
        m_flag=True
    else:
        m_flag=False
    p_dist=robot[i][0]+robot[i][1]
    m_dist=robot[i][0]-robot[i][1]
    while p_flag or m_flag:
        if p_flag:
            if robot[j][0]<=p_dist:
                count+=1
            else:
                p_flag=False
        if m_flag:
            if robot[k][0]>=m_dist:
                count+=1
            else:
                m_flag=False
        j+=1
        k-=1
        if j==n:
            p_flag=False
        if k==-1:
            m_flag=False
    if count==0:
        robot2.pop(i-count_not_touch)
        count_not_touch+=1
    else:
        list_touch.append(count)

eliminate_num=0
while len(robot2)>0:
    max_index=list_touch.index(max(list_touch))
    max_robot=robot2.pop(max_index)
    list_touch.pop(max_index)
    eliminate_num+=1
    m_range=max_robot[0]-max_robot[1]
    p_range=max_robot[0]+max_robot[1]
    for i in range(len(robot2)):
        if m_range<robot2[i][0] and p_range>robot2[i][0]:
            list_touch[i]-=1
        if p_range<=robot2[i][0]:
            break
    tmp_num=0
    for i in range(len(robot2)):
        if list_touch[i]==0:
            robot2.pop(i-tmp_num)
            list_touch.pop(i-tmp_num)
            tmp_num+=1
            
print(n-eliminate_num)

Submission status: Runtime Error

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

minrx = 10 ** 10
minrx_idx = -1
for i in range(n):
    xx, ll = map(int, input().split(' '))
    rx[xx - ll] = (xx - ll, xx + ll)

rxs = sorted(rx.items(), key=lambda x:x[0])

rxs_ = [i[1] for i in rxs]

max_cnt = 0

for s in range(n):
    if max_cnt >= n - s + 1:
        break

    rxs2 = rxs_[s:]

    now_idx = s
    cnt = 1
    for i, x in enumerate(rxs2):
        if now_idx == i:
            continue
        if rxs2[now_idx][1] > rxs2[i][0]:
            continue
        now_idx += 1
        cnt += 1

    if max_cnt < cnt:
        max_cnt = cnt

print(max_cnt)

Submission status: Runtime Error

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

ranges.sort()

if (len(ranges) == 1):
    print(1)

elif (len(ranges) == 2):
    if (ranges[1][0] < ranges[0][1]):
        print(1)
    else:
        print(2)

else:
    corr = [0 for i in range(n+1)]
    temp = []

    while True:
        
        l = len(ranges)
        for i in range(l-2):
            if (ranges[i+1][0] < ranges[i][1]):
                if (ranges[i+2][0] < ranges[i+1][1]):
                    corr[i+1] = 1
                    ranges[i+1] = ranges[i]
                else:
                    corr[i] = 1
                    if (i != 0):
                        ranges[i] = ranges[i-1]

        if (ranges[l-1][0] < ranges[l-2][1]):
            corr[l-1] = 1

        if (set(corr)) == {0}:
            break
        
        for i in range(l):
            if (corr[i] == 1):
                pass
            else:
                temp.append(ranges[i])

        ranges = list(temp)
        temp = []
        l = len(ranges)

        for i in range(l-1):
            if (ranges[i] == ranges[i+1]):
                if (i == l-2):
                    temp.append(ranges[i])
                pass
            
            else:
                temp.append(ranges[i])
                if (i == l-2):
                    temp.append(ranges[i+1])

        ranges = list(temp)
        temp = []
        corr = [0 for i in range(len(ranges))]

    print(len(corr))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
X = []
L = []
XL = []
for _ in range(N):
    XL.append([int(x) for x in input().split()])
XL = sorted(XL)
for i in XL:
    X.append(i[0])
    L.append(i[1])
import numpy as np
X = np.array(X, np.int64)
L = np.array(L, np.int64)
XL_max = X + L
XL_min = X - L
A = [0] * N
for i in range(N):
    cnt = 0
    left = sorted(XL_max[:i])
    right = sorted(XL_min[i+1:])
    cnt += i - np.searchsorted(left, XL_min[i], side = "right") 
    cnt += np.searchsorted(right, XL_max[i], side = "left")
    A[i] = cnt
cnt = np.array(sorted(A, reverse=True), np.int64)
cnt = np.cumsum(cnt)
if cnt[-1] == 0:
    print(n)
else:
    print(N - (np.searchsorted(cnt, cnt[-1] // 2) + 1))

Submission status: Runtime Error

Solution code:
n = int(input())
xls = [list(map(int, input().split()))for i in range(n)]
xls.sort(key=lambda x:x[0])
flag = 1
ans1 = ans2 = 1
x, l = xls[0]
for i in range(1, n):
    nx, nl = xls[i]
    if nx-nl+1<x+l: continue
    if i==1: flag=0
    ans1 += 1
    x, l = nx, nl

if flag:
    x, l = xls[1]
    for i in range(2, n):
        nx, nl = xls[i]
        if nx-nl+1<x+l: continue
        if i==1: flag=0
        ans2 += 1
        x, l = nx, nl
print(max(ans1, ans2))

Submission status: Runtime Error

Solution code:
n = int(input())
a = [[0,0] for _ in range(n)]

for i in range(n):
    a[i][0],a[i][1]=map(int,input().split())
a.sort()
cnt=0
now=0
temp=1
for i in range(n-1):
    if a[now][0]+a[now][1]>a[now+temp][0]+a[now+temp][1]:
        cnt+=1
        now+=temp
    elif  a[now+temp][0]-a[now+temp][1]<a[now][0]+a[now][1]:
        cnt+=1
        temp+=1
    else:
        now+=temp
        temp=1

print(n-cnt)

Submission status: Runtime Error

Solution code:
from math import ceil

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

X1 = [x-l for x, l in zip(X, L)]
X2 = [x+l for x, l in zip(X, L)]

# 左端でソート
XP = sorted([(x-l, x+l) for x, l in zip(X, L)], key=lambda x: x[0])

X1 = [x[0] for x in XP]
X2 = [x[1] for x in XP]

from bisect import bisect_right
def find(xs, t):
    return bisect_right(t, xs)
    # for i, x in enumerate(xs):
    #     if t <= x:
    #         return i
    # return -1


# 左端indexを指定
i1 = 0
count = 0
while i1 < N:
    right = X2[i1]
    i_pick = i1
    for i2 in range(i1+1, N):
        # より短いなら
        if X2[i2] < right:
            right = X2[i2]
            i_pick = i2

    count += 1
    # right より右で 最小のX1のindex
    i1 = find(X1, right)
    if i1 == -1:
        break

print(count)

Submission status: Runtime Error

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

robots = sorted(robots, key=lambda x: x[0])
# print(robots)
rightest_point = robots[0][0] + robots[0][1] - 1

ans = 0
for i in range(1, N):
    # print("rightest_point: ", rightest_point)
    if robots[i][0]-robots[i][1] + 1 < rightest_point:
        ans += 1
        continue
    else:
        rightest_point = robots[i][0]+robots[i][1] - 1
# print("rightest_point: ", rightest_point)
first = N-ans
# 最初だけは例外

# ２体目から考える
rightest_point = robots[1][0] + robots[1][1] - 1

ans = 0
for i in range(2, N):
    # print("rightest_point: ", rightest_point)
    if robots[i][0]-robots[i][1] + 1 < rightest_point:
        ans += 1
        continue
    else:
        rightest_point = robots[i][0]+robots[i][1] - 1
second = N-ans
if robots[1][0] - robots[1][1] + 1 < robots[0][0] + robots[0][1] - 1:
    second -= 1

print(max(first, second))

Submission status: Runtime Error

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

X = 0
N = 0
co = 0
ans = 0


for i in range(len(lis)):
    h = []
    h = lis[i]
    X = h[0]
    N = h[1]    
    if i == 0:
        co = X+N
        ans += 1
    else:
        if co - X =< 0:
            co = X+N
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

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

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


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

if a < b:
    count += 1



print(count)

Submission status: Runtime Error

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 = []
	for i in range(N):
		X,L = inputMap()
		LL = X-L
		RR = X+L
		tmp.append((LL,RR))

	tmp.sort()
	kabu = 0
	tt = []
	for i,val in enumerate(tmp):
		if i == len(tmp)-1:
			break

		ima_L,ima_R = val
		tugi_L, tugi_R = tmp[i+1]

		if ima_R > tugi_L:
			kabu += 1

		tt.append(kabu)
		kabu = 0

	#print(tmp)
	#print(tt)
	aa = max(tt)
	print(N-aa)


if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
N=int(input())
X=[[0 for j in range(2)] for i in range(N)]


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


X.sort()
n=1
i=0
k=0
flag=0
while(1):
  if X[i][0]+X[i][1]>X[n][0]-X[n][1]:
    n+=1
    flag=0
  else:
    i+=1
    if flag==0:
      k+=1
      flag=1
  if i>=N-1 or n>=N:
    break
    
print(k+1)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

n = int(readline())
xl = [list(map(int, readline().decode('utf-8').split())) for _ in range(n)]
xl = np.array(xl)
xl_ = np.c_[xl[:, 0] - xl[:, 1], xl[:, 0] + xl[:, 1]]
xl_ += abs(xl_.min()) + 1

cnt_array = np.zeros(xl_.max())
cnt = 0
for l, r in xl_:
    if (cnt_array[l:r] > 0).sum() > 0:
        continue
    else:
        cnt_array[l:r] += 1
        cnt += 1

cnt_ = 0
for l, r in xl_[::-1]:
    if (cnt_array[l:r] > 0).sum() > 0:
        continue
    else:
        cnt_array[l:r] += 1
        cnt_ += 1

print(max(cnt, cnt_))

Submission status: Runtime Error

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

cnt = 0
for i in range(len(List)-2):
  migi = int(List[i-cnt][0] + List[i-cnt][1])
  hidari = int(List[i+2-cnt][0] - List[i+2-cnt][1])
  if migi > hidari:
    List.pop(i)
    cnt = cnt + 1

cnt = 0
for i in range(len(List)-2):
  if i > 1:
    migi = int(List[i-2-cnt][0] + List[i-2-cnt][1])
    hidari = int(List[i-cnt][0] - List[i-cnt][1])
    if migi > hidari:
      List.pop(i)
      cnt = cnt + 1

cnt = 0
for i in range(len(List)-1):
  if i > 0:
    hidari_1 = int(List[i-cnt][0] - List[i-cnt][1])
    migi_1 = int(List[i-1-cnt][0] + List[i-1-cnt][1])

    migi_2 = int(List[i-cnt][0] + List[i-cnt][1])
    hidari_2 = int(List[i+1-cnt][0] - List[i+1-cnt][1])
    
    if hidari_1 < migi_1 and migi_2 > hidari_2:
      List.pop(i)
      cnt = cnt + 1

cnt = 0
for i in range(len(List)-1):
  hidari = int(List[i+1-cnt][0] - List[i+1-cnt][1])
  migi = int(List[i-cnt][0] + List[i-cnt][1])
  if hidari < migi:
    List.pop(i)
    cnt = cnt + 1
      
length = len(List)
print(length)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

n = int(readline())
xl = [list(map(int, readline().decode('utf-8').split())) for _ in range(n)]
xl = np.array(xl)
xl_ = np.c_[xl[:, 0] - xl[:, 1], xl[:, 0] + xl[:, 1]]
xl_ += abs(xl_.min())

cnt_array = np.zeros(xl_.max())
cnt = 0
for l, r in xl_:
    if (cnt_array[l:r] > 0).sum() > 0:
        continue
    else:
        cnt_array[l:r] += 1
        cnt += 1

cnt_ = 0
for l, r in xl_[::-1]:
    if (cnt_array[l:r] > 0).sum() > 0:
        continue
    else:
        cnt_array[l:r] += 1
        cnt_ += 1

print(max(cnt, cnt_))

Submission status: Runtime Error

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

minrx = 10 ** 10
minrx_idx = -1
for i in range(n):
    xx, ll = map(int, input().split(' '))
    rx[xx - ll] = (xx - ll, xx + ll)

rxs = sorted(rx.items(), key=lambda x:x[0])

rxs2 = [i[1] for i in rxs]

now_idx = 0
cnt1 = 1
for i, x in enumerate(rxs2):
    if now_idx == i:
        continue
    if rxs2[now_idx][1] > rxs2[i][0]:
        continue
    now_idx += 1
    cnt1 += 1

print(cnt)

rxs3 = rxs2[1:]

now_idx = 0
cnt2 = 1
for i, x in enumerate(rxs3):
    if now_idx == i:
        continue
    if rxs3[now_idx][1] > rxs3[i][0]:
        continue
    now_idx += 1
    cnt2 += 1

print(max(cnt1, cnt2))

Submission status: Runtime Error

Solution code:
# N個のロボット
N = int(input())

# 1個前
rem = 0
bx = 0
bl = 0
for i in range(N):
    x,l = map(int, input().split())
    
    #print(x,l, bx,bl)
    
    # 1個前と重複確認
    if i != 0:
        rn = list(range(x+l-1, x-l, -1 ))
        before = list(range(bx+bl-1, bx-bl, -1 ))
        #print(rn)
        #print(before)
        if len(set(rn) & set(before)) != 0:
            #print("rem")
            rem +=1
            # 1個前は変えないで次へ
            continue
        else:
            # 1個前を更新
            bx = x
            bl = l
    else:
        # 1個前を更新
        bx = x
        bl = l
    

print(N-rem)

Submission status: Runtime Error

Solution code:
n = int(input())
xl = []
for i in range(n):
    x1, l1 = map(int, input().split())
    xl.append([x1, x1 + l1, 2 * l1])
xl.sort()
ans = n
for i in range(n - 1):
    if xl[i][1] > xl[i + 1][0]:
        if xl[i][2] >= xl[i + 1][2]:
            ans -= 1
        else:
            ans -= 1
            xl[i + 1][0] = [i][0]
            xl[i + 1][1] = [i][1]
            xl[i + 1][2] = [i][2]

print(ans)

Submission status: Runtime Error

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

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

ans=0
now=0

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

print(n-ans)

Submission status: Runtime Error

Solution code:
N=int(input())
X=[[0 for j in range(2)] for i in range(N)]
Y=[[0 for j in range(N)] for i in range(N)]

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


X.sort()
n=1
i=0
k=0
flag=0
while(1):
  if X[i][0]+X[i][1]>X[n][0]-X[n][1]:
    n+=1
    flag=0
  else:
    i+=1
    if flag==0:
      k+=1
      flag=1
  if i>=N-1 or n>=N:
    break
    
print(k+1)

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

Submission status: Runtime Error

Solution code:
N=int(input())
if N==1:
  print(1)
  exit()
XL=[list(map(int,input().split())) for i in range(N)]
XL.sort(key=lambda x:x[0]-x[1])
i=0
normv=0
rmv=0
while True:
  if XL[i][0]+XL[i][1]<=XL[i+1][0]-XL[i+1][1]:
    i+=1
    normv+=1
  else:
    if XL[i]>XL[i+1]:
      XL.pop(i)
      rmv+=1
    elif XL[i][0]+XL[i][1] < XL[i+1][0]+XL[i+1][1]:
      XL.pop(i+1)
      i+=1
      normv+=1
      rmv+=1
    else:
      XL.pop(i)
      rmv+=1
  if rmv+normv==N-1:
    break
if len(XL)<2:
  pass
elif XL[-1][0]-XL[-1][0]<XL[-2][0]-XL[-2][0]:
  rmv+=1
else:
  normv+=1
print(len(XL))

Submission status: Runtime Error

Solution code:
n=int(input())
l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append([a-b+1,i])
    l.append([a+b,i])
l.sort()
re=0
c=[0]*n
f=0
mf
di=set([])
for i in range(n*2):
    p=l[i][0]
    j=l[i][1]
    if c[j]==0:
        c[j]+=1
        f+=1
        mf=max(mf,f)
        #di.add(j)
    else:
        f-=1 
        if f==0:
            re+=mf-1
        mf=0
            
        #f=0
print(n-re)

Submission status: Runtime Error

Solution code:
n=int(input())
x=[]
for i in range(n):
    xi=list(map(int, input().split()))
    x.append(xi)
x_new=sorted(x) #これで、座標順にxとlを対応させて並べ替えできた
ans=n
#xi-liより大、xi+liより小の範囲に何個のロボットがいるかをそれぞれ調べたい
buf=[0]*n
for i in range(n):
    c=0
    for j in range(n):
        if (x[i][0]-x[i][1])<x[j][0]<(x[i][0]+x[i][1]):
            c+=1
    buf[i]=c-1
#両隣のかぶりの数と比較して、大きかったらそれを取り除く作業をする
if n>2:
    for i in range(1,n-1):
        if buf[i]!=0 and buf[i-1]<=buf[i] and buf[i+1]<=buf[i]:
            ans-=1
elif buf[0]<=buf[1]:
    ans-=1
print(ans)

Submission status: Runtime Error

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

n = int(input())
robo = []
for i in range(n):
    x, y = map(int, input().split())
    if x - y > 0:
        r = x - y
    else:
        r = 0
    if x + y - 2 < n:
        l = x + y - 2
    else:
        l = n - 1
    robo.append([r, l])

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

check = [0] * n
ans = 0

for i in robo:
    for j in i:
        check[j] = 1
        
    ans += 1
    
    k = 0
    for s in check:
        k += s
    if k == n:
        break
    
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
rlist =[[]]*N
for i in range(N):
  rlist[i] = list(map(int, input().split()))
rlist.sort()
rangelist = [[0]]*(rlist[N-1][0]+rlist[N-1][1])
nrobo = 1
for k in range(rlist[0][0]+rlist[0][1]):
  rangelist[k] = 1

for j in range(1,N):
  judge = True
  for m in range(rlist[j][0]-rlist[j][1],rlist[j][0]+rlist[j][1]):
    if rangelist[m] == 1:
      judge = False
  if judge:
    nrobo += 1
    for l in range(rlist[j][0]-rlist[j][1],rlist[j][0]+rlist[j][1]):
      rangelist[l] = 1
print(nrobo)

Submission status: Runtime Error

Solution code:
n=int(input())
temp = [input() for _ in range(n)]
x = [0]*n
l = [0]*n
for i in range(n):
  x[i],l[i] = map(int, temp[i].split())
temp2 = zip(x,l)
x,l = zip(*sorted(temp2))
x = list(x)
l = list(l)
result=n
for j in range(n-1):
  if x[j]+l[j]>x[j+1]-l[j+1]:
    if j!=(n-2) :
      if x[j+1]+l[j+1]>x[j+2]-l[j+2]:
        result-=1
        x[j+1]=0
        l[j+1]=0
      else:
        result-=1
        x[j]=0
        j[j]=0
    else:
      result-=1
      x[j]=0
      j[j]=0
print(result)

Submission status: Runtime Error

Solution code:
n= int(raw_input())
d = []
for i in range(n):

	r, l= raw_input().split(" ")
	d.append([int(r),int(l)])
    
s = []
s = sorted(d, key=lambda tup: tup[0])

t=0
popped = 0
for i in s:
  x_current = s[t][0]
  x_next = s[t+1][0]
  l_current = s[t][1]
  l_next = s[t+1][1]
  
  if (x_current + l_current) > (x_next - l_next):
    # current interserts with next
    # pop next
    popped += 1
    t+=1
  t +=1
  if t >= len(s)-1:
    break

print(len(s)-popped)

Submission status: Runtime Error

Solution code:
N = gets.chomp.to_i
# xl = []
ll = []

ans = 0

h = Hash.new(0)

N.times do |i|
  x, l = gets.chomp.split.map(&:to_i)
  h[x-l+1] = +1
  h[x+l] = -1
  ll << [x-l+1,x+l-1]
end

ll.sort_by!{|x| [x[0],x[1]] }


N.times do |i|
  next if i == 0
  if ll[i][0] <= ll[i-1][1]
    ans += 1
  end

end


p N-ans

Submission status: Runtime Error

Solution code:
n = int(input())
x = [0]*n
l = [0]*n
li = []
for i in range(n):
  x[i], l[i] = list(map(int, input().split()))
  li.append([x[i], l[i]])
li.sort()
count = 0
if n == 2:
  if (li[0][0] + li[0][1]) >= (li[1][0] - li[1][1]):
    print(1)
  else:
    print(n)
else:
  for i in range(n):
    if i == n-1:
      continue
    else:
      top = (li[i][0] + li[i][1]) >= (li[i+1][0] - li[i+1][1])  
      if top == False:
        i -= 1
        del li[i+1]

  print(len(li))

Submission status: Runtime Error

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

ranges.sort()

if (len(ranges) == 1):
    print(1)

elif (len(ranges) == 2):
    if (ranges[1][0] < ranges[0][1]):
        print(1)
    else:
        print(2)

else:
    corr = [0 for i in range(n+1)]
    temp = []

    while True:
        
        l = len(ranges)
        for i in range(l-2):
            if (ranges[i+1][0] < ranges[i][1]):
                if (ranges[i+2][0] < ranges[i+1][1]):
                    corr[i+1] = 1
                    ranges[i+1] = ranges[i]
                else:
                    corr[i] = 1
                    if (i != 0):
                        ranges[i] = ranges[i-1]

        if (ranges[l-1][0] < ranges[l-2][1]):
            corr[l-1] = 1

        if (set(corr)) == {0}:
            break
        
        for i in range(l):
            if (corr[i] == 1):
                pass
            else:
                temp.append(ranges[i])

        ranges = list(temp)
        temp = []
        corr = [0 for i in range(len(ranges))]

    print(len(corr))

Submission status: Runtime Error

Solution code:
n=int(input())
temp = [input() for _ in range(n)]
x = [0]*n
l = [0]*n
for i in range(n):
  x[i],l[i] = map(int, temp[i].split())
temp2 = zip(x,l)
x,l = zip(*sorted(temp2))
x = list(x)
l = list(l)
result=n
for j in range(n-1):
  if x[j]+l[j]>x[j+1]-l[j+1]:
    if x[j+1]+l[j+1]>x[j+2]-l[j+2]:
      result-=1
      x[j+1]=0
      l[j+1]=0
    else:
      result-=1
      x[j]=0
      j[j]=0
print(result)

Submission status: Runtime Error

Solution code:
n = int(input())
x = [0]*n
l = [0]*n
li = []
for i in range(n):
  x[i], l[i] = list(map(int, input().split()))
  li.append([x[i], l[i]])
li.sort()
count = 0
if n == 2:
  if (li[0][0] + li[0][1]) >= (li[1][0] - li[1][1]):
    print(1)
  else:
    print(n)
else:
  for i in range(n):
    if i == n-1:
      continue
    else:
      top = (li[i][0] + li[i][1]) >= (li[i+1][0] - li[i+1][1])  
      if top == False:
        del li[i+1]

  print(len(li))

Submission status: Runtime Error

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

x_l.sort()

for i in range(1,N):
  if (x_l[i-1][0] + x_l[i-1][1]) > (x_l[i][0] - x_l[i][1]):
    del x_l[i]

print(len(x_l))

Submission status: Runtime Error

Solution code:
N = int(input())
X = []
L = []
for i in range(N):
  temp = list(map(int, input().split()))
  X.append(temp[0])
  L.append(temp[1])
  
num = 0
maxlength = max(X) + max(L)
area = [0] * maxlength
for i in range(N):
  if(L[i]==1):
    if(area[X[i]]==0):
      area[X[i]]=1
    else:
      num += 1
  for j in range(1,2*L[i]-1):
    if(X[i]-L[i]+j>=0):
      if(area[X[i]-L[i]+j]==0):
        area[X[i]-L[i]+j]=1
      else:
        num += 1
        break
print(N-num)

Submission status: Runtime Error

Solution code:
n=int(input())
robots = []
for _ in range(n):
    x,arm = map(int, input().split())
    robots.append([num for num in range(x-arm,x+arm,1)])
double=[set() for _ in range(len(robots))]
for i in range(len(robots)):
    for j in range(len(robots)):
        if i!=j and set(robots[i]) & set(robots[j]):
             double[i].add(j)
#print(double)
count=0
#print(max([len(s) for s in double]))
while isdouble(double):
    m=max([len(s) for s in double])
    for i,s in enumerate(double):
        if len(s)==m:
            break
    double[i]=set()
    for j,s in enumerate(double):
        if i in s:
            #print('>>',s,set([i]))
            double[j] = s-set([i])
            #print('>>',double)
    count+=1
print(len(robots)-count)

Submission status: Runtime Error

Solution code:
N=int(input())
XL=[list(map(int,input().split())) for i in range(N)]
XL.sort(key=lambda x:x[0]-x[1])
i=0
normv=0
rmv=0
while True:
  if XL[i][0]+XL[i][1]<=XL[i+1][0]-XL[i+1][1]:
    i+=1
    normv+=1
  else:
    if XL[i]>XL[i+1]:
      XL.pop(i)
      rmv+=1
    elif XL[i][0]+XL[i][1] < XL[i+1][0]+XL[i+1][1]:
      XL.pop(i+1)
      i+=1
      normv+=1
      rmv+=1
    else:
      XL.pop(i)
      rmv+=1
  if rmv+normv==N-1:
    break
if len(XL)<2:
  pass
elif XL[-1][0]-XL[-1][0]<XL[-2][0]-XL[-2][0]:
  rmv+=1
else:
  normv+=1
print(len(XL))

Submission status: Runtime Error

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

List.sort()
cnt = 0
for i in range(len(List)-2):
  migi = List[i-cnt][0] + List[i-cnt][1]
  hidari = List[i+2-cnt][0] - List[i+2-cnt][1]
  
  if migi > hidari:
    List.pop(i)
    cnt = cnt + 1

cnt = 0
for i in range(len(List)-1):
  if i > 0:
    hidari_1 = List[i-cnt][0] - List[i-cnt][1]
    migi_1 = List[i-1-cnt][0] + List[i-1-cnt][1]

    migi_2 = List[i-cnt][0] + List[i-cnt][1]
    hidari_2 = List[i+1-cnt][0] - List[i+1-cnt][1]
    
    if hidari_1 < migi_1 and migi_2 > hidari_2:
      List.pop(i)
      cnt = cnt + 1
cnt = 0
for i in range(len(List)-1):
  hidari = List[i+1-cnt][0] - List[i+1-cnt][1]
  migi = List[i-cnt][0] + List[i-cnt][1]
  if hidari < migi:
    List.pop(i)
    cnt = cnt + 1
      
length = len(List)
print(length)

Submission status: Runtime Error

Solution code:
N = int(input())
arm = []
for i in range(N):
    x,l=[int(i) for i in input().split()]
    arm.append([x-l,x+l])
i = 0
j = 1
while True:
    if arm[i][1]>arm[j][0] and arm[i][0]<arm[j][0]:
        arm.pop(j)
    elif arm[i][0]<arm[j][1] and arm[i][0]>arm[j][0]:
        arm.pop(j)
    elif arm[i][1]<arm[j][1] and arm[i][0]>arm[j][0]:
        arm.pop(j)
    else:
        j+=1
    
    if j>=len(arm):
        i+=1
        j=i+1
        if i>=len(arm)-1:
            break
print(len(arm))

Submission status: Runtime Error

Solution code:
def find_dex(list,dex):
    for j in range(len(list)):
        if list[j][0] == dex:
            return j
    return 0
n = int(input())
a = np.zeros((10**9))
d = []
left = []
right = []
for i in range(n):
    x,l = map(int, input().split())
    # num , left , right
    left.append([i,x-l+1,x+l-1])
    right.append([i,x-l+1,x+l-1])

left.sort(key=lambda x:x[1],reverse=False)
right.sort(key=lambda x:x[2],reverse=False)

flag = True
p = 10**9 + 1
ans = 0
while len(left) > 0:
    if flag:
        i,l,r = left.pop(-1)
        right.pop(find_dex(right,i))
        flag = False
        if r >= p:
            ans += 1
        p = l

    else:
        i,l,r = right.pop(-1)
        left.pop(find_dex(left,i))
        flag = True
        if r >= p:
            ans += 1
        p = l

    #print(i,l,r)
    #print(left)
    #print(right)

print(n-ans)

Submission status: Runtime Error

Solution code:
# N個のロボット
N = int(input())

X = []
L = []
for n in range(N):
    x,l = map(int, input().split())
    X.append(x)
    L.append(l)
    
rem = 0
flg = False
for i in range(0, N-1):
    # アームの行動範囲
    if flg == True:
        flg = False
        continue
    if i !=0:
        rn = list(range(X[i]+L[i]-1, X[i]-L[i], -1 ))
        before = list(range(X[i-1]+L[i-1]-1, X[i-1]-L[i-1], -1 ))
        next = list(range(X[i+1]+L[i+1]-1, X[i+1]-L[i+1], -1 ))
        #print(rn)
        #print(before)
        #print(next)
        
        # アームの可動範囲が被る
        if len(set(rn) & set(before)) != 0 or len(set(rn) & set(next)) != 0:
            rem +=1
            flg = True
    else:
        rn = list(range(X[i]+L[i]-1, X[i]-L[i], -1 ))
        next = list(range(X[i+1]+L[i+1]-1, X[i+1]-L[i+1], -1 ))
        #print(rn)
        #print(next)
        # アームの可動範囲が被る
        if len(set(rn) & set(next)) != 0:
            rem +=1
            flg = True

print(N-rem)