Background

Original link: https://oier.team/problems/X5G.

Abiogenesis - Juggernaut.

This problem is adapted from Codeforces 1981 E. Turtle and Intersected Segments.

Problem Description

You are given $n$ segments $[l_i, r_i]$. The $i$-th segment has a pair of weights $a_i, b_i$.

There is an undirected graph $G$ that initially has $n$ vertices and $0$ edges. For every pair of positive integers $i, j$ such that $1 \le i < j \le n$, if segments $i$ and $j$ intersect, then add an edge in $G$ with endpoints $i$ and $j$, and edge weight $a_i + a_j + |b_i - b_j|$.

Find the sum of edge weights of a minimum spanning tree of $G$, or report that $G$ is disconnected.

Two segments $[l_1, r_1]$ and $[l_2, r_2]$ are considered intersecting if $\max(l_1, l_2) \le \min(r_1, r_2)$.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case:

The first line contains a positive integer $n$, the number of segments.

Each of the next $n$ lines, the $i$-th line contains four positive integers $l_i, r_i, a_i, b_i$.

Output Format

For each test case, output one integer per line, the sum of edge weights of a minimum spanning tree of $G$. In particular, if $G$ is disconnected, output $-1$.

4
5
1 7 1 3
2 4 2 6
3 5 3 5
6 7 2 9
3 4 1 4
5
2 7 3 3
1 3 5 6
4 5 3 5
6 7 1 9
1 1 5 4
4
1 4 1 3
1 2 2 1
3 4 3 5
1 4 4 4
3
1 3 1 1
2 3 1 3
4 5 1 8

22
41
17
-1

Hint

Sample Explanation

For the first test case, the graph $G$ looks like this:

One possible minimum spanning tree of $G$ looks like this:

Constraints

This problem uses bundled testdata and has subtask dependencies enabled.

• Special Property A: $\forall i \in [1, n], l_i = 1$.
• Special Property B: $\forall i \in [1, n - 1], l_i \le l_{i + 1}, r_i \le r_{i + 1}$.
• Special Property C: $\forall i \in [1, n], b_i = 1$.
• Special Property D: $\forall i \in [1, n], a_i = b_i$.

For all testdata, it holds that $1 \le T \le 10^4$, $1 \le n, \sum n \le 10^5$, $1 \le l_i, r_i, a_i, b_i \le 10^8$, and $l_i \le r_i$.

Translated by ChatGPT 5