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:
N = int(input())
robot = []

for i in range(N):
    x,l = map(int,input().split())
    robot.append([x,l])
    
robot.sort()
use = [0]*N
i = 0

while i < N-1:
    #print(i,"called")
    min_j = i
    min_pos = robot[i][0] + robot[i][1]
    if (robot[i][0] + robot[i][1]) <= (robot[i+1][0] - robot[i+1][1]):
        #print(i, "pass")
        use[i] = 1
        if i == N-2:
            use[N-1] = 1
            break
        i += 1

    else:
        for j in range(i+1,N):
            if (robot[i][0] + robot[i][1]) <= (robot[j][0] - robot[j][1]):
                break
            else:
                if min_pos > robot[j][0] + robot[j][1]:
                    min_pos = robot[j][0] + robot[j][1]
                    min_j = j
        use[min_j] = 1
        #print(i, min_j)
        if i == min_j:
            i = j
        else:
            i = min_j
        

print(sum(use))
#print(use)

Submission status: Wrong Answer

Solution code:
n=int(input())
a =[]
for _ in range(n):
  a.append([int(i) for i in input().split()])
  
a.sort(key = lambda x : x[0])
#a.sort(key = lambda x : x[1])
#print(a)

curi = 0;curj=1
cnt=1
while(curj<n):
  if a[curi][0]+a[curi][1] <= a[curj][0]-a[curj][1]:
    curi=curj
    curj+=1
    cnt+=1
  else:
    curj+=1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = []
for i in range(n):
    X,L = map(int, input().split())
    x.append([X-L,X+L])
x.sort()
y = [0]*n
ans = 0
for i in range(n-1):
    if i==n-2:
        if x[i][1]>x[i+1][0] and y[i]==1:
            y[i-1] = 0
            y[i] = -1
            ans +=1
            if x[i+1][0]<x[i-1][1]:
                ans +=1
            continue
        elif x[i][1]>x[i+1][0] and y[i]<1:
            y[i+1] = -1
            ans +=1
            continue
        elif x[i+1][0]<x[i][1]:
            ans +=1
        else:
            continue
        

    if x[i][1]>x[i+2][0]:
        ans +=1
        y[i] = -1
        continue
    elif x[i][1]>x[i+1][0] and y[i]==0:
        y[i] +=1
        y[i+1] +=1
    elif x[i][1]>x[i+1][0] and y[i]==1:
        ans +=1
        y[i] = -1
        y[i-1] = 0
        continue

for i in range(n-1):
    if y[i]<=0:
        continue
    else:
        y[i] = 0
        y[i+1] = 0
        ans +=1
print(n-ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XL):
    ans = 0
    XL.sort(key=lambda x: x[0])
    XL.sort(key=lambda x: x[1])

    s = []
    for x, l in XL:
        lp, rp = x-l+1, x+l-1
        s.append((lp, rp))

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


    cand = [s.pop(0)]
    ans = 0
    for l, r in s:
        for ll, rr in cand:
            if rr >= l:
                break
        else:
            ans += len(cand)
            cand = [(l, r) if r < rr else (ll, rr)]

    return ans + len(cand)

def main():
    N = read_int()
    XL = [read_int_n() for _ in range(N)]
    print(slv(N, XL))

    # N = 10**5
    # XL = [[random.randint(0, 10**9), random.randint(0, 10**9)] for _ in range(N)]
    # print(slv(N, XL))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
lr = [[0,0]]*N

for i in range(N):
    X,L = map(int,input().split())
    lr[i] = [X-L,X+L]
lr_s = sorted(lr)

ans = 1
now_r = lr_s[0][1]

for i in range(1,N):
    next_l = lr_s[i][0]
    next_r = lr_s[i][1]
    if now_r > next_l: #かぶってるときは右端が小さい方を残す
        now_r = min(now_r,next_r)
        #ロボットの数の増減はプラマイゼロ
    else:
        #かぶってないときはロボットが増える
        ans += 1
        
print(ans)

Submission status: Wrong Answer

Solution code:
#input
N = int(input())
X = []
L = []
for i in range(N):
    X_temp, L_temp = map(int, input().split())
    X.append(X_temp)
    L.append(L_temp)

#output
import bisect as bi
import numpy as np

x = np.array(X)
l = np.array(L)

idx = np.argsort(x)
x = x[idx]
l = l[idx]

answer = 0
length = 0
for i in range(N):
    if length < x[i]:
        answer += 1
        length = l[i]

print(answer)

Submission status: Wrong Answer

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

ans = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
    ans[i][1]=(x[i]+l[i])
    ans[i][0]=max(0,x[i]-l[i])
ans.sort()
count=1
j=0
for i in range(n-1):
    if ans[j][1]<=ans[i+1][0] :
        count+=1
        j=i+1
    else:
        if ans[i][1]>ans[i+1][1]:
           j=i+1  

print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())

P = [0] * 150

robot = []

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

    robot.append([X,L])

robot = sorted(robot)

p_max = robot[0][0] + robot[0][1]
cnt = 1

for i in range(1,N):
    if p_max <= robot[i][0] - robot[i][1]:
        p_max  = robot[i][0] + robot[i][1]
        cnt += 1

robot = sorted(robot,reverse=True)

p_min = robot[0][0] - robot[0][1]
cnt2 = 1

for i in range(1,N):
    if p_min >= robot[i][0] + robot[i][1]:
        p_min  = robot[i][0] - robot[i][1]
        cnt2 += 1


print(max(cnt,cnt2))

Submission status: Wrong Answer

Solution code:
n = int(input())
xl = []
for i in range(n):
    x1, l1 = map(int, input().split())
    xl.append([x1 - l1, x1 + l1])
xl.sort()
ans = n
import copy
xl2 = copy.deepcopy(xl)
xl2 = xl2[::-1]
for i in range(1, n - 1):
    # print(xl, i)
    if xl[i - 1][1] > xl[i][0] and xl[i][1] > xl[i + 1][0]:
        xl[i] = copy.copy(xl[i - 1])
        ans -= 1
    elif xl[i - 1][1] > xl[i][0]:
        xl[i] = copy.copy(xl[i - 1])
        ans -= 1

i = n - 1
if xl[i - 1][1] > xl[i][0]:
    ans -= 1

ans1 = ans
ans = n
xl = xl2
for i in range(1, n - 1):
    # print(xl, i)
    if xl[i - 1][1] > xl[i][0] and xl[i][1] > xl[i + 1][0]:
        xl[i] = copy.copy(xl[i - 1])
        ans -= 1
    elif xl[i - 1][1] > xl[i][0]:
        xl[i] = copy.copy(xl[i - 1])
        ans -= 1

i = n - 1
if xl[i - 1][1] > xl[i][0]:
    ans -= 1

print(min(ans1, ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
x = []
for i in range(n):
    tmpx, tmpl = map(int,input().split())
    x.append((tmpx,tmpl))
x = sorted(x)
#print(x)
ans = n

flag = 1
for i in range(n-1):
    if x[i][0]+x[i][1]>x[i+1][0] and flag == 1:
        ans -= 1
        flag = 0
    elif x[i][0]+x[i][1]<=x[i+1][0] and flag == 0:
        flag = 1
print(ans)

Submission status: Wrong Answer

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

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

t = list(map(lambda j:(j[0]-j[1]+1, j[0]+j[1]-1), s))
NN = len(t)
dobon = []

for k, k_l in enumerate(t):
  if k in dobon:
    break
  else:
    for l in range(k+1, NN):
      if l in dobon:
        pass
      else:
        if int(k_l[1]) <= int(t[l][1]):
          if (t[l][0] <= k_l[1]) and (k_l[1] <= t[l][1]):
            N -= 1
            dobon.append(l)
            break
        else:
          if (t[l][0] <= k_l[0]) and (k_l[0] <= t[l][1]):
            N -= 1
            dobon.append(l)
            break

print(N)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for i in range(n):
    xl = list(map(int,input().split()))
    a.append(xl)
#print(a)
b = sorted(a)
#print(b)
count = 0
j =  0

for i in range(n-1):
    if j != 0:
        j = 0
        break
#if b[i][0] + b[i][1] > b[i+2][0] - b[i+2][1]:
    #if i <= n-3 and b[i-1][0] + b[i-1][1] > b[i+1][0] - b[i+1][1]:
    #    count -= 1
    #if i > 0 and b[i-1][0] + b[i-1][1] > b[i][0] - b[i][1]:
    #    count -= 1
    ude_mae = b[i][0] + b[i][1]
    ude_ushiro = b[i+1][0] - b[i+1][1]

    if ude_mae > ude_ushiro:
        count += 1
        j += 1
    #print(i)
        if i > 0 and b[i-1][0] + b[i-1][1] > b[i][0] - b[i][1]:
            count -= 1
        #if i <= n-3 and b[i][0] + b[i][1] > b[i+2][0] - b[i+2][1]:
        #    count -= 1
    #elif b[i][0] + b[i][1] > b[i+1][0] - b[i+1][1]:
    #    count += 1
    #    i += 1
#print(count)
ans = n - count
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if x[mid] >= n:
        rr = mid
    else:
        ll = mid+1


n = onem()
a = []
b = []
for i in range(n):
    x,c = m()
    a.append([x-c-1,x+c-1])
    b.append([x-c-1,x+c-1])

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

for i in range(n):
    if not aa:
        aa.append(a[0])
        bbb = a[0][1]
    else:
        if bbb <= a[i][0]:
            aa.append(a[i])
        else:
            continue

print(len(aa))

Submission status: Wrong Answer

Solution code:
n = int(input())

x = []
for i in range(n):
    x1, y1=[int(i) for i in input().split()]
    x.append([x1, y1])

x.sort()

remove = 0
stocks = 0

for k in range(n - 1):
    if k+1+stocks < n:
  	    if (x[k + 1 + stocks][0] - x[k][0]) < x[k][1] + x[k + 1][1]:
              
              remove += 1
              if x[k + 1][0] > x[k][0]:
                  x[k + 1][0] = -1
                  k -= 1
                  if n - 2 > k:
                      stocks += 1
              else:
                  x[k][0] = -1
                  
              
  	    else:
              stocks=0

print (n -remove)

Submission status: Wrong Answer

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

x.sort()

ans = n
cp = ans
maxs = 0
for i in range(n - 1):
    if cp == ans:
        maxs = max(maxs, x[i][0] + x[i][1])
    ming = x[i + 1][0] - x[i + 1][1]
    if ming < maxs:
        ans -= 1
    else:
        cp = ans

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
x = []
l = []
c = []
d = {}

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


dct = sorted(d.items())

print(dct)
f = 0
ans = 0
f = dct[0][0] + dct[0][1]
for i in range(1,len(dct)):
    if f > dct[i][0] - dct[i][1]:
        ans += 1
        f = min(f,dct[i][0]+dct[i][1])
    else:
        f = dct[i][0]+dct[i][1]


print(n-ans)

Submission status: Wrong Answer

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()
	ddeell = []
	for i,val in enumerate(tmp):
		if i == len(tmp)-1:
			break
		LL, RR = val
		LL2, RR2 = tmp[i+1]

		if RR > RR2:
			ddeell.append((LL,RR))

	habu = len(ddeell)

	for val in ddeell:
		tmp.remove(val)

	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(tt)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N=int(input())
XL=[]
for i in range(N):
    XL.append(list(map(int,list(input().split()))))
XL=np.asarray(XL)
XLs=XL[np.argsort(XL[:,0])]
right=XLs[0][0]+XLs[0][1]
ans=1
for i in range(N-1):
    if XLs[i+1][0]-XLs[i+1][1]-right>=0:
        ans+=1
        right=XLs[i+1][0]-XLs[i+1][1]
    elif right-(XLs[i+1][0]+XLs[i+1][1])>0:
        right=XLs[i+1][0]+XLs[i+1][1]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

c_n = 0
list_x = []
list_l = []
for i in range(n):
    x,l = map(int,input().split())
    if (c_n != 0):
        if list_x[c_n-1] > x:
            list_x.insert(c_n-1,x)
            list_l.insert(c_n-1,l)
        else:
            list_x.append(x)
            list_l.append(l)
    else:
        list_x.append(x)
        list_l.append(l)
    c_n += 1    
    
z = 0
y = 0
j = n
while y != n:
    if len(list_x) != z+1:
        aid = list_x[z+1] - list_x[z]     
        ud = list_l[z+1] + list_l[z]     

        if aid < ud:
            list_x.pop(z+1)
            list_l.pop(z+1)
            j -= 1
    else:
        z += 1
    y += 1

print(j)

Submission status: Wrong Answer

Solution code:
n = int(input())
xl = []
for i in range(n):
    x1, l1 = map(int, input().split())
    xl.append([x1, x1 - l1, x1 + l1])
xl.sort()
ans = n
import copy
xl2 = copy.deepcopy(xl)
xl2 = xl2[::-1]
for i in range(1, n - 1):
    # print(xl, i)
    if xl[i - 1][2] > xl[i][1] and xl[i][2] > xl[i + 1][1]:
        xl[i] = copy.copy(xl[i - 1])
        ans -= 1
    elif xl[i - 1][2] > xl[i][1]:
        xl[i] = copy.copy(xl[i - 1])
        ans -= 1

i = n - 1
if xl[i - 1][2] > xl[i][1]:
    ans -= 1

ans1 = ans
ans = n
xl == xl2
for i in range(1, n - 1):
    # print(xl, i)
    if xl[i - 1][2] > xl[i][1] and xl[i][2] > xl[i + 1][1]:
        xl[i] = copy.copy(xl[i - 1])
        ans -= 1
    elif xl[i - 1][2] > xl[i][1]:
        xl[i] = copy.copy(xl[i - 1])
        ans -= 1

i = n - 1
if xl[i - 1][2] > xl[i][1]:
    ans -= 1

print(min(ans1, ans))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

tmp = 0
for i in range(N):
    x, l = map(int, input().split())
    lower = x-l
    if x-l <= 0:
        lower = 0
    higher =  x+l

    array[i][0] = lower
    array[i][1] = higher

array.sort()
flg = 0
for i in range(len(array)-1):

    if flg == 1: continue
    if array[i+1][0] < array[i][1]:
        tmp += 1
        flg = 1
        continue
    flg = 0
print(len(array)-tmp)

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:
        
        # 1個前と比べて、範囲が重複してなければOK
        #print(bx - bl+1 , bx+bl-1 , x-l+1 , x+l-1)
        if (bx - bl+1 <= bx+bl-1 < x-l+1 <= x+l-1):
            # 1個前を更新
            bx = x
            bl = l
        else:
            #print("rem")
            rem +=1
            # 1個前は変えないで次へ
            continue

    else:
        # 1個前を更新
        bx = x
        bl = l
    

if rem == 0:
    print(N-1)
else:
    print(N-rem)

Submission status: Wrong Answer

Solution code:
n = int(input())
r = []
for i in range(n):
    x, l = map(int, input().split())
    r.append((x - l + 1, x + l - 1))
r.sort()
am = [[] for _ in range(n)]
for i in range(n):
    for j in range(i + 1, n):
        if r[i][1] < r[j][0]:
            break

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

Submission status: Wrong Answer

Solution code:
n=int(input())
li=[]
for i in range(n):
  tmpli=list(map(int, input().split()))
  li.append(tmpli)
li.sort()
# print(li)
for i in range(len(li)-1):
  if li[i][0]+li[i][1] > li[i+1][0]-li[i+1][1]:
    li[i+1][0] = 0
    a=li[i]
    li[i]=li[i+1]
    li[i+1]=a
    n -= 1
print(n)

Submission status: Wrong Answer

Solution code:
import sys
inputs = sys.stdin.readlines()

n = int(inputs[0])
Y = []
for s in inputs[1:]:
    x, l = map(int, s.split())
    Y.append((x-l+1, x+l-1))
Y.sort(key=lambda x: x[0])

cnt = 0
l0, r0 = Y[0]
for i in range(1, n):
    l, r = Y[i]
    if r0 >= l:
        cnt += 1
        if r0 > r:
            l0, r0 = l, r
    else:
        l0, r0 = l, r
print(n-cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = []
L = []
for i in range(N):
    a, b = map(int,input().split())
    X.append(a)
    L.append(b)
l = dict()
for i in range(N):
    l[X[i]] = L[i]
X.sort()
R = dict()
flag = dict()
for i in range(N):
    R[X[i]] = X[i] + l[X[i]]
    R[-X[i]] = X[i] - l[X[i]]
    flag[X[i]] = 0

for i in range(1,N-1):
    if i > 1:
        #3個以上侵食する奴ら
        if (R[X[i-2]] > R[-X[i]]): #or (R[X[i]] > R[-X[i+2]]):
            flag[X[i]] = 2
            continue
    if i < (N-3):
        if (R[X[i]] > R[-X[i+2]]):
            flag[X[i]] = 2
            continue
    #2個以上侵食する奴ら
    if (R[X[i-1]] > R[-X[i]]) and (R[X[i]] > R[-X[i+1]]):
        flag[X[i]] = 2
        continue
        #1個侵食する奴ら
    if (R[X[i-1]] > R[-X[i]]) or (R[X[i]] > R[-X[i+1]]):
        if flag[X[i]] == 0:
            flag[X[i]] = 1
#X[0]とX[N-1]の扱い
lenx = len(X)
if lenx > 2:
    if R[X[0]] > R[-X[2]]:
        flag[X[0]] = 2
if lenx > 1:
    if R[X[0]] > R[-X[1]]:
        if flag[X[0]] == 0:
            flag[X[0]] = 1
if lenx > 2:
    if R[X[N-3]] > R[X[N-1]]:
        flag[X[N-1]] = 2
if lenx > 2:
    if R[X[N-2]] > R[X[N-1]]:
        if flag[X[N-1]] == 0:
            flag[X[N-1]] = 1
while(1):
    fl = 0
    del2_list = []
    del2 = 0
    for i in range(len(X)):
        if flag[X[i]] != 2:
            del2_list.append(X[i])
        else:
            del2 = 1
            flag[X[i]] = -1
    if del2 > 0:
        X = del2_list
        X.sort()
    del1_list = []
    del1 = 0
    if del2 == 0:
        for i in range(len(X)-1):
            on_off = 1
            if flag[X[i]] != 1:
                del1_list.append(X[i])
            else:
                if flag[X[i+1]] == 1:
                    if R[X[i]] > R[-X[i+1]]:
                        del1_list.append(X[i])
                        on_off = 0
                del1 = 1
                if on_off:
                    flag[X[i]] = -1
        lenx = len(X)
        #len(X)-1の処理
        if lenx > 0:
            if flag[X[len(X)-1]] != 1:
                del1_list.append(X[len(X)-1])
            else:
                del1 = 1
                flag[X[len(X)-1]] = -1
        if del1 > 0:
            X = del1_list
            X.sort()


    R_2 = dict()
    for i in range(len(X)):
        R_2[X[i]] = X[i] + l[X[i]]
        R_2[-X[i]] = X[i] - l[X[i]]
        flag[X[i]] = 0
    for i in range(1,len(X)-1):
        if (R_2[X[i-1]] > R_2[-X[i]]) or (R_2[X[i]] > R_2[-X[i+1]]):
            if flag[X[i]] == 0:
                flag[X[i]] = 1
    if len(X) > 2:
        if R_2[X[0]] > R_2[-X[1]]:
            if flag[X[0]] == 0:
                flag[X[0]] = 1
    if len(X) > 2:
        if R_2[X[len(X)-2]] > R_2[X[len(X)-1]]:
            if flag[X[N-1]] == 0:
                flag[X[N-1]] = 1

    for i in range(len(X)):
        if flag[X[i]] > 0:
            fl = 1
    if fl == 0:
        break
ans = len(X)
if ans == 0:
    ans = 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

a=[]
k=[]

for i in range(N):
    m=input().split()
    k=[int(m[0]),int(m[1])]
    a.append(k)

a=sorted(a)

p=[]

z=[]
out=[]
for i in a:

    x=i[0]
    y=i[1]
    z=[x-y,x,x+y]

    p.append(z)
A=[]

counter=0
out=0
#[[-2, 2, 6], [1, 4, 7], [6, 9, 12], [95, 100, 105]]
for j in p:
    x0=j[0]
    x1=j[1]
    x2=j[2]
    if counter==0:

        A=[x0,x1,x2]
        counter+=1

        continue
    if A[0]<x0<A[2] :
        out+=1





        continue
    A=[x0,x1,x2]
    counter+=1

print(len(p)-out)

Submission status: Wrong Answer

Solution code:
n = int(input())
xl = []
for i in range(n):
    x1, l1 = map(int, input().split())
    xl.append([x1, x1 - l1, x1 + l1])
xl.sort()
ans = n
import copy
xl2 = copy.deepcopy(xl)
xl2 = xl2[::-1]
for i in range(1, n - 1):
    # print(xl, i)
    if xl[i - 1][2] > xl[i][1] and xl[i][2] > xl[i + 1][1]:
        xl[i] = copy.copy(xl[i - 1])
        ans -= 1
    elif xl[i - 1][2] > xl[i][1]:
        xl[i] = copy.copy(xl[i - 1])
        ans -= 1

ans1 = ans
ans = n
xl == xl2
for i in range(1, n - 1):
    # print(xl, i)
    if xl[i - 1][2] > xl[i][1] and xl[i][2] > xl[i + 1][1]:
        xl[i] = copy.copy(xl[i - 1])
        ans -= 1
    elif xl[i - 1][2] > xl[i][1]:
        xl[i] = copy.copy(xl[i - 1])
        ans -= 1

i = n - 1
if xl[i - 1][2] > xl[i][1]:
    ans -= 1

print(min(ans1, ans))

Submission status: Wrong Answer

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

for i in range(N-1):
  j=1
  while True:
    if XL[i][0]+XL[i][1]>XL[i+j][0]-XL[i][1]:
      F[i].append(i+j)
      F[i+j].append(i)
      F_c[i]+=1
      F_c[i+j]+=1
      j+=1
      if i+j==N:
        break
    else:
      break
      
ans=N
for i in range(N):
  j = F_c.index(max(F_c))
  if max(F_c)!=0:
    ans-=1
  for k in F[j]:
    F[k].remove(j)
    F_c[k]-=1
  F[j]=[]
  F_c[j]=0
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
XLlist = [tuple(map(int, input().split())) for _ in range(N)]
XLlist.sort(key=lambda x: x[0])
ans = 1
tikan = -1
x, l = XLlist[0]
rl = x + (l - 1)
for x, l in XLlist:
    ll = x - l
    if ll < rl:
        tikan += 1
        rl = min(rl, x + l - 1)
    else:
        ans += 1
        rl = x + l - 1

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XL):
    ans = 0
    XL.sort(key=lambda x: x[0])
    XL.sort(key=lambda x: x[1])

    s = []
    for x, l in XL:
        lp, rp = x-l+1, x+l-1
        s.append((lp, rp))

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


    cand = [s.pop(0)]
    ans = 0
    for l, r in s:
        for ll, rr in cand:
            if rr >= l:
                break
        else:
            ans += len(cand)
            cand = [(l, r)]

    return ans + len(cand)

    # p.sort()
    # d = {}
    # for i, v in enumerate(p):
    #     d[v] = i

    # ans = 0
    # a = [0] * len(p)
    # for lp, rp in s:
    #     # print(lp, rp)
    #     l = d[lp]
    #     r = d[rp]
    #     print(l, r)
    #     for i in range(l, r+1):
    #         if a[i] != 0:
    #             break
    #     else:
    #         ans += 1
    #         for i in range(l, r+1):
    #             a[i] = 1
    # return ans


def main():
    N = read_int()
    XL = [read_int_n() for _ in range(N)]
    print(slv(N, XL))

    # N = 10**5
    # XL = [[random.randint(0, 10**9), random.randint(0, 10**9)] for _ in range(N)]
    # print(slv(N, XL))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

P = [0] * 150

robot = []

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

    robot.append([X,L])

robot = sorted(robot)

p_max = robot[0][0] + robot[0][1]
cnt = 1

for i in range(1,N):
    if p_max <= robot[i][0] - robot[i][1]:
        p_max  = robot[i][0] + robot[i][1]
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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

x.sort()

ans = n
cp = ans
maxs = 0
for i in range(n - 1):
    if cp == ans:
        maxs = max(maxs, x[i][0] + x[i][1])
    ming = x[i + 1][0] - x[i + 1][1]
    if ming < maxs:
        ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

mylist= []

for n in range(N):
    x, l = map(int, input().split())
    mylist += [ [x-l, x +l] ]
    
mylist.sort()
#print(mylist)

overlap = [ [] for n in range(N) ]
#print(overlap)

n = 0

for m in range(len(mylist)):
    myl = mylist[m][0]
    myr = mylist[m][1]
    
    #左方向の探索
    if m != 0:
        l = m-1
        nr = mylist[l][1]
        while l >= 0 and nr > myl:
            overlap[m] += [l]
            l -= 1
            nr = mylist[l][1]
            
    #右方向の探索
    if m < len(mylist) - 1:
        r = m+1
        nl = mylist[r][0]
        #print(m, l < len(mylist), nl < myr)
        while r <= len(mylist)-1 and nl < myr:
            #print(m, l < len(mylist))
            overlap[m] += [r]
            if r < len(mylist)-1:
                r += 1
                nl = mylist[r][0]
            else:
                break
#print(overlap)

myans = 0
flag = [ 0 for n in range(N) ]
for i in range(len(overlap)):
    if len(overlap[i]) == 0:
        myans += 1
    elif len(overlap[i]) == 1:
        if len(overlap[overlap[i][0]]) > 1:
            myans += 1
        elif len(overlap[overlap[i][0]]) == 1:
            if flag[i] == 0:
                myans += 1
                flag[i] = 1
                flag[overlap[i][0]] = 1
print(myans)

Submission status: Wrong Answer

Solution code:
n=int(input())
li=[None]*n
for i in range(0,n):
    flag=True
    x,l=map(int, input().split())
    li[i]=(x,l)
li=sorted(li)
if (li[-1][0] - li[-1][1]) <= (li[0][0]+li[0][1]): 
    print(1)
else:
    for i in range(n):
        if li[i] == None:
            continue
        x,l = li[i]
        for j in range(i+1,n):
            x2,l2 = li[j]
            if x+l <= x2-l2:
                break
            li[j] = None
    print(len(li) - li.count(None))

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]) < 0:
        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())
data = [[]]*(n+2)
data[0] = [-10**10, -10**10]
for i in range(1, n+1):
    x, l = map(int, input().split())
    data[i] = [x-l, x+l]
data[n+1] = [10**10, 10**10]
data.sort()
ans = n
if n == 2:
  if data[1][1] > data[2][0]:
    ans -= 1
else:
  for i in range(1, n):
    if data[i][1] > data[i+1][0] and data[i-1][1] > data[i][0]:
        ans -= 1
        data[i][0] = 0
        data[i][1] = 0
    
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:
        
        # 1個前と比べて、範囲が重複してなければOK
        #print(bx - bl+1 , bx+bl-1 , x-l+1 , x+l-1)
        if (bx - bl+1 <= bx+bl-1 < x-l+1 <= x+l-1):
            # 1個前を更新
            bx = x
            bl = l
        else:
            #print("rem")
            rem +=1
            # 1個前は変えないで次へ
            continue

    else:
        # 1個前を更新
        bx = x
        bl = l
    

print(N-rem)