Convoluted Intervals

    1#include <bits/stdc++.h>
    2using namespace std;
    3#define int long long
    4int l[5001], r[5001], psa[5001 * 2];
    5signed main(){
    6    ios::sync_with_stdio(0); cin.tie(0);
    7    int n, m; cin >> n >> m;
    8    for(int i = 0; i < n; i++){int a, b; cin >> a >> b; l[a]++; r[b]++;}
    9    int k = 2 * m;
    10    for(int i = 0; i <= m; i++){
    11        for(int j = 0; j <= m; j++){
    12            psa[i + j] += l[i] * l[j];
    13            psa[i + j + 1] -= r[i] * r[j];
    14        } 
    15    }
    16    cout << psa[0] << '\n';
    17    for(int i = 1; i <= k; i++){
    18        psa[i] = psa[i] + psa[i - 1];
    19        cout << psa[i] << '\n';
    20    }
    21    return 0;
    22}