Official Analysis (C++, Java)

Explanation

Let's start with the brute force solution.

We can iterate over all $k$ from $0…2M$ along with all pairs of intervals $(a_i, b_i)$ and $(a_j, b_j)$. For each combination, we increment our answer if $a_i + a_j \le k \le b_i + b_j$. This runs in $\mathcal{O}(MN^{2})$, which is extremely slow.

Consider the two following optimizations:

Optimization 1

Instead of considering each individual $k$, we can think of it as a pair of intervals contributing to all $k$ from $a_i + a_j$ to $b_i + b_j$. To count this efficiently, we can use difference arrays, where we do range updates by incrementing position $a_i + a_j$ by one and decrementing position $b_i + b_j + 1$ by one. This improves the time complexity to $\mathcal{O}(N^{2}+M)$.

Optimization 2

We should probably take advantage of the fact that $M$ is relatively small. Instead of looping through all pairs of left endpoints $(a_i, a_j)$ and right endpoints $(b_i, b_j)$ in $\mathcal{O}(N^2)$ time, we can iterate over all distinct left endpoint and right endpoint pairs to process multiple at once in $\mathcal{O}(M^2)$. We can then multiply the frequencies of each pair of $a_i$ values and each pair of $b_i$ values to count how many times $a_i + a_j$ and $b_i + b_j + 1$ occur among all interval pairs.

Implementation

Time Complexity: $\mathcal{O}\left(N+M^2\right)$

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

int main() {
	int n, m;
	cin >> n >> m;

	vector<pair<int, int>> intervals(n);
	for (auto &interval : intervals) { cin >> interval.first >> interval.second; }

Copy
import java.io.*;
import java.util.StringTokenizer;

public class ConvolutedIntervals {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokenizer = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(tokenizer.nextToken());
		int m = Integer.parseInt(tokenizer.nextToken());