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: Wrong Answer

Solution code:
# coding: utf-8
import math

def findTwoDup(positions, arms, N):
    indices = []
    removed = False
    for i in range(1, N-1):
        left_distance_between = abs(positions[i] - positions[i-1])
        right_distance_between = abs(positions[i] - positions[i+1])
        left_touched = left_distance_between < (arms[i] + arms[i-1])
        right_touched = right_distance_between < (arms[i] + arms[i+1])
        if left_touched and right_touched:
            indices.append(int(i))
            removed = True
    if removed:
        indices.append(-1)
    return indices

def findDup(positions, arms, N):
    indices = []
    removed = False
    for i in range(N-1):
        right_distance_between = abs(positions[i] - positions[i+1])
        right_touched = right_distance_between < (arms[i] + arms[i+1])
        if right_touched:
            indices.append(int(i))
            removed = True
    if removed:
        indices.append(-1)
    return indices



positions = []
arms = []
N = int(input())
for i in range(N):
    a, b = (int(n) for n in input().split())
    positions.append(a)
    arms.append(b)
last_index = -1
while last_index == -1:
    two_dup_indices = findTwoDup(positions, arms, len(arms))
    if len(two_dup_indices) == 0 or two_dup_indices[-1] != -1:
        break
    else:
        two_dup_indices.pop(-1)
    while len(two_dup_indices) != 0:
        removed_index = two_dup_indices.pop(-1)
        positions.pop(removed_index)
        arms.pop(removed_index)

last_index = -1
while last_index == -1:
    dup_indices = findDup(positions, arms, len(arms))
    if len(dup_indices) == 0 or dup_indices[-1] != -1:
        break
    else:
        dup_indices.pop(-1)
    while len(dup_indices) != 0:
        removed_index = dup_indices.pop(-1)
        positions.pop(removed_index)
        arms.pop(removed_index)
print(len(arms))

Submission status: Wrong Answer

Solution code:
from math import ceil
from bisect import bisect_right as br
from bisect import bisect_left as bl
import heapq


def main():
    N = int(input())
    XL  = [list(map(int,input().split())) for _ in range(N)]
    X = []
    L = {}

    for x,l in XL:
        L[x] = l
    R = []
    for i in range(1,N - 1):
        x,l = XL[i]
        if x + l <= XL[i + 1][0] -XL[i + 1][1] and x - l >= XL[i + 1][0] + XL[i + 1][1]:
            R.append(x)
    for j in range(N):
        x,l = XL[j]
        if len(R) == 0:
            R.append(x)
        point = br(R,x)
        if point == len(R):
            xx = R[-1]
            ll = L[xx]
            if xx + ll <= x - l:
                R.append(xx)
        elif point == 0:
            xx = R[0]
            ll = L[xx]
            if xx - ll >= x + l:
                R.append(xx)
        else:
            if x + l <= XL[j + 1][0] -XL[j + 1][1] and x - l >= XL[j + 1][0] + XL[j + 1][1]:
                R.append(XL[j][0])
            
    print(len(R))
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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][0] + List[i][1])
  hidari = int(List[i+2][0] - List[i+2][1])
  if migi > hidari:
    List[i][0] = -10000000000
    List[i][1] = 0
    cnt = cnt + 1
List.sort()
length = len(List)-1
for i in range(len(List)-2):
  if i > 1:
    migi = int(List[length-(i+2)][0] + List[length-(i+2)][1])
    hidari = int(List[length-i][0] - List[length-i][1])
    if migi > hidari:
      List[length-i][0] = 90000000000
      List[length-i][1] = 0
      cnt = cnt + 1
List.sort()
for i in range(len(List)-1):
  if i > 0:
    hidari_1 = int(List[i][0] - List[i][1])
    migi_1 = int(List[i-1][0] + List[i-1][1])

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

print(N-cnt)

Submission status: Wrong Answer

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

print(n-cnt)

Submission status: Wrong Answer

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

R = [[X[n] - L[n], X[n] + L[n]] for n in range(N)]

R = sorted(R)
#print(R)

from bisect import bisect_right

rr = []

#print(rr)
s = []
sub = 0
for r in R:
    sIdx = bisect_right(s, r[0])
    eIdx = bisect_right(s, r[1])

    if sIdx == len(s) and eIdx == len(s):
        s.append(r[0])
        s.append(r[1])

    else:
        sub += 1
#print(s)
print(N - sub)

Submission status: Wrong Answer

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

ans = N
l, r = 0, 1
while r < N:
    x1, l1 = a[l]
    x2, l2 = a[r]

    if (x1+l1) > (x2-l2):
        if (x1+l1) > (x2+l2):
            l += 1
            r += 1
        else:
            r += 1
        ans -= 1
    else:
        l += 1
        r += 1

print(ans)

Submission status: Wrong Answer

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

import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
LR = []
for i in range(N):
    x, l = MAP()
    LR.append((x-l+1, x+l-1))

LR.sort(key=itemgetter(0))
LR.sort(key=itemgetter(1))
cur = -INF
cnt = 0
for l, r in LR:
    if cur < l:
        cur = r
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N = int(input())
arms = []
for i in range(N):
    xl = [int(i) for i in  input().split()]
    xl[1] -= 1
    arms.append([xl[0] - xl[1], xl[0] + xl[1]])
arms = sorted(arms, key=itemgetter(1))
rm = 0
prev_arm = 0
for i in range(1, N):
    if arms[prev_arm][0] > arms[i][1] or arms[prev_arm][1] < arms[i][0]:
        prev_arm = i
    else:
        rm += 1
print(N - rm)

Submission status: Wrong Answer

Solution code:
import sys

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

if(N==1):
  print("1")
  sys.exit()

rightX=robotList[0][0]+robotList[0][1]
leftX=0
count=0


for i in range(N-1):
  leftX=robotList[i+1][0]-robotList[i+1][1]
  if(rightX<=leftX):#共通範囲を持たない
    rightX=robotList[i+1][0]+robotList[i+1][1]
  else:#共通範囲を持つ
    count+=1
    if(i!=N-2):
      if(robotList[i+2][0]+robotList[i+2][1]<=rightX):
        rightX=robotList[i+1][0]+robotList[i+1][1]
    
print(N-count)

Submission status: Wrong Answer

Solution code:
N = int(input())
y = [[None] * N for _ in range(N)]
L = [0]*N
d = {}
max = 0
del_count = 0
first = 0
for i in range(N):
  y[i]= list(map(int,list(input().split())))
count = 0
x = sorted(y)
for z in x:
  if count == 0:
    max = z[0] + z[1]
  elif max > z[0] - z[1]:
    del_count +=1
  else:
    max = z[0] + z[1]
print(N-del_count)

Submission status: Wrong Answer

Solution code:
N = int(input())
R=[list(map(int,input().split())) for i in range(N)]
bf = 0
ans = N
R = sorted(R)
for i in range(N-1):
  
  if R[bf][0] + R[bf][1] - 1 >= R[i+1][0] - R[i+1][1] + 1:
    bf = i
    ans -= 1
    for j in range(i)[::-1]:
      if R[j][0] + R[j][1] - 1 >= R[i+1][0] - R[i+1][1] + 1:
        ans -= 1
      else:
        break
  else:
    bf = i+1
  if ans == 0:
    break
  
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
XL = []
for i in range(N):
  tmp = list(map(int, input().split()))
  XL.append(tmp)

XL.sort()
s = [1]*N
for i in range(N-2):
  if(s[i] == 1):
    #print(i)
    if(XL[i][0] + XL[i][1] > XL[i+1][0]- XL[i+1][1]):
      if(XL[i][0] + XL[i][1] > XL[i+2][0]- XL[i+2][1]):
        s[i] = 0
      elif(XL[i+1][0] + XL[i+1][1] > XL[i+2][0]- XL[i+2][1]):
        s[i+1] = 0

total = sum(s)
if(s[N-2] == 1):
  if(XL[N-2][0] + XL[N-2][1] > XL[N-1][0]- XL[N-1][1]):
    print(total-1)
  else:
    print(total)
else:
  print(total)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N = int(input())
robot_list = []

for i in range(N):
    robot_list.append(list(map(int, input().split())))
    robot_list[i] = (robot_list[i][0] - robot_list[i][1] + 1, robot_list[i][0] + robot_list[i][1] - 1, robot_list[i][0], robot_list[i][1])

sort_robot_list = sorted(robot_list, key=itemgetter(2))

minus_count = 0
for i in range(1, len(sort_robot_list), 2):
    if i < N - 1:
        if sort_robot_list[i - 1][1] >= sort_robot_list[i][0] or sort_robot_list[i + 1][0] <= sort_robot_list[i][1]:
            minus_count += 1
    else:
        if sort_robot_list[i - 1][1] >= sort_robot_list[i][0]:
            minus_count += 1
print(len(sort_robot_list) - minus_count)

Submission status: Wrong Answer

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

d = []

for xl in X_L:
  d.append([xl[0] - xl[1], 1])
  d.append([xl[0] + xl[1] - 1, -1])

d.sort(key=lambda x: x[0])
#print(d)
ans = 0
tmp = 0
kasanari =[]
for d in d:

  tmp += d[1]
  kasanari.append(tmp)
  if tmp > 1:
    ans += tmp - 1
#print(kasanari)
print(N - ans)

Submission status: Wrong Answer

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

for i in range(n):
	x, l = map(int, input().split())
	a = x - l
	b = x + l
	is_kaburi=False
	for y in range(int(len(x_l)/2)):
		a_2 = x_l[(y*2)]
		b_2 = x_l[(y*2)+1]
		if a_2 <= a and b_2 >= a:
			is_kaburi=True
			break
		if a_2 <= b and b_2 >= b:
			is_kaburi=True
			break
	if is_kaburi == False:
		x_l.append(a)
		x_l.append(b)

if len(x_l)!=0:
	print(int(len(x_l)/2))
else:
	print(0)

Submission status: Wrong Answer

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
xl = []
for i in range(n):
    xx,ll = inm()
    xl.append((xx,ll))
xl.sort()
x = [z[0] for z in xl]
l = [z[1] for z in xl]

#ddprint(x)
#ddprint(l)

ok = [1]*n
for i in range(n):
    if i<n-1 and x[i]+l[i] >= x[i+1]+l[i+1] or \
       i>0 and ok[i-1]==1 and x[i]-l[i] <= x[i-1]-l[i-1]:
       ok[i] = 0

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

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

print(sum(ok))

Submission status: Wrong Answer

Solution code:
n = int(input())
xs = []
scope = {}
for _ in range(n):
    x, l = map(int, input().split())
    xs.append(x)
    scope[x] = [x-l, x+l]
    
xs.sort()
ans = n
end = scope[xs[0]][1]
for i in xs[1:]:
    start = scope[i][0]
    if end > start:
        ans -= 1
        end = start
print(ans)

Submission status: Wrong Answer

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, x-l-1, -(max(x,l) )))
        before = list(range(bx+bl, bx-bl-1, -(max(bx,bl) )))
        #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: Wrong Answer

Solution code:
def main():
    N = int(input())
    li = []
    for _ in range(N):
        a,b = [int(n) for n in input().split()]
        li.append([a-b+1,a+b-1])
    # li.sort(key=lambda x:x[0])
    # last = (-10**10,-10**10)
    res = N
    # for a in li:
        
    #     if last[1] > a[1]:
    #         last = a
    #         res-=1
    #     elif last[1] > a[0]:
    #         last = last
    #         res-=1
    #     else:
    #         last = a
    li.sort(key=lambda x:-x[0])
    last = (10**10,10**10)
    for a in li:
        
        if a[1] > last[0]:
            last = last
            res-=1
        else:
            last=a
    print(res)

main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

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

xl = sorted(xl, key=itemgetter(0))

ans = 0
prev_right = -float("inf")
for i in range(n):
    now_left = xl[i][0]
    now_right = xl[i][2]
    if prev_right > now_left:
        if i < n - 1 and now_right > xl[i + 1][0]:
            ans += 1
        else:
            ans += 1
            prev_right = now_right
    else:
        prev_right = now_right

print(n - ans)

Submission status: Wrong Answer

Solution code:
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def my_round(a,dig=0):
    p = 10 ** dig
    return (a * p * 2 + 1) // 2 / p

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b): #最小公倍数
    return a/gcd(a,b)*b

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    n = int(input())
    xl = []
    for i in range(n):
        a,b = map(int,input().split())
        xl.append([a,b])
    xl.sort()
    ans = 1
    width = xl[0]
    count = 0
    for i in range(1,n):
        if max(xl[i][0] - xl[i][1] + 1,0) < width[0] + width[1]:
            count += 1
            if count == 2:
                width = xl[i]
                ans += 2
                count = 0
        else:
            ans += 1
            count = 0
            width = xl[i]
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input().strip())
xl = []
for i in range(n):
    xl.append(list(map(int, input().split())))
xl.sort()
if n == 1:
    print(0)
    exit()
if n == 2:
    if (xl[1][0] - xl[1][1]) < (xl[0][0] + xl[0][1]):
        print(1)
        exit()
    else:
        print(0)
        exit()
ans = 0
while 3 <= len(xl):
    reps = [0] * len(xl)
    for i in range(len(xl) - 2):
        cnt = 0
        if (xl[i + 1][0] - xl[i + 1][1]) < (xl[i][0] + xl[i][1]):
            cnt += 1
        if (xl[i + 2][0] - xl[i + 2][1]) < (xl[i + 1][0] + xl[i + 1][1]):
            cnt += 1
        reps[i + 1] = cnt
    tmp = []
    add = 0
    for i in range(len(xl)):
        if reps[i] < 2:
            tmp.append(xl[i])
        else:
            add += 1
    if add == 0:
        break
    else:
        ans += add
    xl = tmp

for i in range(len(xl) - 1):
    if (xl[i + 1][0] - xl[i + 1][1]) < (xl[i][0] + xl[i][1]):
        ans += 1
print(n - ans)

Submission status: Wrong Answer

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

j = 0
while j < len(x)-1:
    if x[j][0]+x[j][1] > x[j+1][0]-x[j+1][1]:
        n -= 1
        j += 2
        continue
    j += 1

print(count)

Submission status: Wrong Answer

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

x = sorted(x_org, key=lambda z: int(z[0]))

removed = 0
for i in range(1, n):
    if int(x[i][0]) < int(x[i][1]):
        before = 0
    else:
        before = int(x[i][0]) - int(x[i][1])
    if (int(x[i-1][0]) + int(x[i-1][1])) > 1000000000:
        after = 1000000000
    else:
        after = int(x[i-1][0]) + int(x[i-1][1]) 
    if before < after:
        removed += 1
        x[i] = x[i-1]

print(n - removed)

Submission status: Wrong Answer

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

prv_idx = 0
idx = 1
removed_num = 0
while idx <= N-1:
    if ranges[idx][0] <= ranges[prv_idx][1]:
        removed_num += 1
        if ranges[idx][1] < ranges[prv_idx][1]:
            prv_idx = idx
        idx += 2
    else:
        idx += 1
        prv_idx += 1
    if N - 1 < idx:
        break
print(N - removed_num)

Submission status: Wrong Answer

Solution code:
def delete_max_line(arr):
    max_i=0
    M=0
    i=0

    for a in arr:
        s=sum(a)
        if M<s:
            M=s
            max_i=i
        i+=1

    arr.pop(max_i)
    for a in arr:
        a.pop(max_i)

    return M

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

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

XL.sort()

attach=[[0]*N for i in range(N) ]

right=[xl[0]+xl[1] for xl in XL]
left=[xl[0]-xl[1] for xl in XL]

for i in range(N-1):
    for j in range(i+1,N):
        if right[i]>left[j]:
            attach[i][j]=1
            attach[j][i]=1

print(attach)

ans=0
while True:
    judge=delete_max_line(attach)
    if judge==0:
        break
    ans+=1

print(N-ans)

Submission status: Wrong Answer

Solution code:
def search_touched_idx(i, val, l):
    ret = []
    base_idx = val[0]
    arm_length = val[1]
    minus_idx = base_idx - arm_length
    plus_idx = base_idx + arm_length
    for n in range(i-1, 0, -1):
        if minus_idx <= l[n][0]:
            ret.append(n)
        else:
            break

    for n in range(i+1, len(l)):
        if l[n][0] <= plus_idx:
            ret.append(n)
        else:
            break

    return ret

N = int(input().rstrip())
l = []
for i in range(N):
    l.append(list(map(int ,input().rstrip().split())))
# print(l)

touch = []  # stored touched idx to list
l.sort(key=lambda x: x[0])
count = 0
for i, val in enumerate(l):
    # touch.append(search_touched_idx(i, val, l))
    tmp = len(search_touched_idx(i, val, l))
    if tmp:
        count += tmp
# print(touch)
print(len(l) - count)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = []
p = []
res = 0
for _ in range(N):
  x, l = map(int, input().split())
  a.append((x - l + 1, x + l - 1))
  p.append(x - l + 1)
p.sort()
a.sort(key = lambda x: (x[0], -x[1]))
#print(a)
#print(p)
for i in range(N):
  r = bl(p, a[i][1])
  #print(a[i], r, i)
  if max(r - i - 1, 0) >= 1: res += 1
print(N - res)

Submission status: Wrong Answer

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

for i in range(n):
	x, l = map(int, input().split())
	a = x - l
	b = x + l
	is_kaburi=False
	for y in range(int(len(x_l)/2)):
		a_2 = x_l[(y*2)]
		b_2 = x_l[(y*2)+1]
		if a_2 < a and b_2 > a:
			is_kaburi=True
			break
		if a_2 < b and b_2 > b:
			is_kaburi=True
			break
	if is_kaburi == False:
		x_l.append(a)
		x_l.append(b)

if len(x_l)!=0:
	print(int(len(x_l)/2))
else:
	print(0)

Submission status: Wrong Answer

Solution code:
import math
def main():
    N = int(input())
    robo = []

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

    robo = sorted(robo, key=lambda x:x[1], reverse=True)
    robo = sorted(robo, key=lambda x: x[0])
    #print(robo)

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

    print(ans)




    return 0

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

xl.sort()
cnt=0
flag=0
for i in range(n-1):
    if flag==1:
        flag=0
        continue
    if xl[i][0]+xl[i][1] > xl[i+1][0]-xl[i+1][1]:
        cnt+=1
        flag=1
    else:
        flag=0
ans=n-cnt
print(ans)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
xl = [LI() for _ in range(n)]
lst = []
for x,l in xl:
    lst.append((x-l,x+l))
lst.sort(key = itemgetter(1),reverse=1)
ans = 0
i = 0
while i < n:
    (l,r) = lst[i]
    j = i+1
    while j < n:
        (l1,r1) = lst[j]
        if l < l1 < r:
            ans += 1
        else:
            break
        j += 1
    i = j+1
print(n-ans)

Submission status: Wrong Answer

Solution code:
import math
def main():
    N = int(input())
    robo = []

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

    robo = sorted(robo, key=lambda x:x[1])
    robo = sorted(robo, key=lambda x: x[0])
    #print(robo)

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

    print(ans)




    return 0

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

print(N - count)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = []
left = []
right = []
for i in range(n):
    x,l = map(int, input().split())
    # num , left , right
    d.append([i,x-l+1,x+l-1])
    #left.append([i,x-l+1,x+l-1])
    #right.append([i,x-l+1,x+l-1])

d.sort(key=lambda x:x[1],reverse=False)
#left.sort(key=lambda x:x[1],reverse=False)
#right.sort(key=lambda x:x[2],reverse=False)
#print(d)
p_r = 10**10 + 1
p_l = -1 * (10**10 + 1)
ans = 0
flag = True
while len(d) > 0:

    if flag:
        i,l,r = d.pop(-1)
        #print(i,l,r,p_l)
        if r < p_r and l > p_l:
            p_r = l
            flag = False
        else:
            ans += 1
    else:
        i,l,r = d.pop(0)
        #print(i,l,r,p_r)
        if r < p_r and l > p_l:
            p_l = r
            flag = True
        else:
            ans += 1
    #print(d)

print(n-ans)

Submission status: Wrong Answer

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

not_accepted = []

for s in range(n):
    if max_cnt >= n - s + 1 or (s not in not_accepted and s > 0):
        break

    rxs2 = rxs_[s:]

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

    if max_cnt < cnt:
        max_cnt = cnt

print(max_cnt)

Submission status: Wrong Answer

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

i, j = 0, 1
count = N
while j < count:
  if XL[i][0] + XL[i][1] > XL[j][0] - XL[j][1]:
    if XL[i][0] + XL[i][1] < XL[j][0] + XL[j][1]:
      j += 1
    else:
      i, j = j, j + 1
    count -= 1
  else:
    i, j = j, j + 1
print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
B=[]
for i in range(n):
    B.append([A[i][0]-A[i][1],A[i][0]+A[i][1]])
B.sort()
point=B[0][1]
ans=1
for i in range(1,n):
    if B[i][0]>=point:
        point=B[i][1]
        ans +=1

print(ans)

Submission status: Wrong Answer

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

x.sort()

i = n - 1
while i != 0:
    mins = max(0, x[i][0] - x[i][1])
    i -= 1
    maxs = x[i][0] + x[i][1]
    if mins < maxs:
        del x[i]
        i = len(x) - 1

print(len(x))

Submission status: Wrong Answer

Solution code:
N = int(input())
XL = []
for _ in range(N):
    x,l = map(int,input().split())
    XL.append([x-l,x+l])
XL.sort()
ANS = [XL[0]]
ans = 0
i = 1
flg = True
for a in ANS:
    while i < N:
        #完全に含まれている場合
        if a[0] <= XL[i][0] and XL[i][1] <= a[1]:
            #print(1)
            ANS.pop(0)
            ans += 1
            ANS.append(XL[i])
            i += 1
            flg = True
        elif a[1] <= XL[i][0]:
            if a[1] == XL[i][0] and flg:
                flg = False
                ans += 1
            #print(2)
            ans += 1
            ANS.append(XL[i])
            i += 1
            break
        else:
            #print(3)
            i += 1
            flg = True
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
li=[]
for i in range(0,n):
    flag=True
    x,l=map(int, input().split())
    mi=x-l
    ma=x+l
    for j in li:
        if j[0] < mi < j[1] or j[0] < ma < j[1]:
            flag=False
            break
    if flag:
        li.append([mi,ma])
print(len(li))

Submission status: Wrong Answer

Solution code:
n=int(input())

L=[]
for i in range(n):
    x,l=map(int,input().split())
    L.append([x,l])
L.sort(key=lambda x:x[0])

ans=1
bef=sum(L[0])
for i in range(1,n):
    if bef<=L[i][0]-L[i][1]:
        ans+=1
        bef=sum(L[i])
print(ans)

Submission status: Wrong Answer

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

K = len(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
    else:
        if co - X < 0:
            co = X+N
        else:
            co = X+N
            K -= 1
print(K)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter, attrgetter
def solve():
    def f(x, l):
        return [x, l - 1]
    n = int(input())
    B = [1] * n
    XL = sorted(f(*list(map(int, input().split()))) for _ in range(n))
    XL2 = sorted([[x, l, i] for i, [x, l] in enumerate(XL)], key=itemgetter(1), reverse=True)
    ans = n
    for x, l, i in XL2:
        if B[i] == 0:
            continue
        if 0 < i and B[i - 1] and XL[i - 1][0] + XL[i - 1][1] >= x - l:
            B[i] = 0
            ans -= 1
            continue
        if i < n - 1 and B[i + 1] and x + l >= XL[i + 1][0] + XL[i + 1][1]:
            B[i] = 0
            ans -= 1
            continue
    print(ans)
solve()

Submission status: Wrong Answer

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=1
now=0
temp=1
for i in range(n-1):
    if a[now][0]+a[now][1]>a[now+1][0]+a[now+1][1]:
        now+=1
    elif  a[now+temp][0]-a[now+temp][1]<a[now][0]+a[now][1]:
        temp+=1
    else:
        now+=temp
        temp=1
        cnt+=1

print(cnt)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())

wk =[]
for i in range(n):
    wk.append(list(map(int,input().split())))
xl = sorted(wk, key=lambda x:x[0])

xx = []
ll = []

cnt = 0
xx.append(xl[0][0])
ll.append(xl[0][1])

for i in range(1,n):
    x,l = xl[i][0],xl[i][1]

    if xx[cnt] + ll[cnt] -1 <  x - l + 1:
        if xx[cnt] + ll[cnt] -1 < x + l -1:
            xx.append(x)
            ll.append(l)
            cnt +=1
        else:
            xx[cnt] = x
            ll[cnt] = l

print(len(xx))