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())
r = [list(map(int, input().split())) for _ in range(N)]
r.sort()

ans = N
i = 1
l = i-1
while i < N:
    x1, l1 = r[l]
    x2, l2 = r[i]
    l = i
    if (x1+l1) > (x2-l2):
        i += 1
        ans -= 1
        if (x1+l1) > (x2+l2):
            l += 1
    i += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = []
for _ in range(N):
  x, l = map(int,input().split())
  X.append([x+l, x-l, x, l])
sorted_X = sorted(X, key=lambda x:(x[1], x[2]))
ans = 1
cnt = sorted_X[0][0]
for i in range(N):
  if sorted_X[i][1] >= cnt:
    ans += 1
    cnt = sorted_X[i][0]
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=0
ans2=0
cnt=-(10**9)
cnt2=(10**9)*2
li=[]
for i in range(n):
    X,L=map(int,input().split())
    li.append([X,L])
li=sorted(li,key=lambda x:x[0])
for i in range(n):
    if cnt>li[i][0]-li[i][1]:
        ans+=1
    else:
        cnt=li[i][0]+li[i][1]
li=sorted(li,key=lambda x:x[0],reverse=True)
for i in range(n):
    if cnt2<li[i][0]+li[i][1]:
        ans2+=1
    else:
        cnt2=li[i][0]-li[i][1]
print(n-min(ans,ans2))

Submission status: Wrong Answer

Solution code:
from math import ceil

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

reps = [0] * len(xl)
for i in range(len(xl) - 1):
    if (xl[i + 1][0] - xl[i + 1][1]) < (xl[i][0] + xl[i][1]):
        reps[i + 1] = 1
print(n - (ans + ceil(reps.count(1) / 2)))

Submission status: Wrong Answer

Solution code:
n = int(input())
li=[]
lis=[]
count_lis=[0]*n
for i in range(n):
    li = list(map(int, input().split()))
    lis.append(li)
lis.sort()
for i in range(n):
    for j in range(i+1, n):
        if lis[i][0] + lis[i][1] > lis[j][0] - lis[j][1]:
            count_lis[i] += 1
            count_lis[j] += 1
        else:
            break
num = n- int(sum(count_lis)/2)
print(str(num))

Submission status: Wrong Answer

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

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


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

print(ans)

Submission status: Wrong Answer

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

minno = []
maxno = []
no = 0

for i in range(n):
    minno.append(L[i][0] - L[i][1])
    maxno.append(L[i][0] + L[i][1])



for k in range(10000):

    t = [0] * n

    for i in range(n - k):
        for j in range(n-i-1-k):
            if (minno[i] < minno[i + j + 1] and maxno[i] > minno[i + j + 1]) or (minno[i] < maxno[i + j + 1] and maxno[i] > maxno[i + j + 1]) \
                    or (minno[i + j + 1] < minno[i] and maxno[i] < maxno[i + j + 1]):
                t[i] += 1
                t[i+j+1] += 1


    for i in range(n):
        if max(t) == 0:
            print(n-no)
            sys.exit()

        if t[i] == max(t):
            print(i)
            del minno[i]
            del maxno[i]
            no += 1
            break

Submission status: Wrong Answer

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

for i in range(n):
    inp = list(map(int, input().split()))
    dic[inp[0]] = inp[1]

dic = sorted(dic.items())
ans = 1
pre = dic[0][0]+dic[0][1]
fidx = 0
for i in range(1, n):
    n_s = dic[i][0]+dic[i][1]
    if pre > n_s:
        pre = n_s
        fidx = i
idx = fidx

for i in range(fidx+1, n):
    if dic[idx][0]+dic[idx][1] > dic[i][0]-dic[i][1]:
        if dic[fidx][0]+dic[fidx][1] > dic[i][0]+dic[i][1]:
            idx = i
    else:
        ans += 1
        idx = i


print(ans)

Submission status: Wrong Answer

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

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

ans = 0
t = -10**9
for i in range(N):
    if t <= XL[i][0]:
        ans += 1
        t = XL[i][1]
print(ans)

Submission status: Wrong Answer

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

robots = sorted(robots, key=lambda x: x[0])
rightest_point = robots[0][0] + robots[0][1] - 1
ans = 0
# 無理やり一体目を置いた時
for i in range(1, len(robots)):
    if robots[i][0]-robots[i][1] + 1 < rightest_point:
        ans += 1
        continue
    else:
        rightest_point = robots[i][0]+robots[i][1] - 1
first = N-ans


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

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)
  res += max(r - i - 1, 0)
print(N - res)

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.sort()
    #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())
XL=sorted([list(map(int,input().split())) for i in range(N)])
l,a=-10**9,1
for i in range(1,N):
    if XL[i][0]-XL[i][1]<l:
        a+=1
    else:
        l=XL[i][0]+XL[i][1]
l,b=XL[0][0]+XL[0][1],0
for i in range(1,N):
    if XL[i][0]-XL[i][1]<l:
        b+=1
    else:
        l=XL[i][0]+XL[i][1]
print(N-min(a,b))

Submission status: Wrong Answer

Solution code:
n=int(input())
xlis=sorted([list(map(int,input().split())) for i in range(n)])
counter=0
nlis=[]
rlis=[]
highest=-1000000000000
th=0
for i in range(n):
    high=xlis[i][0]+xlis[i][1]
    low=xlis[i][0]-xlis[i][1]
    nlis.append([low,high])
    rlis.append([low,high])
for i in range(n-2):
    if nlis[i][1]>=nlis[i+2][0]:
        rlis.remove(nlis[i])
for i in range(len(rlis)):
    if rlis[i][0]>=highest:
        counter+=1
        highest=rlis[i][1]
        th=0
print(counter)

Submission status: Wrong Answer

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

x, l = xl[0]
ans = n
for i in range(1, n):
    if l > xl[i][1]: 
        if (
            x-l < xl[i][0]-xl[i][1] < x+l or
            x-l < xl[i][0]+xl[i][1] < x+l
            ):
                ans -= 1
    else:
        if (
            xl[i][0]-xl[i][1] < x-l < xl[i][0]+xl[i][1] or
            xl[i][0]-xl[i][1] < x+l < xl[i][0]+xl[i][1]
            ):
                x, l = xl[i]
                ans -= 1

print(ans)

Submission status: Wrong Answer

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

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

ans = 0
t = -10**9
for i in range(N):
    if t <= XL[i][0] and XL[i]:
        ans += 1
        t = XL[i][1]
print(ans)

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]

count = 0
i = 0
while i < N - 1:
    for j in range(i + 1, N):
        if x[i] + l[i] > x[j] - l[j]:
            count += 1
            j = j + 1
        else:
            i = j
            break
    else:
        break
print(N - 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
  else:
    bf = i+1
  if ans == 0:
    break
  
print(ans)

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[i][0], a[i][1] = map(int, input().split())

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

Submission status: Wrong Answer

Solution code:
n = int(input())
robot = [
    list(map(int, input().split())) for i in range(n)
]
robot.sort(key=lambda x: x[0], reverse=True)
ans = [robot.pop()]
for i in range(1, n):
    robot_i = robot.pop()
    x_dif = robot_i[0] - ans[-1][0]
    r_necessary = robot_i[1] + ans[-1][1]
    if r_necessary <= x_dif:
        ans.append(robot_i)

print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
XL = []
for n in range(N):
    XL.append([int(x) for x in input().split()])
XL = sorted(XL, key=lambda x:x[0]+x[1])
m = 0
ans = 0
for n in range(N):
    if XL[n][0]-XL[n][1] >= m:
        ans += 1
        m = XL[n][0]+XL[n][1]
print(ans)

Submission status: Wrong Answer

Solution code:
#python3
import operator as op
n = int(input())
a = []
for _ in range(n):
    x, l = map(int, input().split())
    a.append((x,l))

a.sort(key=op.itemgetter(0))

MAX = -1001001001
cnt = 0
for i in range(n):
    x, l = a[i]
    MIN = x - l
    if MAX > MIN:
        pass
    else:
        cnt +=1
        MAX = x+l

print(cnt)

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=0
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]:
        cnt+=1
        now+=1
    elif  a[now+temp][0]-a[now+temp][1]<a[now][0]+a[now][1]:
        cnt+=1
        temp+=1
    else:
        now+=temp
        temp=1

print(n-cnt)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
import itertools
from functools import reduce
from operator import mul
def gcd(*numbers):
    return reduce(math.gcd, numbers)


def gcd_list(numbers):
    return reduce(math.gcd, numbers)


def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


N = int(stdin.readline().rstrip())
Xs = []
Ls = []
Ran = []
for k in range(N):
    tmp = stdin.readline().rstrip().split()
    Xs.append(int(tmp[0]))
    Ls.append(int(tmp[1]))
    before = int(tmp[0]) - int(tmp[1])
    after = int(tmp[0]) + int(tmp[1])
    Ran.append([before, after, int(tmp[0])])
sorted_data = sorted(Ran, key=lambda x: (x[2]))
Ran = sorted_data
count = 0
posAfter = Ran[0][1]
numP = 0
numT = 1
while True:
    if numP == len(Ran):
        break
    if numT == len(Ran):
        break
    nextBefore = Ran[numT][0]
    if nextBefore < posAfter:
        count += 1
        numT += 1
    else:
        numP = numT
        numT = numP+1
        posAfter = Ran[numP][1]
a = N - count
sorted_data = sorted(Ran, key=lambda x: (x[2]), reverse=True)
Ran = sorted_data
count = 0
posAfter = Ran[0][1]
numP = 0
numT = 1
while True:
    if numP == len(Ran):
        break
    if numT == len(Ran):
        break
    nextBefore = Ran[numT][0]
    if nextBefore < posAfter:
        count += 1
        numT += 1
    else:
        numP = numT
        numT = numP+1
        posAfter = Ran[numP][1]
b = N - count
res = a if a >= b else b
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
robots = []
for i in range(n):
    l = input().split()
    x = int(l[0])
    length = int(l[1])
    robots.append((x - length + 1, x + length - 1))

    
robots = sorted(robots, key=lambda x:x[0])
covered_x = robots.pop(0)[1]
robots_num = 1
try:
    while True:
        robots = filter(lambda r: r[0] > covered_x, robots)
        covered_x = next(robots)[1]
        robots_num += 1
except StopIteration:
    pass
print(robots_num)

Submission status: Wrong Answer

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

removal_count = 0
for index, arm in enumerate(s):
  if arm[0]+arm[1]>= s[index][0]+s[index][1]:
    removal_count += 1
print(removal_count)

Submission status: Wrong Answer

Solution code:
import queue
import copy
import math
from collections import deque

# そのまま入力文字列の入力
n = int(input())

lines = []

for i in range(0, n):
    # 2つの入力を空白で分割し、数値化
    x, l = map(int, input().split())
    lines.append((x-l, x+l))

sorted_line = deque(sorted(lines))

ans = 0
while True:
    if len(sorted_line) == 1:
        break

    current_line = sorted_line.popleft()
    next_line = sorted_line[0]

    if current_line[1] <= next_line[0]:
        pass
    else:
        if current_line[1] < next_line[1]:
            # ----
            #   ----
            if len(sorted_line) >= 2:
                next_line = sorted_line.popleft()
                next_next_line = sorted_line[0]

                if next_next_line[0] < next_line[1]:
                    # ----        o
                    #   ----      x
                    #     ----    o
                    sorted_line.appendleft(current_line)
                    ans += 1
                elif next_next_line[0] < next_line[1]:
                    # ----       o
                    #   -------  x
                    #     ----   o
                    sorted_line.appendleft(current_line)
                    ans += 1
                else:
                    # ----         o
                    #   ----       x
                    #        ----  o
                    sorted_line.appendleft(current_line)
                    ans += 1
        else:
            # -------      ---------
            #   -----  or    ----
            ans += 1

print(n - ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

X = []
d = {}

for _ in range(N):
    x,l = map(int, input().split())
    X.append(x)
    d[x] = l
X.sort()
count = 0
for i in range(0,len(X)-1):

    I = (X[i]+d[X[i]]-1)

    J = (X[i+1]-d[X[i+1]]+1)
    if I>=J:
        count = count + 1
        idx = i
        idx = idx + 2
        flg = 1
        while flg!=0:
            if idx>(N-1):
                break
            J = (X[idx]-d[X[idx]]+1)
            if I>=J:
                count = count + 1
                idx = idx + 1
                continue
            else:
                i = idx
                break      
        continue
print(N-count)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N = int(input())
XL = sorted([list(map(int, input().split())) for _ in range(N)], key=itemgetter(0, 1))

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

print(res)

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:
    l -= 1
    ll = x - l
    if ll <= rl:
        tikan += 1
        rl = min(rl, x + l)
    else:
        ans += 1
        rl = x + l
if ans != N - tikan:
    raise ValueError
print(N - tikan)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
prev_x = 0
prev_l = 0
sum = n
d = {}
for i in range(n):
  x,l = map(int, input().split())
  d[x] = l
d_sorted = sorted(d.items(), key=lambda x:x[0])

count = 0
for x,l in d_sorted:
    if count == 0:
      count = count + 1
      prev_x, prev_l = x, l
      continue
    if x - l < prev_x + prev_l:
      sum = sum -1
      i = i + 1
    else:
      prev_x, prev_l = x, l
    count = count + 1
print(sum)
'''

'''

Submission status: Wrong Answer

Solution code:
N = int(input())

list_ = list()

for i in range(N):
  X,L = map(int,input().split())
  max_ = min(10**9,X+L-0.1)
  min_ = max(0,X-L+0.1)
  list_.append((X,min_,max_))
list_.sort()

d = 0
nowmax = -1
nowmin = -1

for x, min_, max_ in list_:
  if nowmax > min_:
    d += 1
    if nowmin >= min_:
      pass
    elif nowmax <= max_:
      pass
    else:
      nowmin = min_
      nowmax = max_
  else:
    nowmin = min_
    nowmax = max_
  
print(N-d)

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-cnt][0] + List[i-cnt][1])
  hidari = int(List[i+2-cnt][0] - List[i+2-cnt][1])
  if migi > hidari:
    List.pop(i-cnt)
    cnt = cnt + 1

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

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

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

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

Submission status: Wrong Answer

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

N = int(readline())
X, L = zip(*[map(int, readline().split()) for i in range(N)])

rm = -10000000
dropc = 0
for i in range(N):
    if X[i] - L[i] < rm:
        if rm > X[i] + L[i]:
            rm = X[i] + L[i]
        dropc += 1
    else:
        rm = X[i] + L[i]

print(N - dropc)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    xls_input = [[int(k) for k in input().split(" ")] for n in range(N)]
    xls_input.sort()

    xls = []
    ans = N
    for i in range(N):
        xl = xls_input[i]
        if i == 0:
            xls.append(xl)
        else:
            xl_before = xls[-1]
            x_before = xl_before[0]
            l_before = xl_before[1]
            x = xl[0]
            l = xl[1]
            if x - x_before < l + l_before:
                ans -= 1
            else:
                xls.append(xl)
    print(ans)


if __name__ == '__main__':
    main()

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 xl[i-1][1]>t[0] or max_cover > t[0]:
        num_remove +=1
        if xl[i-1][1]>max_cover:
            max_cover = t[1]

print(N-int(num_remove/2))

Submission status: Wrong Answer

Solution code:
import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n = ni()
xl = [na() for i in range(n)]
xl.sort()
d = [(xl[i][0] - xl[i][1] + 1, xl[i][0] + xl[i][1] - 1) for i in range(n)]
p = [1 if i > 0 and d[i][0] <= d[i - 1][1] else 0 for i in range(n)]
q = [1 if i < n - 1 and d[i + 1][0] <= d[i][1] else 0 for i in range(n)]
print(p)
print(q)

res = min(sum(p), sum(q))

print(n - res)

Submission status: Wrong Answer

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

for i in range(n):
    inp = list(map(int, input().split()))
    dic[inp[0]] = inp[1]

dic = sorted(dic.items())
ans = 1
pre = dic[0][0]+dic[0][1]
fidx = 0
for i in range(1, n):
    n_s = dic[i][0]+dic[i][1]
    if pre > n_s:
        pre = n_s
        fidx = i
idx = fidx

for i in range(fidx+1, n):
    if dic[idx][0]+dic[idx][1] > dic[i][0]-dic[i][1]:
        if dic[fidx][0]+dic[fidx][1] > dic[i][0]+dic[i][1]:
            idx = i
    else:
        ans += 1


print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

robots = []
for _ in range(N):
    robots.append([int(x) for x in input().split()])

lines = [(robots[0][0]-robots[0][1], robots[0][0]-robots[0][1])]
count = 0
for robot in robots[1:]:
    left = robot[0]-robot[1]
    right = robot[0]+robot[1]

    for r in lines:
        if (left not in range(r[0], r[1]) and right-1 not in range(r[0], r[1])):
            lines.append((left, right))

    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
min_list = []
max_list = []
middle_list = []
for i in range(n):
    a,b = map(int,input().split(" "))
    min_list.append(a - b)
    max_list.append(a + b)
    middle_list.append(a)

count = 0    
for i in range(n):
    if min_list[i] <= middle_list[0] <= max_list[i]:
        count += 1
       
res = n - (count - 1)
    
print(res)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N=int(input())
zahyo=[]
kouho = []
hako=[]
for i in range(N):
    X,Y=map(int,input().split())
    zahyo.append([X-Y,X+Y,X])
zahyo.sort(key=itemgetter(2))



j=0
while j<len(zahyo):
    if j+1<len(zahyo):
        if zahyo[j][1]>zahyo[j+1][0]:   
            if j+2<len(zahyo): 
                if zahyo[j+1][1]>zahyo[j+2][0]:
                    zahyo.pop(j+1)
                else:
                    j+=1
            else:
                j+=1
                    
        elif zahyo[j][1]>zahyo[j+1][0]:
            if j-1>=0:
                if zahyo[j][1]>zahyo[j-1][0]:
                    zahyo.pop(j)
                else:
                    j+=1
            else:
                j+=1               
        else:
            j+=1
    else:
        break
k=0
while k+1<len(zahyo):
    if zahyo[k][1]>zahyo[k+1][0]:
        zahyo.pop(k)
    else:
        k+=1
print(len(zahyo))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3.5
# -*- coding: utf-8 -*-
from math import ceil

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

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

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

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

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


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

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

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
xl = []
ans = n
for i in range(n):
    x, l = map(int, input().split())
    xl.append([x - l + 1, x + l - 1])
x1 = 0
x2 = 1
xl.sort()
while x2 < n:
    f = xl[x1][1]
    s = xl[x2][0]
    if s <= f:
        ans -= 1
        num1 = xl[x1][1] - xl[x1][0]
        num2 = xl[x2][1] - xl[x2][0]
        if num1 > num2:
            x1 += 1
            x2 += 1
        else:
            x2 += 1
    else:
        x1 += 1
        x2 += 1
print(ans)

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
  else:
    bf = i+1
    
print(ans)

Submission status: Wrong Answer

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

ppair.sort()
ans = 0
pf = False
for i in range(N-1):
    if (pf):
        pf = False
        continue
    else:
        if (sum(ppair[i]) > ppair[i+1][0] - ppair[i+1][1]):
            ans += 1
            pf = True

print(max(N-ans,ans))

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 = []
    XL = []
    for i in range(N):
        temp = list(map(int,input().split()))
        XL.append([temp[0],temp[1]])

    XL.sort()

    res = 1
    end = sum(XL[0])

    for i in range(1,N):
        if end <= XL[i][0] - XL[i][1]:
            res += 1
            end = sum(XL[i])

    print(res)



main()

Submission status: Wrong Answer

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

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


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

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

X = []
d = {}

for _ in range(N):
    x,l = map(int, input().split())
    X.append(x)
    d[x] = l
X.sort()
count = 0
for i in range(0,len(X)-1):

    I = (X[i]+d[X[i]]-1)

    J = (X[i+1]-d[X[i+1]]+1)
    if I>=J:
        count = count + 1
        idx = i
        idx = idx + 2
        flg = 1
        while flg!=0:
            if idx>(N-1):
                break
            J = (X[idx]-d[X[idx]]+1)
            if I>=J:
                count = count + 1
                idx = idx + 1
                continue
            else:
                i = i + 2
                break      
        continue
print(N-count)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

cnt = N
start, end = map(int, b_list[0])
for i in range(1,N):
  start_, end_ = map(int, b_list[i])
  if start_ <= end:
    if end_ <= end:
      cnt -= 1
      start = start_
      end = end_
      continue
    else:
      cnt -= 1
      continue
  else:
    start = start_
    end = end_
      
      
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = [0]*N
L = [0]*N
d = {}
max = 0
del_count = 0
first = 0
for i in range(N):

  x,l= map(int,list(input().split()))
  if i == 0:
    first = x
  d[x] = l
s = sorted(d.items())
new_list = sorted(X)
for x,l in s:
  if first == x:
    max = x + l
  elif max > x - l:
    del_count +=1
  else:
    max = x + l
print(N-del_count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
X = [0] * N
for i in range(N):
    x, l = map(int, input().split())
    X[i] = x, l, x - l, x + l

X.sort(key=lambda x: x[1], reverse=True)  # 長い順
X = list(enumerate(X))
removed = [False] * N
X2 = sorted(X, key=lambda x: x[1][2])  # 端点順

for i, t in X:
    x, l, rl, rr = t
    if i <= N - 2 and rr <= X2[i + 1][1][2] and not removed[X2[i + 1][0]]:
        removed[i] = True
    if i >= 1 and rl >= X2[i - 1][1][3] and not removed[X2[i - 1][0]]:
        removed[i] = True

print(N - sum(removed))

Submission status: Wrong Answer

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

new = sorted(list)
i = 0
d = 0
while i < n-1:
  if new[i][0] + new[i][1] > new[i+1][0] - new[i+1][1]:
    if i + 2 > n-1:
      d = d + 1
    else:
      if new[i][0] + new[i][1] > new[i+2][0] - new[i+2][1]:
        d = d +1
      else:
        new[i+1] = new[i]
        d = d + 1
    i = i + 1
  else:
    i = i + 1  

print(n - d)

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

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

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

print(len(xx))

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])
#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+=1
    curj+=1
    cnt+=1
  else:
    curj+=1
    
print(cnt)

Submission status: Wrong Answer

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

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

ans = 0
t = -10**9
for i in range(N):
    if t < XL[i][0]:
        ans += 1
        t = XL[i][1]
print(ans)