[Codility] Lesson6. NumberOfDiscIntersections (C#)

문제: app.codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/

NumberOfDiscIntersections coding task - Learn to Code - Codility

 

 

            int result = 0;
            int[] start = new int[A.Length];
            int[] end = new int[A.Length];
            int t = A.Length - 1;

            for (int i = 0; i < A.Length; i++)
            {
                int s = i > A[i] ? i - A[i] : 0;
                int e = t - i > A[i] ? i + A[i] : t;
                start[s]++;
                end[e]++;
            }

            t = 0;
            for (int i = 0; i < A.Length; i++)
            {
                if (start[i] > 0)
                {
                    result += t * start[i];
                    result += start[i] * (start[i] - 1) / 2;
                    if (10000000 < result) return -1;
                    t += start[i];
                }
                t -= end[i];
            }

            return result;