P11134 [MX-X5-T6] "GFOI Round 1" Abiogenesis

Original link: . --- > [Abiogenesis - Juggernaut.](https://music.163.com/#/song?id=1416321652) This problem is adapted from [Codeforces 1981 E. Turtle and Intersected Segments](https://codeforces.com/contest/1981/problem/E).

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)$.

**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$.

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$.

**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.** | Subtask ID | $n \le$ | $\sum n \le$ | Special Property | Dependencies | Score | | :-: | :-: | :-: | :-: | :-: | :-: | | $1$ | $100$ | $10^5$ | None | None | $11$ | | $2$ | $10^5$ | $10^5$ | AC | None | $5$ | | $3$ | $10^5$ | $10^5$ | A | $2$ | $14$ | | $4$ | $10^5$ | $10^5$ | B | None | $14$ | | $5$ | $10^5$ | $10^5$ | C | $2$ | $14$ | | $6$ | $10^5$ | $10^5$ | D | None | $14$ | | $7$ | $10^5$ | $10^5$ | None | $1, 2, 3, 4, 5, 6$ | $28$ | - 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