P14668 [ICPC 2025 Seoul R] Badge Relay

A research facility operates two buildings, Left Lab and Right Lab, connected by a single secure corridor. At the beginning, all selected employees are standing in the Left Lab. - The corridor can hold at most two people at a time. - There is exactly one security badge, and every traversal of the corridor (whether by one person or two together) must be accompanied by the badge. - If two people travel together, they must walk side by side, and the traversal time is equal to the slower person's time. - If there are still employees remaining in the Left Lab after a traversal to the Right Lab, then someone in Right Lab must bring the badge back to the Left Lab before the next traversal from the Left Lab to the Right Lab can begin. To see how the strategy affects the total time, consider four employees whose individual traversal times $\{1, 2, 5, 10\}$. One possible strategy is as follows. If $(1, 2)$ traverse first (taking 2 minutes), then $(1)$ returns with the badge (1 minute), then $(1, 5)$ traverse (5 minutes), $(1)$ returns (1 minute), and finally $(1, 10)$ traverse (10 minutes), the total time is $19$ minutes. However, there is another (better) strategy; if $(1, 2)$ traverse first (2 minutes), $(1)$ returns (1 minute), then $(5, 10)$ traverse together (10 minutes), $(2)$ returns (2 minutes), and finally $(1, 2)$ traverse again (2 minutes), the total time becomes $17$ minutes, which yields a smaller total traversal time than the first. For convenience, the two crossing sequences are summarized in Tables 1 and 2 below. :::align{center} **Table 1. Sequence A (Total 19 min)** ::: | Step | Action | Left Lab (after) | Right Lab (after) | Duration (min) | Elapsed (min) | |:-:|:-:|:-:|:-:|:-:|:-:| | 0 | - | $\{1, 2, 5, 10\}$ | $\emptyset$ | - | - | | 1 | Cross $(1, 2)$ | $\{5, 10\}$ | $\{1, 2\}$ | $2$ | $2$ | | 2 | Return $(1)$ | $\{1, 5, 10\}$ | $\{2\}$ | $1$ | $3$ | | 3 | Cross $(1, 5)$ | $\{10\}$ | $\{1, 2, 5\}$ | $5$ | $8$ | | 4 | Return $(1)$ | $\{1, 10\}$ | $\{2, 5\}$ | $1$ | $9$ | | 5 | Cross $(1, 10)$ | $\emptyset$ | $\{1, 2, 5, 10\}$ | $10$ | $19$ | :::align{center} **Table 2. Sequence B (Total 17 min)** ::: | Step | Action | Left Lab (after) | Right Lab (after) | Duration (min) | Elapsed (min) | |:-:|:-:|:-:|:-:|:-:|:-:| | 0 | - | $\{1, 2, 5, 10\}$ | $\emptyset$ | - | - | | 1 | Cross $(1, 2)$ | $\{5, 10\}$ | $\{1, 2\}$ | $2$ | $2$ | | 2 | Return $(1)$ | $\{1, 5, 10\}$ | $\{2\}$ | $1$ | $3$ | | 3 | Cross $(5, 10)$ | $\{1\}$ | $\{2, 5, 10\}$ | $10$ | $13$ | | 4 | Return $(2)$ | $\{1, 2\}$ | $\{5, 10\}$ | $2$ | $15$ | | 5 | Cross $(1, 2)$ | $\emptyset$ | $\{1, 2, 5, 10\}$ | $2$ | $17$ | You are given $n$ employees. Employee $i$ needs $T_i$ minutes to traverse the corridor. You are also given $q$ queries. Each query is specified by: - an index range $[x, y]$ (inclusive), - a time range $[a, b]$ (inclusive), and - a selection cap $K$ (the maximum number of employees you may select). For each query, consider all employees whose indices lie in $[x, y]$ and whose traversal times lie in $[a, b]$. Among these employees, select the $K$ employees who have the smallest individual traversal times. If fewer than $K$ such employees exist, select all of them. These selected employees all start in the Left Lab with the single badge. Under the rules described above, you should compute the **minimum total traversal time** required for **all selected employees** to reach the Right Lab. If no employee is selected, the answer should be zero. Given $n$ employees with traversal times $T_1, \cdots, T_n$ and $q$ queries of the form $(x, y, a, b, K)$, write a program that processes the queries and outputs, for each query, the minimum total traversal time for the selected employees to move from the Left Lab to the Right Lab.

Your program is to read from standard input. The input starts with a line containing two integers $n$ and $q$ ($1 \le n, q \le 100,000$), where $n$ is the number of employees and $q$ is the number of queries. Employees are numbered from 1 to $n$. The second line contains $n$ integers $T_1, \cdots, T_n$ ($1 \le T_i \le 10^9$), where $T_i$ is the traversal time of employee $i$ ($1 \le i \le n$). Each of the following $q$ lines contains five integers $x, y, a, b, K$ described above, where $1 \le x \le y \le n$; $1 \le a \le b \le 10^9$; $1 \le K \le n$.

Your program is to write to standard output. For each query, print a single line containing the minimum total traversal time for the selected employees to move from the Left Lab to the Right Lab. If no employee is selected, output 0.

翻译由 DeepSeek V3 完成