Overview

Collect the goal times of runners by school, and compute the total sum of \(|L_i - L_j|\) over all pairs \((i, j)\) within the same school.

Analysis

If the number of people belonging to the same school is \(k\), the number of pairs within that school is \(\frac{k(k-1)}{2}\). Naively enumerating all pairs for each school and summing the absolute differences would be \(O(N^2)\) (about 500,000 operations) in the worst case when \(N=1000\), which might seem feasible at first glance. However, as the number of people increases this quickly becomes too slow, and a better method is needed.

The two key observations are:

• The sum of absolute values becomes easier to handle after sorting
  If we sort the times of a school in ascending order as \(a_0 \le a_1 \le \dots \le a_{k-1}\), then for \(i < j\) we have \(|a_i - a_j| = a_j - a_i\), eliminating the absolute value.
• The “contribution of each element with respect to preceding elements” can be computed efficiently using prefix sums
  The sum of differences that \(a_j\) creates is $\( \sum_{i=0}^{j-1} (a_j - a_i) = j\cdot a_j - \sum_{i=0}^{j-1} a_i \)\( By maintaining \)\sum_{i=0}^{j-1} a_i\( as a prefix sum, this can be computed in \)O(1)$.

For example, when the times are \([2, 5, 9]\) (already sorted): - \(j=0\): contribution \(0\) - \(j=1\): \(1 \cdot 5 - (2) = 3\) - \(j=2\): \(2 \cdot 9 - (2 + 5) = 18 - 7 = 11\) Total: \(3 + 11 = 14\), which matches \(|2-5| + |2-9| + |5-9| = 14\).

By performing this computation for each school and summing across all schools, we obtain the answer.

Algorithm

1. Read the input and group the times \(L_i\) into arrays by school number \(C_i\) (using a dictionary groups).
2. For each school, do the following:
   1. Sort the time array times in ascending order.
   2. Initialize the prefix sum pref to \(0\).
   3. Iterate through times from left to right. Let \(i\) be the index and \(x\) be the value:
      • Add \(x \cdot i - \text{pref}\) to the answer (the total sum of differences between \(x\) and all preceding elements).
      • Update the prefix sum with pref += x.
3. Output the total contribution summed across all schools.

Complexity

• Time complexity: \(O\!\left(N \log N\right)\) (sorting is done per school, but since the total number of elements across all schools is \(N\), the total sorting cost is at most this)
• Space complexity: \(O(N)\) (for storing the times grouped by school)

Implementation Notes

• Grouping by school can be written concisely using dict (setdefault).

• The sum of differences can become very large, so depending on the language, 64-bit integers may be necessary (Python handles arbitrarily large integers automatically).

• By using the form ans += x * i - pref after sorting, we avoid nested loops and achieve fast computation.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    groups = {}
    for _ in range(N):
        c, l = map(int, input().split())
        groups.setdefault(c, []).append(l)

    ans = 0
    for times in groups.values():
        times.sort()
        pref = 0
        for i, x in enumerate(times):
            ans += x * i - pref
            pref += x

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.