# [A2SV G7 — Round #8](https://mirror.codeforces.com/contests)↵
↵
#### [A. Temesgen and His Books](https://mirror.codeforces.com/gym/683262/problemset/A)↵
↵
<spoiler summary="Hint">↵
What does "book with the highest number" mean? Does it mean the highest number of pages, or the highest index? Read the note carefully!↵
</spoiler>↵
↵
<spoiler summary="Observation">↵
"Book with the highest number" refers to the book's index ($1$-st, $2$-nd, $\dots$, $n$-th), not the number of pages it contains.↵
↵
When we divide the $n$ books into two non-empty piles, the absolute highest index $n$ must end up in one of the piles. Therefore, the maximum index in that pile will always be $n$, meaning Temesgen will always read the $n$-th book and read $a_n$ pages from it.↵
↵
For the other pile, we want its highest index, let's call it $k$, to have the maximum possible pages $a_k$. Can we make $k$ be any index from $1$ to $n-1$? Yes! We can simply place our chosen book $k$ into the second pile, and put all other books (including $n$) into the first pile. Thus, the second pile only contains book $k$, making $k$ its highest index.↵
↵
Therefore, the maximum total number of pages Temesgen can read is $a_n + \max(a_1, a_2, \dots, a_{n-1})$.↵
</spoiler>↵
↵
<spoiler summary="Approach">↵
<ol>↵
<li>Read the array of books $a$.</li>↵
<li>The pages from the first pile will always be $a_n$ (the last element in the array).</li>↵
<li>The pages from the second pile will be the maximum value among the first $n-1$ elements.</li>↵
<li>Add these two values together and print the sum.</li>↵
</ol>↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~python↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
# a[-1] is the n-th book↵
# max(a[:-1]) is the max pages among the first n-1 books↵
print(a[-1] + max(a[:-1]))↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
<ul>↵
<li><b>Time Complexity:</b> $O(n)$ per test case to find the maximum in the first $n-1$ elements.</li>↵
<li><b>Space Complexity:</b> $O(n)$ to store the array.</li>↵
</ul>↵
</spoiler>↵
↵
#### [B. Increasing Split of Digit String](https://mirror.codeforces.com/gym/683262/problemset/B)↵
↵
<spoiler summary="Hint">↵
There are no zeros in the string. How does the number of digits affect the integer value of a string?↵
</spoiler>↵
↵
<spoiler summary="Observation">↵
Since the digits are only from $1$ to $9$ (no leading zeros to worry about), any number with $2$ or more digits will always be strictly greater than a $1$-digit number. ↵
↵
This means if we split the string immediately after the first character, the first part has length $1$, and the second part has length $n-1$. If $n \ge 3$, the second part will have at least $2$ digits and will inherently be greater than the first part. The only edge case is when $n = 2$, where both parts have length $1$. In that case, we just need to ensure the first digit is strictly less than the second digit.↵
</spoiler>↵
↵
<spoiler summary="Approach">↵
<ol>↵
<li>If $n = 2$ and the first digit is greater than or equal to the second digit, output <code>NO</code>.</li>↵
<li>Otherwise, output <code>YES</code>, set the number of splits to $2$, and print the first character followed by the rest of the string.</li>↵
</ol>↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~python↵
q = int(input())↵
for _ in range(q):↵
n = int(input())↵
s = input().strip()↵
↵
if n == 2 and s[0] >= s[1]:↵
print("NO")↵
else:↵
print("YES")↵
print(2)↵
print(s[0], s[1:])↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
<ul>↵
<li><b>Time Complexity:</b> $O(n)$ per test case for string slicing.</li>↵
<li><b>Space Complexity:</b> $O(n)$ to store the substrings.</li>↵
</ul>↵
</spoiler>↵
↵
#### [C. Radiant Selection](https://mirror.codeforces.com/gym/683262/problemset/C)↵
↵
<spoiler summary="Hint">↵
A bulb flips its state for every divisor of its index. Which numbers have an odd number of divisors?↵
</spoiler>↵
↵
<spoiler summary="Observation">↵
A bulb $j$ starts ON and is flipped exactly $d(j)$ times, where $d(j)$ is the number of divisors of $j$. It will end up OFF if it is flipped an odd number of times.↵
↵
The only numbers with an odd number of divisors are perfect squares. Therefore, out of the first $n$ bulbs, the number of bulbs that end up OFF is exactly $\lfloor \sqrt{n} \rfloor$. This means the number of bulbs remaining ON is $n - \lfloor \sqrt{n} \rfloor$.↵
↵
Since the function $f(n) = n - \lfloor \sqrt{n} \rfloor$ is monotonically non-decreasing, we can find the minimum $n$ that yields exactly $k$ ON bulbs using binary search.↵
</spoiler>↵
↵
<spoiler summary="Approach">↵
<ol>↵
<li>Set the binary search range: <code>low = 1</code> and <code>high = 2 * 10^18</code>.</li>↵
<li>Calculate $mid$ and find how many bulbs are ON: $mid - \lfloor \sqrt{mid} \rfloor$.</li>↵
<li>If the number of ON bulbs is $\ge k$, update our answer to $mid$ and search the left half (<code>high = mid — 1</code>) to minimize $n$.</li>↵
<li>Otherwise, search the right half (<code>low = mid + 1</code>).</li>↵
</ol>↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~python↵
import math↵
import sys↵
↵
input = sys.stdin.readline↵
↵
def solve():↵
t = int(input())↵
for _ in range(t):↵
k = int(input())↵
↵
low, high = 1, 2000000000000000000↵
ans = high↵
↵
while low <= high:↵
mid = (low + high) // 2↵
on_bulbs = mid - math.isqrt(mid)↵
↵
if on_bulbs >= k:↵
ans = mid↵
high = mid - 1↵
else:↵
low = mid + 1↵
↵
print(ans)↵
↵
solve()↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
<ul>↵
<li><b>Time Complexity:</b> $O(\log(\text{MAX\_N}))$ per query. With $MAX\_N \approx 2 \cdot 10^{18}$, this takes around 60 iterations, making it extremely fast overall.</li>↵
<li><b>Space Complexity:</b> $O(1)$.</li>↵
</ul>↵
</spoiler>↵
↵
#### [D. Array Harmonization](https://mirror.codeforces.com/gym/683262/problemset/D)↵
↵
<spoiler summary="Hint">↵
If you know the maximum number of elements $k$ you can keep in the array, which elements from array $a$ and array $b$ should you pick to maximize the chances that $a_i < b_i$?↵
</spoiler>↵
↵
<spoiler summary="Observation">↵
To minimize the number of operations (deletions), we need to maximize the final array length $k$. ↵
To maximize the probability of forming $k$ valid pairs $(a_i, b_i)$ where $a_i < b_i$, we should pair the $k$ **smallest** elements of array $a$ with the $k$ **largest** elements of array $b$.↵
↵
Notice that $m=1$ in the constraints, so we only need to consider the case where the first element of $a$ is set to $1$. Once $a$ is updated and both arrays are sorted, the property of "being able to form $k$ pairs" is monotonic. If we can form $k$ pairs, we can also form $k-1$ pairs. Thus, we can use binary search on the answer!↵
</spoiler>↵
↵
<spoiler summary="Approach">↵
<ol>↵
<li>Construct array $a$ by prepending $1$ to the given $n-1$ elements.</li>↵
<li>Sort both array $a$ and array $b$ in ascending order.</li>↵
<li>Binary search the maximum possible $k$ in the range $[0, n]$.</li>↵
<li>To check if a specific $k$ is valid: compare the first $k$ elements of $a$ with the last $k$ elements of $b$. If $a[i] < b[n - k + i]$ holds true for all $0 \le i < k$, then this $k$ is valid.</li>↵
<li>If valid, try to look for a larger $k$ by searching the right half. Otherwise, search the left half.</li>↵
<li>The minimum operations needed will be the total elements minus the maximum paired ones: $n - k$.</li>↵
</ol>↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~python↵
import sys↵
↵
input = sys.stdin.readline↵
↵
def solve():↵
t = int(input())↵
for _ in range(t):↵
n, m = map(int, input().split())↵
a = [1] + list(map(int, input().split()))↵
b = list(map(int, input().split()))↵
↵
a.sort()↵
b.sort()↵
↵
def check(k):↵
# check if first k elements of 'a' are strictly less than the last k elements of 'b'↵
for i in range(k):↵
if a[i] >= b[n - k + i]:↵
return False↵
return True↵
↵
low, high = 0, n↵
max_k = 0↵
↵
while low <= high:↵
mid = (low + high) // 2↵
if check(mid):↵
max_k = mid # valid, store answer↵
low = mid + 1 # try to find a larger k↵
else:↵
high = mid - 1 # invalid, try a smaller k↵
↵
# the minimum deletions is n minus the max elements we could keep↵
print(n - max_k)↵
↵
solve()↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
<ul>↵
<li><b>Time Complexity:</b> $O(n \log n)$. Sorting both arrays takes $O(n \log n)$. The binary search iterates $\log n$ times, and each `check` function takes $O(n)$ time in the worst case, contributing another $O(n \log n)$.</li>↵
<li><b>Space Complexity:</b> $O(n)$ to store the inputs.</li>↵
</ul>↵
</spoiler>↵
↵
#### [E. Strategic Vacation Planning](https://mirror.codeforces.com/gym/683262/problemset/E)↵
↵
<spoiler summary="Hint">↵
For a given voucher, you need another non-overlapping voucher with a specific remaining duration that has the minimum possible cost. How can you efficiently query this using binary search?↵
</spoiler>↵
↵
<spoiler summary="Observation">↵
Since the two chosen vouchers must equal exactly $x$ in total duration, a voucher of duration $dur$ strictly requires a partner voucher of duration $x - dur$. ↵
↵
We can group all the vouchers by their duration. Inside each group, if we sort the vouchers by their start time $l$, we can quickly find a non-overlapping partner! Specifically, for a voucher ending at $r_i$, we can binary search (using `bisect_right`) in the target duration group for the first voucher whose start time $l_j$ is strictly greater than $r_i$. ↵
↵
To quickly get the minimum cost among all valid partners that start at or after this index, we can precalculate a `suffix minimums` array for costs in each duration group.↵
</spoiler>↵
↵
<spoiler summary="Approach">↵
<ol>↵
<li>Group all vouchers in a dictionary mapped by their duration: $r - l + 1$.</li>↵
<li>For each duration group, sort the vouchers by their start time $l$.</li>↵
<li>For each sorted group, create an array of just the start times (to be used for binary search) and a `suffix_mins` array that stores the minimum cost from that index to the end of the group.</li>↵
<li>Iterate over all vouchers. For a voucher with duration $dur$, end time $r$, and cost $c$, the target complementary duration is $rem = x - dur$.</li>↵
<li>If the $rem$ group exists, use binary search to find the first index where the start time is $> r$.</li>↵
<li>If such an index exists, add $c$ to the value in the `suffix_mins` at that index, and update the global minimum total cost.</li>↵
<li>If the global minimum remains infinity, output <code>-1</code>.</li>↵
</ol>↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~python↵
import sys↵
from bisect import bisect_right↵
from collections import defaultdict↵
↵
input = sys.stdin.readline↵
↵
def solve():↵
n, x = map(int, input().split())↵
↵
vouchers = []↵
groups = defaultdict(list)↵
↵
for _ in range(n):↵
l, r, cost = map(int, input().split())↵
dur = r - l + 1↵
vouchers.append((l, r, cost, dur))↵
groups[dur].append((l, r, cost))↵
↵
start_times = {}↵
suffix_mins = {}↵
↵
# Sort each duration group and build suffix minimums for O(1) minimum queries↵
for dur in groups:↵
groups[dur].sort(key=lambda v: v[0])↵
st = [v[0] for v in groups[dur]]↵
start_times[dur] = st↵
↵
# Build suffix minimums↵
sm = [0] * len(st)↵
sm[-1] = groups[dur][-1][2]↵
for i in range(len(st)-2, -1, -1):↵
sm[i] = min(sm[i+1], groups[dur][i][2])↵
suffix_mins[dur] = sm↵
↵
ans = float('inf')↵
↵
for l, r, cost, dur in vouchers:↵
rem = x - dur↵
↵
if rem in groups:↵
st = start_times[rem]↵
# Binary search for the first valid voucher that starts after this one ends↵
pos = bisect_right(st, r)↵
↵
if pos < len(st):↵
ans = min(ans, cost + suffix_mins[rem][pos])↵
↵
print(ans if ans != float('inf') else -1)↵
↵
solve()↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
<ul>↵
<li><b>Time Complexity:</b> $O(n \log n)$. Grouping and sorting the vouchers takes $O(n \log n)$. Iterating through $n$ vouchers and performing a binary search on the start times takes $O(n \log n)$ as well.</li>↵
<li><b>Space Complexity:</b> $O(n)$ to store the dictionary groups, start times, and suffix minimums.</li>↵
</ul>↵
</spoiler>↵
↵
↵
#### [A. Temesgen and His Books](https://mirror.codeforces.com/gym/683262/problem
↵
<spoiler summary="Hint">↵
What does "book with the highest number" mean? Does it mean the highest number of pages, or the highest index? Read the note carefully!↵
</spoiler>↵
↵
<spoiler summary="Observation">↵
"Book with the highest number" refers to the book's index ($1$-st, $2$-nd, $\dots$, $n$-th), not the number of pages it contains.↵
↵
When we divide the $n$ books into two non-empty piles, the absolute highest index $n$ must end up in one of the piles. Therefore, the maximum index in that pile will always be $n$, meaning Temesgen will always read the $n$-th book and read $a_n$ pages from it.↵
↵
For the other pile, we want its highest index, let's call it $k$, to have the maximum possible pages $a_k$. Can we make $k$ be any index from $1$ to $n-1$? Yes! We can simply place our chosen book $k$ into the second pile, and put all other books (including $n$) into the first pile. Thus, the second pile only contains book $k$, making $k$ its highest index.↵
↵
Therefore, the maximum total number of pages Temesgen can read is $a_n + \max(a_1, a_2, \dots, a_{n-1})$.↵
</spoiler>↵
↵
<spoiler summary="Approach">↵
<ol>↵
<li>Read the array of books $a$.</li>↵
<li>The pages from the first pile will always be $a_n$ (the last element in the array).</li>↵
<li>The pages from the second pile will be the maximum value among the first $n-1$ elements.</li>↵
<li>Add these two values together and print the sum.</li>↵
</ol>↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~python↵
t = int(input())↵
for _ in range(t):↵
n = int(input())↵
a = list(map(int, input().split()))↵
↵
# a[-1] is the n-th book↵
# max(a[:-1]) is the max pages among the first n-1 books↵
print(a[-1] + max(a[:-1]))↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
<ul>↵
<li><b>Time Complexity:</b> $O(n)$ per test case to find the maximum in the first $n-1$ elements.</li>↵
<li><b>Space Complexity:</b> $O(n)$ to store the array.</li>↵
</ul>↵
</spoiler>↵
↵
#### [B. Increasing Split of Digit String](https://mirror.codeforces.com/gym/683262/problem
↵
<spoiler summary="Hint">↵
There are no zeros in the string. How does the number of digits affect the integer value of a string?↵
</spoiler>↵
↵
<spoiler summary="Observation">↵
Since the digits are only from $1$ to $9$ (no leading zeros to worry about), any number with $2$ or more digits will always be strictly greater than a $1$-digit number. ↵
↵
This means if we split the string immediately after the first character, the first part has length $1$, and the second part has length $n-1$. If $n \ge 3$, the second part will have at least $2$ digits and will inherently be greater than the first part. The only edge case is when $n = 2$, where both parts have length $1$. In that case, we just need to ensure the first digit is strictly less than the second digit.↵
</spoiler>↵
↵
<spoiler summary="Approach">↵
<ol>↵
<li>If $n = 2$ and the first digit is greater than or equal to the second digit, output <code>NO</code>.</li>↵
<li>Otherwise, output <code>YES</code>, set the number of splits to $2$, and print the first character followed by the rest of the string.</li>↵
</ol>↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~python↵
q = int(input())↵
for _ in range(q):↵
n = int(input())↵
s = input().strip()↵
↵
if n == 2 and s[0] >= s[1]:↵
print("NO")↵
else:↵
print("YES")↵
print(2)↵
print(s[0], s[1:])↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
<ul>↵
<li><b>Time Complexity:</b> $O(n)$ per test case for string slicing.</li>↵
<li><b>Space Complexity:</b> $O(n)$ to store the substrings.</li>↵
</ul>↵
</spoiler>↵
↵
#### [C. Radiant Selection](https://mirror.codeforces.com/gym/683262/problem
↵
<spoiler summary="Hint">↵
A bulb flips its state for every divisor of its index. Which numbers have an odd number of divisors?↵
</spoiler>↵
↵
<spoiler summary="Observation">↵
A bulb $j$ starts ON and is flipped exactly $d(j)$ times, where $d(j)$ is the number of divisors of $j$. It will end up OFF if it is flipped an odd number of times.↵
↵
The only numbers with an odd number of divisors are perfect squares. Therefore, out of the first $n$ bulbs, the number of bulbs that end up OFF is exactly $\lfloor \sqrt{n} \rfloor$. This means the number of bulbs remaining ON is $n - \lfloor \sqrt{n} \rfloor$.↵
↵
Since the function $f(n) = n - \lfloor \sqrt{n} \rfloor$ is monotonically non-decreasing, we can find the minimum $n$ that yields exactly $k$ ON bulbs using binary search.↵
</spoiler>↵
↵
<spoiler summary="Approach">↵
<ol>↵
<li>Set the binary search range: <code>low = 1</code> and <code>high = 2 * 10^18</code>.</li>↵
<li>Calculate $mid$ and find how many bulbs are ON: $mid - \lfloor \sqrt{mid} \rfloor$.</li>↵
<li>If the number of ON bulbs is $\ge k$, update our answer to $mid$ and search the left half (<code>high = mid — 1</code>) to minimize $n$.</li>↵
<li>Otherwise, search the right half (<code>low = mid + 1</code>).</li>↵
</ol>↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~python↵
import math↵
import sys↵
↵
input = sys.stdin.readline↵
↵
def solve():↵
t = int(input())↵
for _ in range(t):↵
k = int(input())↵
↵
low, high = 1, 2000000000000000000↵
ans = high↵
↵
while low <= high:↵
mid = (low + high) // 2↵
on_bulbs = mid - math.isqrt(mid)↵
↵
if on_bulbs >= k:↵
ans = mid↵
high = mid - 1↵
else:↵
low = mid + 1↵
↵
print(ans)↵
↵
solve()↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
<ul>↵
<li><b>Time Complexity:</b> $O(\log(\text{MAX\_N}))$ per query. With $MAX\_N \approx 2 \cdot 10^{18}$, this takes around 60 iterations, making it extremely fast overall.</li>↵
<li><b>Space Complexity:</b> $O(1)$.</li>↵
</ul>↵
</spoiler>↵
↵
#### [D. Array Harmonization](https://mirror.codeforces.com/gym/683262/problem
↵
<spoiler summary="Hint">↵
If you know the maximum number of elements $k$ you can keep in the array, which elements from array $a$ and array $b$ should you pick to maximize the chances that $a_i < b_i$?↵
</spoiler>↵
↵
<spoiler summary="Observation">↵
To minimize the number of operations (deletions), we need to maximize the final array length $k$. ↵
To maximize the probability of forming $k$ valid pairs $(a_i, b_i)$ where $a_i < b_i$, we should pair the $k$ **smallest** elements of array $a$ with the $k$ **largest** elements of array $b$.↵
↵
Notice that $m=1$ in the constraints, so we only need to consider the case where the first element of $a$ is set to $1$. Once $a$ is updated and both arrays are sorted, the property of "being able to form $k$ pairs" is monotonic. If we can form $k$ pairs, we can also form $k-1$ pairs. Thus, we can use binary search on the answer!↵
</spoiler>↵
↵
<spoiler summary="Approach">↵
<ol>↵
<li>Construct array $a$ by prepending $1$ to the given $n-1$ elements.</li>↵
<li>Sort both array $a$ and array $b$ in ascending order.</li>↵
<li>Binary search the maximum possible $k$ in the range $[0, n]$.</li>↵
<li>To check if a specific $k$ is valid: compare the first $k$ elements of $a$ with the last $k$ elements of $b$. If $a[i] < b[n - k + i]$ holds true for all $0 \le i < k$, then this $k$ is valid.</li>↵
<li>If valid, try to look for a larger $k$ by searching the right half. Otherwise, search the left half.</li>↵
<li>The minimum operations needed will be the total elements minus the maximum paired ones: $n - k$.</li>↵
</ol>↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~python↵
import sys↵
↵
input = sys.stdin.readline↵
↵
def solve():↵
t = int(input())↵
for _ in range(t):↵
n, m = map(int, input().split())↵
a = [1] + list(map(int, input().split()))↵
b = list(map(int, input().split()))↵
↵
a.sort()↵
b.sort()↵
↵
def check(k):↵
# check if first k elements of 'a' are strictly less than the last k elements of 'b'↵
for i in range(k):↵
if a[i] >= b[n - k + i]:↵
return False↵
return True↵
↵
low, high = 0, n↵
max_k = 0↵
↵
while low <= high:↵
mid = (low + high) // 2↵
if check(mid):↵
max_k = mid # valid, store answer↵
low = mid + 1 # try to find a larger k↵
else:↵
high = mid - 1 # invalid, try a smaller k↵
↵
# the minimum deletions is n minus the max elements we could keep↵
print(n - max_k)↵
↵
solve()↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
<ul>↵
<li><b>Time Complexity:</b> $O(n \log n)$. Sorting both arrays takes $O(n \log n)$. The binary search iterates $\log n$ times, and each `check` function takes $O(n)$ time in the worst case, contributing another $O(n \log n)$.</li>↵
<li><b>Space Complexity:</b> $O(n)$ to store the inputs.</li>↵
</ul>↵
</spoiler>↵
↵
#### [E. Strategic Vacation Planning](https://mirror.codeforces.com/gym/683262/problem
↵
<spoiler summary="Hint">↵
For a given voucher, you need another non-overlapping voucher with a specific remaining duration that has the minimum possible cost. How can you efficiently query this using binary search?↵
</spoiler>↵
↵
<spoiler summary="Observation">↵
Since the two chosen vouchers must equal exactly $x$ in total duration, a voucher of duration $dur$ strictly requires a partner voucher of duration $x - dur$. ↵
↵
We can group all the vouchers by their duration. Inside each group, if we sort the vouchers by their start time $l$, we can quickly find a non-overlapping partner! Specifically, for a voucher ending at $r_i$, we can binary search (using `bisect_right`) in the target duration group for the first voucher whose start time $l_j$ is strictly greater than $r_i$. ↵
↵
To quickly get the minimum cost among all valid partners that start at or after this index, we can precalculate a `suffix minimums` array for costs in each duration group.↵
</spoiler>↵
↵
<spoiler summary="Approach">↵
<ol>↵
<li>Group all vouchers in a dictionary mapped by their duration: $r - l + 1$.</li>↵
<li>For each duration group, sort the vouchers by their start time $l$.</li>↵
<li>For each sorted group, create an array of just the start times (to be used for binary search) and a `suffix_mins` array that stores the minimum cost from that index to the end of the group.</li>↵
<li>Iterate over all vouchers. For a voucher with duration $dur$, end time $r$, and cost $c$, the target complementary duration is $rem = x - dur$.</li>↵
<li>If the $rem$ group exists, use binary search to find the first index where the start time is $> r$.</li>↵
<li>If such an index exists, add $c$ to the value in the `suffix_mins` at that index, and update the global minimum total cost.</li>↵
<li>If the global minimum remains infinity, output <code>-1</code>.</li>↵
</ol>↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~python↵
import sys↵
from bisect import bisect_right↵
from collections import defaultdict↵
↵
input = sys.stdin.readline↵
↵
def solve():↵
n, x = map(int, input().split())↵
↵
vouchers = []↵
groups = defaultdict(list)↵
↵
for _ in range(n):↵
l, r, cost = map(int, input().split())↵
dur = r - l + 1↵
vouchers.append((l, r, cost, dur))↵
groups[dur].append((l, r, cost))↵
↵
start_times = {}↵
suffix_mins = {}↵
↵
# Sort each duration group and build suffix minimums for O(1) minimum queries↵
for dur in groups:↵
groups[dur].sort(key=lambda v: v[0])↵
st = [v[0] for v in groups[dur]]↵
start_times[dur] = st↵
↵
# Build suffix minimums↵
sm = [0] * len(st)↵
sm[-1] = groups[dur][-1][2]↵
for i in range(len(st)-2, -1, -1):↵
sm[i] = min(sm[i+1], groups[dur][i][2])↵
suffix_mins[dur] = sm↵
↵
ans = float('inf')↵
↵
for l, r, cost, dur in vouchers:↵
rem = x - dur↵
↵
if rem in groups:↵
st = start_times[rem]↵
# Binary search for the first valid voucher that starts after this one ends↵
pos = bisect_right(st, r)↵
↵
if pos < len(st):↵
ans = min(ans, cost + suffix_mins[rem][pos])↵
↵
print(ans if ans != float('inf') else -1)↵
↵
solve()↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Complexity Analysis">↵
<ul>↵
<li><b>Time Complexity:</b> $O(n \log n)$. Grouping and sorting the vouchers takes $O(n \log n)$. Iterating through $n$ vouchers and performing a binary search on the start times takes $O(n \log n)$ as well.</li>↵
<li><b>Space Complexity:</b> $O(n)$ to store the dictionary groups, start times, and suffix minimums.</li>↵
</ul>↵
</spoiler>↵
↵
