USACO 2021 December Contest Silver Division - Convoluted Intervals

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We use the size of \(M\) and make frequency arrays on the ends of the intervals. In \(M^2\) we can calculate for each pair of start and end for which starts and which ends are good. At the end for each \(i\) we add to the answer the number of good starts at \(i\) and print it, and then we subtract the number of good ends at \(i\).

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>
using namespace std;

signed main() {

    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> sets(n);
    vector<long long> freq_fi(m + 5);
    vector<long long> freq_se(m + 5);
    for (int i = 0; i < n; i++) {
        cin >> sets[i].first >> sets[i].second;
        freq_fi[sets[i].first]++;
        freq_se[sets[i].second]++;
    }

    vector<long long> pre(2 * m + 5);
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= m; j++) {
            pre[i + j + 1] += freq_fi[i] * freq_fi[j];
            pre[i + j + 2] -= freq_se[i] * freq_se[j];
        }
    }
    for (int i = 1; i <= 2 * m + 1; i++) {
        pre[i] += pre[i - 1];
        cout << pre[i] << '\n';
    }

    return 0;
}