
# problem

# We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the
# radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].
#
# We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common
# point (assuming that the discs contain their borders).
#
# The figure below shows discs drawn for N = 6 and A as follows:
#
#   A[0] = 1
#   A[1] = 5
#   A[2] = 2
#   A[3] = 1
#   A[4] = 4
#   A[5] = 0
#
#
# There are eleven (unordered) pairs of discs that intersect, namely:
#
# discs 1 and 4 intersect, and both intersect with all the other discs;
# disc 2 also intersects with discs 0 and 3.
# Write a function:
#
# def solution(A)
#
# that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs.
# The function should return −1 if the number of intersecting pairs exceeds 10,000,000.
#
# Given array A shown above, the function should return 11, as explained above.
#
# Write an efficient algorithm for the following assumptions:
#
# N is an integer within the range [0..100,000];
# each element of array A is an integer within the range [0..2,147,483,647].

# how many times do the discs intersect

class DiscLog():
    def __init__(self, x, start_end): # x is where it is happening, start or end of teh disk
        self.x = x
        self.start_end = start_end

def solution(A):
    discHistory = [] # define an empty array, this will be the event log
    for i in range(len(A)):
        discHistory.append(DiscLog(i - A[i], 1)) # the start of the disk
        discHistory.append(DiscLog(i + A[i], -1)) # the end of the disk
    discHistory.sort(key=lambda d: (d.x, -d.start_end)) #then sort the disk history, use lamda to know how to sort
    intersections = 0 #this will hold teh result
    active_intersections = 0 # this will be the cumulative number
    for log in discHistory:
        active_intersections += log.start_end
        if log.start_end > 0:
            intersections += active_intersections - 1
        if intersections > 10000000:
            return -1
    return intersections

print(solution([1, 5, 2, 1, 4, 0]))

print(solution([0] * 100000))