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:
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:
    if xright[i] > xright[i + 1]:
        count += 1
        i += 1
    else:
        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:
from collections import defaultdict
import sys
import math
from datetime import datetime
import re
import math
def sol(n, X, L):
    Cs = []
    for i in range(n):
        Cs.append( (X[i] - L[i], X[i] + L[i] ) )
    mini = sys.maxsize
    m, n = None, None
    counter = 0
    Cs.sort(key=lambda x : x[0])
    for a, b in Cs:
        if m is None:
            counter += 1
        elif a <= m and n <= b:
            counter += 1
        elif n <= a:
            counter += 1
        # 被っている部分の更新
        if m is None: m, n = a, b
        elif a < n: m, n = n, b
        else: m, n = max(a,n), b
    return counter





do_submit = True
#do_submit = False

def input_parse(input_str):
    lines = [x.strip() for x in input_str.split("\n") if x.strip()]
    parsed_lines = [list(map(str, line.split())) for line in lines]
    print(parsed_lines)
    # n = int(parsed_lines[0][0])
    # k = int(parsed_lines[0][1])
    S = parsed_lines[0][0]
    return S


if not do_submit:
    S = input_parse("""
    1905
    """)
    print(sol(S))

    S = input_parse("""
    0112
    """)
    print(sol(S))

    S = input_parse("""
    1700
    """)
    print(sol(S))

    S = input_parse("""
    0000
    """)
    print(sol(S))

    S = input_parse("""
    1001
    """)
    print(sol(S))



else:
    #A, B = list(map(int, input().split()))
    n = int(input())
    X = []
    L = []
    for i in range(n):
        x, l = list(map(int, input().split()))
        X.append(x)
        L.append(l)

    print(sol(n, X, L))

    # S = input().strip()
    # print(sol(S))

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
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][0] = xl[i - 1][0]
        xl[i][1] = xl[i - 1][1]
        xl[i][2] = xl[i - 1][2]
        ans -= 1
    elif xl[i - 1][2] > xl[i][1]:
        xl[i][0] = xl[i - 1][0]
        xl[i][1] = xl[i - 1][1]
        xl[i][2] = xl[i - 1][2]
        ans -= 1


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    MAX = 10 ** 5 + 10

    XL = [tuple(map(int, input().split())) for _ in range(N)]
    XL = sorted(XL, key=lambda x: (x[1], x[0]))

    ans = 0
    res = set()
    for x, l in XL:
        a = x - l
        a = a if a > 0 else 0
        b = x + l - 1
        b = b if b < MAX else (MAX - 1)

        if a not in res and b not in res:
            res |= set(range(a, b))
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

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

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[1]<x0<A[2] or A[1]<x1<A[2] or A[1]<x2<A[2]:

        p.pop(counter)




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

print(len(p))

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=sorted(B)
point=B[0][1]
a,b=1,1
for i in range(1,n):
    if B[i][0]>=point:
        point=B[i][1]
        a +=1

point=B[-1][0]
for i in reversed(range(1,n)):
    if B[i][1]<=point:
        point=B[i][0]
        b +=1
print(max(a,b))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

xl = sorted(xl)
max_cover=0
num_remove = 0
for i,t in enumerate(xl[1:]):
    if t[0] < max_cover:
        num_remove += 1
    else:
        max_cover = t[1]

print(N-num_remove)

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
import copy
import numpy as np
def main():
    n = int(input())
    arm = []
    for i in range(n):
        arm.append(list(map(int,input().split())))

    robot = copy.deepcopy(arm)
    comonn = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        robot[i][0] = (max(arm[i][0] - arm [i][1],0))
        robot[i][1] = arm[i][0] + arm[i][1]
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if min(robot[i]) < min(robot[j]) and max(robot[i])> min(robot[j]):
                comonn[i][j] += 1
                comonn[j][i] += 1

    remove_robot = 0
    remove_count = 0
    comonn_sum = 0
    for i in range(n):
        comonn_sum += sum(comonn[i])

    while comonn_sum > 0:
        for i in range(n-1):
            if sum(comonn[i]) < sum(comonn[i+1]):
                remove_robot = i + 1
        for i in range(n):
            comonn[remove_robot][i] = 0
        for i in range(n):
            comonn[i][remove_robot] = 0
        remove_count += 1
        comonn_sum = 0
        for i in range(n):
            comonn_sum += sum(comonn[i])
    ans = n - remove_count
    print(ans)



main()

Submission status: Wrong Answer

Solution code:
N = int(input())
XList = []
LList = []

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

TMP = zip(XList, LList)
tmp = sorted(TMP)
XList, LList = zip(*tmp)
XList = list(XList)
LList = list(LList)

for i in range(0, N):
    if i >= N - 1:
        break
    else:
        if XList[i] + LList[i] > XList[i + 1] - LList[i + 1]:
            if i + 2 >= N:
                XList.pop(i + 1)
                LList.pop(i + 1)
            elif XList[i] + LList[i] > XList[i + 2] - LList[i + 2]:
                XList.pop(i)
                LList.pop(i)
            else:
                XList.pop(i + 1)
                LList.pop(i + 1)
            i -= 1
            N -= 1
                
                
print(N)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
  n = int(input())
  xl = []
  ans = 0
  for i in range(n):
    xl.append(list(map(int, input().split())))
    xl.sort(key = lambda x:x[1])
    road = set()
  for i in range(n):
    sub = {}
    location = xl[i][0]
    arm = xl[i][1]
    sub = {j for j in range(location-arm+1, location+arm)}
    num_sub = len(sub)
    num_road = len(road)
    if num_sub & num_road == set():
      road = road|sub
      ans += 1

  print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

N = int(input())
X = [0] * N
L = [0] * N

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

for i in range(N -1):
    if X[i] > X[i+1]:
              tempX = X[i]
              X[i] = X[i+1]
              X[i+1] = tempX
              tempL = L[i]
              L[i] = L[i+1]
              L[i+1] = tempL

count = 0
leng1 = 0
leng2 = 0

for i in range(N-1):
    right1 = X[i] + L[i]
    left1 = X[i] - L[i]
    right2 = X[i+ 1] + L[i+ 1]
    left2 = X[i+ 1] - L[i+ 1]
    if abs(right1) < abs(left2):
           count = count + 1

print(N - count)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

N = int(input())
robots_attr = {}
robots = []
for _ in range(N):
    x, l = map(int, input().split(' '))
    robots.append(x)
    robots_attr[x] = {'len': l, 'eliminated': False}

robots = sorted(robots)
eliminated = 0

for i in range(N):
    if i != N-1:
        if robots[i] + robots_attr[robots[i]]['len'] - 1 >= robots[i+1] - robots_attr[robots[i+1]]['len'] + 1:
            robots_attr[robots[i]]['eliminated'] = True
            eliminated += 1
    else:
        shift = 0
        need_check = True
        while 1:
            if i-1-shift < 0:
                need_check = False
                break
            if robots_attr[robots[i-1-shift]]['eliminated']:
                shift += 1
            else:
                break
        if need_check and robots[i] - robots_attr[robots[i]]['len'] + 1 <= robots[i-1-shift] + robots_attr[robots[i-1-shift]]['len'] - 1:
                robots_attr[robots[i]]['eliminated'] = True
                eliminated += 1

print(N - eliminated)

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:
N = int(input())
XLlist = [tuple(map(int, input().split())) for _ in range(N)]
XLlist.sort(reverse=True)
ans = 1
tikan = -1
x, l = XLlist[0]
ll = x - (l - 1)
for x, l in XLlist:
    l -= 1
    rl = x + l
    if rl < ll:
        ans += 1
        ll = x - l
    else:
        tikan += 1
        ll = max(ll, x - l)

print(N - tikan)

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
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][0] = xl[i - 1][0]
        xl[i][1] = xl[i - 1][1]
        xl[i][2] = xl[i - 1][2]
        ans -= 1
    elif xl[i - 1][2] > xl[i][1]:
        xl[i][0] = xl[i - 1][0]
        xl[i][1] = xl[i - 1][1]
        xl[i][2] = xl[i - 1][2]
        ans -= 1


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    MAX = 10 ** 5 + 10

    XL = [tuple(map(int, input().split())) for _ in range(N)]
    XL = sorted(XL, key=lambda x: (x[0], x[1]))

    ans = 0
    res = set()
    for x, l in XL:
        a = x - l
        a = a if a > 0 else 0
        b = x + l - 1
        b = b if b < MAX else (MAX - 1)

        if a not in res and b not in res:
            res |= set(range(a, b))
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = 0
cnt = 0
li.sort()
temp = []

while True:
    arr = []
    check = -10**10
    if len(temp) == 0:
        for i in range(n):
            s = li[i][0] - li[i][1]
            if check > s:
                arr.append(i-1)
                arr.append(i)
            check = li[i][0] + li[i][1]
    else:
        for i in temp:
            s = li[i][0] - li[i][1]
            if check > s:
                arr.append(i-1)
                arr.append(i)
            check = li[i][0] + li[i][1]
    if len(arr) == 0:
        break
    arr = list(set(arr))
    temp = arr
    t = -2
    for index,i in enumerate(arr):
        if t == -2:
            t = i
        elif t+1 == i:
            del temp[index]
            t = -2
            ans += 1
        else:
            t = i

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]
    if arm_length != 0:
        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:
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
l.sort()
t=0
for i in range(0,n-1):
    if l[i+1][0]-l[i][0]<l[i+1][1]+l[i][1]:
        del l[i+1]
        l=[[0,0]]+l
        t+=1
        print(l)
print(max(t,n-t))

Submission status: Wrong Answer

Solution code:
n = int(input())
robot = []
for a in range(n):
    x,l = [int(i) for i in input().split()]
    index = 0
    i = 0
    while i < len(robot) and robot[i][0]-robot[i][1] < x + l:
        temp = robot[i]
        if x-l < temp[0]-temp[1] < x+l or x-l < temp[0] < x+l or x-l < temp[0]+temp[1] < x+l:
            break
        i += 1
    else:
        robot.insert(i, [x,l])
# print(robot)
print(len(robot))

Submission status: Wrong Answer

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

n = int(input())

a = [[0]*2 for _ in range(n)]

for i in range(n):
    a_temp, x_temp = map(int, input().split())
    a[i][0] = a_temp + x_temp - 1
    a[i][1] = a_temp - x_temp + 1

# print(a)
a.sort()
# print(a)
ans = n
temp = a[0][0]
for i in range(1, n):
    if temp >= a[i][1]:
        ans -= 1
    else:
        temp = a[i][0]
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
grid=[]
for i in range(N):
    xi,li=map(int,input().split())
    grid.append([xi,li])
grid = sorted(grid)
cnt,before=0,0
for i in range(1,N):
    now = grid[i][0] - grid[i][1]
    pre = grid[i-1][0] + grid[i-1][1]
    if before==0:
        if pre<=now:
            before=0
            continue
        else:
            cnt+=1
            before = pre
    else:
        if before<=now:
            before=0
            continue
        else:
            cnt+=1
print(N-cnt)

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]:
        count -= 1
        j += 1
    j += 1

print(count)

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()
	kabu = 0
	tt = []
	for i,val in enumerate(tmp):
		for j in range(i+1,len(tmp)):

			ima_L,ima_R = val
			tugi_L, tugi_R = tmp[j]

			if ima_R > tugi_L:
				kabu += 1
			else:
				break

		tt.append(kabu)
		kabu = 0
	aa = max(tt)
	print(N-aa)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N = int(input())
    X = []
    L = []
    LX = []
    for i in range(N):
        temp = list(map(int,input().split()))
        LX.append([temp[1]*2,temp[0]-temp[1]])

    LX.sort()

    res = 0
    end = - 10 ** 9

    for i in range(N):
        if end <= LX[i][1]:
            res += 1
            end = LX[i][0]

    print(res)



main()

Submission status: Wrong Answer

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

lr = []
for i in range(n):
    l = max(xl[i][0] - xl[i][1], 0)
    r = max(xl[i][0] + xl[i][1], 0)
    lr.append([l, r])

lr = sorted(lr)
cnt = 0

while cnt < n:
    for j in range(1, len(lr)):
        if lr[j - 1][0] == lr[j][0] or lr[j - 1][1] == lr[j][1]:
            lr.pop(j)
            break
        elif lr[j - 1][0] < lr[j][0] < lr[j - 1][1]:
            lr.pop(j)
            break

    cnt += 1

print(len(lr))

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-1, x-l, -(max(x,l) )))
        #before = list(range(bx+bl-1, bx-bl, -(max(bx,bl) )))
        #print(rn)
        #print(before)
        
        #print(bx - bl , bx, bx , bx+bl ,bx+bl , x-l , x-l , x ,x , x+l)
        if bx - bl+1 < bx and bx < bx+bl-1 and bx+bl-1 < x-l+1 and x-l+1 < x and x < x+l-1:
            # 1個前を更新
            bx = x
            bl = l
        else:
            #print("rem")
            rem +=1
            # 1個前は変えないで次へ
            continue

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

print(N-rem)

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = [list(map(int,input().split())) for i in range(N)]
arr = sorted(arr, key=lambda x: x[0])
F = [True]*N
P = [0]*N
for i in range(N):
  P[i] = [arr[i][0]-arr[i][1], arr[i][0]+arr[i][1]]
ind = 0
for i in range(1, N):
  if i == 1:
    if P[0][1] > P[1][0]:
      if P[0][1] <= P[1][1]:
        F[1] = False
      else:
        F[0] = False
        ind += 1
  else:
    if P[i][0] < P[ind][1]:
      if P[ind][1] > P[i][1]:
        F[ind] = False
        ind += 1
      else:
        F[i] = False
    else:
      ind += 1
print(F.count(True))

Submission status: Wrong Answer

Solution code:

def Key2():
    N = int(input())
    cnt = 0
    robotlist = []
    x, l = map(int, input().split())

    Lmin = x - l + 1
    Lmax = x + 1 - 1
    robotlist.append([Lmin, Lmax])
    for i in range(N - 1):
        x, l = map(int, input().split())
        flag = 'False'
        Lmin = x - l + 1
        Lmax = x + 1 - 1

        for r in robotlist:


            if r[0] <= Lmin <= r[1]:
                cnt += 1
                flag = 'True'
                continue
            elif r[0] <= Lmax <= r[1]:
                cnt += 1
                flag = 'True'
                continue
            elif r[0] <= x <= r[1]:
                cnt += 1
                flag = 'True'
                continue
        if flag == 'False':
            robotlist.append([Lmin, Lmax])
    


    print(N - cnt)

Key2()

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[0])
    robo = sorted(robo, key=lambda x: x[1])
    

    #print(robo)

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

    print(ans)




    return 0

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

# print("telitory:",ptelitory)
telitory = sorted(ptelitory)
# print(telitory)
unstable = 1
tmp_ind = list(range(len(telitory)))
while unstable:
    unstable = 0
#     print("tmp_ind:",tmp_ind)
    for i in range(len(tmp_ind)-1):
        t = tmp_ind[i]
        u = tmp_ind[i+1]
#         print("t:",t,"u:",u)
#         print(telitory[t],telitory[u])

        if telitory[t][1] > telitory[u][0]: 
            tmp_ind.remove(u)
            unstable = 1
            break
        else:
            pass
ans1 = len(tmp_ind)   
# print("-------------")
# double check
unstable = 1
tmp_ind = list(range(len(telitory)))
while unstable:
    unstable = 0
#     print("tmp_ind:",tmp_ind)
    for i in range(1,len(tmp_ind)):
        t = tmp_ind[i]
        u = tmp_ind[i-1]
#         print("t:",t,"u:",u)
#         print(telitory[t],telitory[u])

        if telitory[u][1] > telitory[t][0]: 
            tmp_ind.remove(u)
            unstable = 1
            break
        else:
            pass
ans2 = len(tmp_ind)
print(min(ans1,ans2))

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)):
            if flag[X[i]] != 1:
                del1_list.append(X[i])
            else:
                del1 = 1
                flag[X[i]] = -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)
print(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 + 1
	b = x + l - 1
	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])
    robo = sorted(robo, key=lambda x: x[0])

    #print(robo)

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

    print(ans)




    return 0

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
li = []
for i in range(N):
    hontai, ude = map(int, input().split())
    li.append([hontai, ude, hontai-ude, hontai+ude])
li.sort(key=lambda x:x[3])
#print(li)
count = 1
now = li[0][3]
for i in range(1, N):
    if now <= li[i][2]:
        count += 1
        now = li[i][2]
    #print(now, count)
print(count)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())

    X_L = tuple(tuple(int(j) for j in input().split()) for i in range(N))
    ranges = tuple((x - l, x + l) for x, l in X_L)
    # sorted_X_L = sorted(X_L, key=lambda x: x[1])

    # sorted_ranges = sorted(ranges, key=lambda x: x[0])

    # x_max = - 1e9
    # x_min = 2e9
    #
    # allowed = []
    #
    # for i in range(N):
    #     i_min = sorted_X_L[i][0] - sorted_X_L[i][1]
    #     i_max = sorted_X_L[i][0] + sorted_X_L[i][1]
    #
    #     if i_min >= x_max or i_max <= i_min:
    #         allowed.append(sorted_X_L[i])
    #         x_max = max(x_max, i_max)
    #         x_min = min(x_min, i_min)

    # print(len(allowed))

    # print(ranges)
    dup = calc_duplicates(ranges)
    print(dup[0])


def calc_duplicates(items):
    result = [0 for _ in range(len(items))]

    for i in range(len(items)):
        for j in range(len(items)):
            if is_duplicates(items[i], items[j]):
                result[i] += 1
    return result


# def duplicate_matrix(items):
#     result = [[0 for j in range(len(items))] for i in range(len(items))]
#
#     for i in range(len(items)):
#         for j in range(len(items)):
#             if is_duplicates(items[i], items[j]):
#                 result[i][j] = 1
#     return result


def is_duplicates(range1, range2):
    is_not_duplicated = range1[1] <= range2[0] or range1[0] >= range2[1]
    return not is_not_duplicated


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
for i in range(n):
    l.append(tuple(map(int,input().split())))
l = sorted(l)
ans = n
for i in range(n-1):
    L = l[i][0]+l[i][1]
    R = l[i+1][0]-l[i+1][1]
    if L > R:
        ans -= 1
        if i+2 <= n-1:
            R2 = l[i+2][0]-l[i+2][1]
            if L <= R2:
                l[i+1] = l[i]
        else:
            l[i+1] = l[i]
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

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[1]<x0<A[2] or A[1]<x1<A[2] or A[1]<x2<A[2]:
        p.pop(counter)

        counter+=1

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

print(len(p))

Submission status: Wrong Answer

Solution code:
N = int(input())
XL = [tuple(map(int,input().split())) for i in range(N)]
XL.sort(key=lambda x:x[1])
xs = set()
for x,l in XL:
    xs.add(x-l+1)
    xs.add(x+l-1)
ss = sorted(xs)
xtoi = {x:i for i,x in enumerate(ss)}

MAXN = 2*N+10
bit = [0] * MAXN
def bit_add(a,w):
    x = a
    while x <= MAXN:
        bit[x] += w
        x += (x & -x)

def bit_sum(a):
    x = a
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= (x & -x)
    return ret

ans = 0
for x,l in XL:
    s,t = x-l+1, x+l-1
    i,j = xtoi[s], xtoi[t]
    #print(i,j)
    if bit_sum(i) == bit_sum(j+1):
        ans += 1
        for k in range(i,j+1):
            bit_add(k+1,1)
    #for i in range(1,10):
    #    print(i, bit_sum(i))

print(ans)

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
    elif int(x[i][0]) - int(x[i][1]) > 1000000000:
        before = 1000000000
    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())
l = []
for i in range(n):
    l.append(tuple(map(int,input().split())))
l = sorted(l)
ans = n
for i in range(n-1):
    L = l[i][0]+l[i][1]
    R = l[i+1][0]-l[i+1][1]
    if L > R:
        ans -= 1
        if i+2 <= n-1:
            R2 = l[i+2][0]-l[i+2][1]
            print(R2)
            if L <= R2:
                l[i+1] = l[i]
        else:
            l[i+1] = l[i]
print(ans)