We hope you liked the problems.↵
↵
[problem:1859A]↵
↵
<spoiler summary="Hints">↵
↵
<spoiler summary="Hint 1">↵
What does it mean that $A$ divides $B$?↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
First, if all numbers are equal, then there is no answer (since $a$ is divisible by $a$, if both arrays are non-empty, then $c_1$ is a divisor of $b_1$).↵
↵
Second, if $a$ is divisible by $b$ and they are both natural numbers, then the following equality holds: $b \le a$ (by definition, if $a$ is divisible by $b$, then $a$ can be represented as $k \dot b$, where $k$ is a natural number).↵
↵
Now we can place all instances of the smallest number into $b$, and all other numbers into $c$. It can be seen that such a construction always gives a valid answer.↵
</spoiler>↵
↵
↵
<spoiler summary="Author's code">↵
```c++↵
#include <iostream>↵
#include <algorithm>↵
#include <vector>↵
using namespace std;↵
↵
void solve() {↵
int n = 0; cin >> n; ↵
vector<int> inp; inp.assign(n, 0);↵
for (auto& x : inp) cin >> x;↵
sort(inp.begin(), inp.end());↵
if (inp.back() == inp[0]) {↵
cout << "-1\n";↵
return;↵
}↵
else {↵
int it = 0;↵
while (inp[it] == inp[0]) it++;↵
cout << it << " " << n - it << "\n";↵
for (int j = 0; j < it; ++j) cout << inp[j] << " ";↵
for (int j = it; j < n; ++j) cout << inp[j] << " ";↵
}↵
}↵
↵
int main() {↵
int t = 0; cin >> t;↵
while (t--) solve();↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
[problem:1859B]↵
↵
<spoiler summary="Hints">↵
↵
<spoiler summary="Hint 1">↵
Do all numbers in a single array really matter?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If only the first minimum and the second minimum matter, what is the only way to increase a single array's beauty?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
What can we say about the array which will have the smallest number in the end?↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
To increase the answer for each array separately, it is necessary to move the minimum to another array. Then, notice that it is optimal to move all the minimums to one array. Let's figure out which array. After moving the minimum from an array, the second minimum in the original array becomes the new minimum. Then, it is easy to notice that it is optimal to move all the minimums to the array with the smallest second minimum. After all the movements, we will have one array where the minimum element is the smallest number among all the arrays, and $n-1$ arrays where the minimum element is the second minimum in the original array.↵
↵
Therefore, the answer to the problem will be $M + K - S$, where $M$ is the minimum element among all the arrays, $K$ is the sum of all the second minimums, and $S$ is the smallest second minimum.↵
</spoiler>↵
↵
↵
<spoiler summary="Author's code">↵
```c++↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
#include <numeric>↵
↵
using namespace std;↵
↵
#define all(v) v.begin(), v.end()↵
↵
typedef long long ll;↵
↵
const int INF = 1e9 + 7;↵
↵
void solve() {↵
int n;↵
cin >> n;↵
↵
int minn = INF;↵
vector<int> min2;↵
for (int i = 0 ; i < n ; i++) {↵
int m;↵
cin >> m;↵
vector<int> v(m);↵
for (auto &el : v) cin >> el;↵
↵
int minel = *min_element(all(v));↵
minn = min(minn, minel);↵
v.erase(find(all(v), minel));↵
min2.push_back(*min_element(all(v)));↵
}↵
cout << minn + (ll) accumulate(all(min2), 0ll) - *min_element(all(min2)) << "\n";↵
}↵
↵
signed main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
#ifdef LOCAL↵
freopen("a.in", "r", stdin);↵
#endif↵
↵
int t = 1;↵
cin >> t;↵
while (t--)↵
solve();↵
↵
return 0;↵
}↵
↵
```↵
</spoiler>↵
↵
[problem:1859C]↵
↵
<spoiler summary="Hints">↵
↵
<spoiler summary="Hint 1">↵
What if we fix the maximum element in the resulting array?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Try using greedy.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Optimize the log factor away by noticing a certain fact.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
Let's fix the maximum element in an array — let it be $M$. Now, let's iterate from $n$ to $1$. Let the current chosen number be $i$. I claim that if we maintain the remaining available numbers to multiply by, then it is optimal to take the maximum such number $x$ that $x * i \le M$. ↵
↵
Proof: let's say that this is not correct. Then, let's say that we pair $i$ with another number $x1$, and $x$ gets paired with some other number $i1$. Then, $i1 < i$, because it was chosen later, and $x1 < x$ (otherwise $i * x1 > M$). Now let's swap $x$ with $x1$. The sum is increased by $i * x - i * x1 - i1 * x + i1 * x1 = (i - i1)(x - x1) > 0$, and all of the numbers are less or equal to $M$.↵
↵
Now the task can be solved in $O(N^3logN)$ by simply iterating on the maximum from $N^2$ to $1$, while maintaining the remaining numbers with a set. In order to squeeze it in the TL, you can only consider such maximums that they can be represented as $i * j, 1 \le i, j \le n$.↵
↵
In order to optimize it to $O(N^3)$, let's notice that for each number $x$, it can be paired with any number from $1$ to $\frac{M} {x}$. Now just maintain a stack of all available elements at the current moment, add all numbers that possible, and pop the maximum number for all $i$ from $1$ to $N$.↵
</spoiler>↵
↵
↵
<spoiler summary="Author's code">↵
```c++↵
#include <iostream>↵
#include <algorithm>↵
#include <set>↵
#include <stack>↵
#include <vector>↵
using namespace std;↵
void solve() {↵
int N = 0; cin >> N;↵
int ans = 0;↵
vector<int> pr;↵
pr.assign(N * N, -1);↵
for (int i = 1; i <= N; ++i) {↵
for (int j = 1; j <= N; ++j) {↵
pr[i * j - 1] = 1;↵
}↵
}↵
for (int mx = N * N; mx >= 1; --mx) {↵
if (pr[mx - 1] == -1) continue;↵
vector<vector<int>> a;↵
int curans = -mx;↵
bool br = false;↵
a.assign(N, vector<int>());↵
for (int j = N; j >= 1; --j) {↵
int num = min(mx / j, N);↵
if (num < 1) {↵
br = true;↵
break;↵
}↵
a[num - 1].push_back(j);↵
}↵
if (br) break;↵
stack<int> s;↵
for (int i = 0; i < N; ++i) {↵
s.push(i + 1);↵
bool brk = false;↵
for (auto x : a[i]) {↵
if (s.empty()) {↵
brk = true; break;↵
}↵
curans += s.top() * x;↵
s.pop();↵
}↵
if (brk) break;↵
}↵
ans = max(ans, curans);↵
}↵
cout << ans << "\n";↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int t = 0; cin >> t;↵
while (t--) solve();↵
return 0;↵
}↵
↵
```↵
</spoiler>↵
↵
[problem:1859D]↵
↵
<spoiler summary="Hints">↵
↵
<spoiler summary="Hint 1">↵
What if we use greedy a bit?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Where it is always beneficial to teleport?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Use scanline↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
Statement: It is always beneficial to teleport to point $b_i$.↵
↵
Proof: Let's assume that we were able to teleport from point $X$ to the right of $b_i$, but not from $b_i$. Then we used some segment $A$ that covers point $X$, but does not cover point $b$, and ends to the right of $b$. This is a contradiction.↵
↵
Let $ans_i$ be the maximum coordinate we can reach while being on segment $i$, and let $p_j$ be the answer to the $j$-th query. Then we notice that the answer to query $p_j = \max(x_j, \max_{i = 1}^n \{ans_i \vert l_i \le x_j \le r_i\})$.↵
↵
We will use the scanline method from the end. Events: $l_i$, $b_i$, $r_i$, $x_j$.↵
↵
We notice that events of type $r_i$ are not important to us when scanning from the end (according to statement number 1). It is important for us that we process events of type $b_i$ first, then events of type $x_j$, and then events of type $l_i$ (closing the segment in the scanline).↵
↵
We will go through the events of the scanline, processing them in the order of $b_i$, then events of type $x_j$, and then events of type $l_i$.↵
↵
We assume that there is a data structure that allows us to add elements, remove elements, and quickly output the maximum.↵
↵
↵
- For each event of type $b_i$, update the value of $ans_i$ — take the maximum value of $ans$ of all open segments from the structure.↵
↵
- For each event of type $x_j$, update the value of $p_j$ — take the maximum value of $ans$ of all open segments from the structure, as well as $x_j$.↵
↵
- For each event of type $l_i$, remove $ans_i$ from the structure.↵
↵
↵
We notice that to solve this problem, we can use the std::multiset} container, which automatically sorts elements in ascending order. We can store in $multiset$ $ans_i$ of all open segments. And then, when processing events, extract the maximum from $multiset$, all operations are performed in $O(\log n)$. This allows us to solve the problem in $O((n + q) \log n)$ time and $O(n)$ memory.↵
</spoiler>↵
↵
↵
<spoiler summary="Author's code">↵
```c++↵
#include <iostream>↵
#include <vector>↵
#include <set>↵
#include <iomanip>↵
#include <cmath>↵
#include <algorithm>↵
#include <map>↵
#include <stack>↵
#include <cassert>↵
#include <unordered_map>↵
#include <bitset>↵
#include <random>↵
#include <unordered_set>↵
#include <chrono>↵
↵
using namespace std;↵
↵
#define all(a) a.begin(), a.end()↵
↵
void solve() {↵
int n;↵
cin >> n;↵
↵
vector<int> ans(n);↵
vector<tuple<int, int, int>> events;↵
for (int i = 0 ; i < n ; i++) {↵
int l, r, a, b;↵
cin >> l >> r >> a >> b;↵
ans[i] = b;↵
events.emplace_back(b, 1, i);↵
events.emplace_back(l, -1, i);↵
}↵
int q;↵
cin >> q;↵
vector<int> queries(q);↵
for (int i = 0 ; i < q ; i++) {↵
int x;↵
cin >> x;↵
queries[i] = x;↵
events.emplace_back(x, 0, i);↵
}↵
↵
sort(all(events));↵
reverse(all(events));↵
multiset<int> s;↵
for (auto [x, type, ind] : events) {↵
if (type == 1) {↵
if (!s.empty()) {↵
ans[ind] = *s.rbegin();↵
}↵
s.insert(ans[ind]);↵
} else if (type == 0) {↵
if (!s.empty()) {↵
queries[ind] = max(queries[ind], *s.rbegin());↵
}↵
} else {↵
s.extract(ans[ind]);↵
}↵
}↵
↵
for (auto el : queries)↵
cout << el << " ";↵
cout << "\n";↵
}↵
↵
signed main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t = 1;↵
cin >> t;↵
while (t--)↵
solve();↵
↵
return 0;↵
}↵
↵
```↵
</spoiler>↵
↵
[problem:1859E]↵
↵
<spoiler summary="Hints">↵
↵
<spoiler summary="Hint 1">↵
Maybe we can relax some conditions?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Do we really need to always correctly calculate all sums?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Optimize the obvious dp.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Let's call the value of a segment $[l; r]$ $f(l, r) = abs(a_l - b_r) + abs(a_r - b_l)$.↵
↵
Let's write $dp[n1][k1]$ — maximum value of segments of total length $k1$ that end before $n1$.↵
↵
The obvious way to recalc is the following:↵
↵
$dp[n1][k1] = max(dp[n1 - 1][k1], dp[n1 - l][k1 - l] + f(n1 - l + 1, n1), 1 \le l \le k1)$.↵
↵
This works in $O(NK^2)$ and is too slow.↵
↵
Now let's consider the following: instead of getting the absolute value of segment $[l; r]$, we consider the maximum of the following four combinations: $b_l - a_r + b_r - a_l$, $b_l - a_r - b_r + a_l$, $-b_l + a_r + b_r - a_l$, $-b_l + a_r - b_r + a_l$. We can see that this always gives us the correct answer to the absolute value, since we check all of the possibilities.↵
↵
Now we can look at out dp states as a table, and notice that we recalc over the diagonal (we recalc over all states that have the same value of n1 — k1). ↵
↵
Now, for each "diagonal", we maintain four maximum combinations: $dp[n1][k1] + b_{k1} + a_{k1}, dp[n1][k1] - b_{k1} + a_{k1}, dp[n1][k1] + b_{k1} - a_{k1}, dp[n1][k1] - b_{k1} - a_{k1}$, and when we want to recalc state $dp[n2][k2]$, we just consider all of the four possibilities.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Author's code">↵
```c++↵
#include <iostream>↵
#include <vector>↵
using namespace std;↵
const long long INF = 1e18;↵
#define int long long↵
↵
void solve() {↵
int N = 0, K = 0; cin >> N >> K;↵
vector<int> a;↵
vector<int> b;↵
a.assign(N, 0);↵
b.assign(N, 0);↵
for (int i = 0; i < N; ++i) {↵
cin >> a[i];↵
}↵
for (int i = 0; i < N; ++i) {↵
cin >> b[i];↵
}↵
vector<long long> mx1; // max of (b_l + a_l) + corresponding dp↵
vector<long long> mx2; // max of (b_l - a_l) + corresponding dp↵
vector<long long> mn1; // min of (b_l + a_l) + corresponding dp↵
vector<long long> mn2; // min of (b_l - a_l) + corresponding dp↵
vector<vector<long long>> dp;↵
mx1.assign(N + 1, -INF); mx2.assign(N + 1, -INF);↵
mn1.assign(N + 1, INF); mn2.assign(N + 1, INF);↵
dp.assign(N + 1, vector<long long>(K + 1, 0));↵
for (int i = 0; i <= N; ++i) {↵
for (int j = 0; j <= min(i, K); ++j) {↵
if (i != 0) dp[i][j] = dp[i - 1][j];↵
int diag_val = i - j;↵
if (i != 0) {↵
dp[i][j] = max(dp[i][j], b[i - 1] + a[i - 1] - mn1[diag_val]);↵
dp[i][j] = max(dp[i][j], -b[i - 1] - a[i - 1] + mx1[diag_val]);↵
dp[i][j] = max(dp[i][j], a[i - 1] - b[i - 1] - mn2[diag_val]);↵
dp[i][j] = max(dp[i][j], b[i - 1] - a[i - 1] + mx2[diag_val]);↵
}↵
if (i != N) {↵
mn1[diag_val] = min(mn1[diag_val], b[i] + a[i] - dp[i][j]);↵
mx1[diag_val] = max(mx1[diag_val], b[i] + a[i] + dp[i][j]);↵
mn2[diag_val] = min(mn2[diag_val], b[i] - a[i] - dp[i][j]);↵
mx2[diag_val] = max(mx2[diag_val], b[i] - a[i] + dp[i][j]);↵
}↵
}↵
}↵
cout << dp[N][K] << "\n";↵
}↵
↵
↵
signed main() {↵
int T = 1;↵
cin >> T;↵
while (T--) {↵
solve();↵
}↵
}↵
↵
↵
```↵
</spoiler>↵
↵
↵
[problem:1859A]↵
↵
<spoiler summary="Hints">↵
↵
<spoiler summary="Hint 1">↵
What does it mean that $A$ divides $B$?↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
First, if all numbers are equal, then there is no answer (since $a$ is divisible by $a$, if both arrays are non-empty, then $c_1$ is a divisor of $b_1$).↵
↵
Second, if $a$ is divisible by $b$ and they are both natural numbers, then the following equality holds: $b \le a$ (by definition, if $a$ is divisible by $b$, then $a$ can be represented as $k \dot b$, where $k$ is a natural number).↵
↵
Now we can place all instances of the smallest number into $b$, and all other numbers into $c$. It can be seen that such a construction always gives a valid answer.↵
</spoiler>↵
↵
↵
<spoiler summary="Author's code">↵
```c++↵
#include <iostream>↵
#include <algorithm>↵
#include <vector>↵
using namespace std;↵
↵
void solve() {↵
int n = 0; cin >> n; ↵
vector<int> inp; inp.assign(n, 0);↵
for (auto& x : inp) cin >> x;↵
sort(inp.begin(), inp.end());↵
if (inp.back() == inp[0]) {↵
cout << "-1\n";↵
return;↵
}↵
else {↵
int it = 0;↵
while (inp[it] == inp[0]) it++;↵
cout << it << " " << n - it << "\n";↵
for (int j = 0; j < it; ++j) cout << inp[j] << " ";↵
for (int j = it; j < n; ++j) cout << inp[j] << " ";↵
}↵
}↵
↵
int main() {↵
int t = 0; cin >> t;↵
while (t--) solve();↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
[problem:1859B]↵
↵
<spoiler summary="Hints">↵
↵
<spoiler summary="Hint 1">↵
Do all numbers in a single array really matter?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If only the first minimum and the second minimum matter, what is the only way to increase a single array's beauty?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
What can we say about the array which will have the smallest number in the end?↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
To increase the answer for each array separately, it is necessary to move the minimum to another array. Then, notice that it is optimal to move all the minimums to one array. Let's figure out which array. After moving the minimum from an array, the second minimum in the original array becomes the new minimum. Then, it is easy to notice that it is optimal to move all the minimums to the array with the smallest second minimum. After all the movements, we will have one array where the minimum element is the smallest number among all the arrays, and $n-1$ arrays where the minimum element is the second minimum in the original array.↵
↵
Therefore, the answer to the problem will be $M + K - S$, where $M$ is the minimum element among all the arrays, $K$ is the sum of all the second minimums, and $S$ is the smallest second minimum.↵
</spoiler>↵
↵
↵
<spoiler summary="Author's code">↵
```c++↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
#include <numeric>↵
↵
using namespace std;↵
↵
#define all(v) v.begin(), v.end()↵
↵
typedef long long ll;↵
↵
const int INF = 1e9 + 7;↵
↵
void solve() {↵
int n;↵
cin >> n;↵
↵
int minn = INF;↵
vector<int> min2;↵
for (int i = 0 ; i < n ; i++) {↵
int m;↵
cin >> m;↵
vector<int> v(m);↵
for (auto &el : v) cin >> el;↵
↵
int minel = *min_element(all(v));↵
minn = min(minn, minel);↵
v.erase(find(all(v), minel));↵
min2.push_back(*min_element(all(v)));↵
}↵
cout << minn + (ll) accumulate(all(min2), 0ll) - *min_element(all(min2)) << "\n";↵
}↵
↵
signed main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
#ifdef LOCAL↵
freopen("a.in", "r", stdin);↵
#endif↵
↵
int t = 1;↵
cin >> t;↵
while (t--)↵
solve();↵
↵
return 0;↵
}↵
↵
```↵
</spoiler>↵
↵
[problem:1859C]↵
↵
<spoiler summary="Hints">↵
↵
<spoiler summary="Hint 1">↵
What if we fix the maximum element in the resulting array?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Try using greedy.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Optimize the log factor away by noticing a certain fact.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
Let's fix the maximum element in an array — let it be $M$. Now, let's iterate from $n$ to $1$. Let the current chosen number be $i$. I claim that if we maintain the remaining available numbers to multiply by, then it is optimal to take the maximum such number $x$ that $x * i \le M$. ↵
↵
Proof: let's say that this is not correct. Then, let's say that we pair $i$ with another number $x1$, and $x$ gets paired with some other number $i1$. Then, $i1 < i$, because it was chosen later, and $x1 < x$ (otherwise $i * x1 > M$). Now let's swap $x$ with $x1$. The sum is increased by $i * x - i * x1 - i1 * x + i1 * x1 = (i - i1)(x - x1) > 0$, and all of the numbers are less or equal to $M$.↵
↵
Now the task can be solved in $O(N^3logN)$ by simply iterating on the maximum from $N^2$ to $1$, while maintaining the remaining numbers with a set. In order to squeeze it in the TL, you can only consider such maximums that they can be represented as $i * j, 1 \le i, j \le n$.↵
↵
In order to optimize it to $O(N^3)$, let's notice that for each number $x$, it can be paired with any number from $1$ to $\frac{M} {x}$. Now just maintain a stack of all available elements at the current moment, add all numbers that possible, and pop the maximum number for all $i$ from $1$ to $N$.↵
</spoiler>↵
↵
↵
<spoiler summary="Author's code">↵
```c++↵
#include <iostream>↵
#include <algorithm>↵
#include <set>↵
#include <stack>↵
#include <vector>↵
using namespace std;↵
void solve() {↵
int N = 0; cin >> N;↵
int ans = 0;↵
vector<int> pr;↵
pr.assign(N * N, -1);↵
for (int i = 1; i <= N; ++i) {↵
for (int j = 1; j <= N; ++j) {↵
pr[i * j - 1] = 1;↵
}↵
}↵
for (int mx = N * N; mx >= 1; --mx) {↵
if (pr[mx - 1] == -1) continue;↵
vector<vector<int>> a;↵
int curans = -mx;↵
bool br = false;↵
a.assign(N, vector<int>());↵
for (int j = N; j >= 1; --j) {↵
int num = min(mx / j, N);↵
if (num < 1) {↵
br = true;↵
break;↵
}↵
a[num - 1].push_back(j);↵
}↵
if (br) break;↵
stack<int> s;↵
for (int i = 0; i < N; ++i) {↵
s.push(i + 1);↵
bool brk = false;↵
for (auto x : a[i]) {↵
if (s.empty()) {↵
brk = true; break;↵
}↵
curans += s.top() * x;↵
s.pop();↵
}↵
if (brk) break;↵
}↵
ans = max(ans, curans);↵
}↵
cout << ans << "\n";↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int t = 0; cin >> t;↵
while (t--) solve();↵
return 0;↵
}↵
↵
```↵
</spoiler>↵
↵
[problem:1859D]↵
↵
<spoiler summary="Hints">↵
↵
<spoiler summary="Hint 1">↵
What if we use greedy a bit?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Where it is always beneficial to teleport?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Use scanline↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Tutorial">↵
Statement: It is always beneficial to teleport to point $b_i$.↵
↵
Proof: Let's assume that we were able to teleport from point $X$ to the right of $b_i$, but not from $b_i$. Then we used some segment $A$ that covers point $X$, but does not cover point $b$, and ends to the right of $b$. This is a contradiction.↵
↵
Let $ans_i$ be the maximum coordinate we can reach while being on segment $i$, and let $p_j$ be the answer to the $j$-th query. Then we notice that the answer to query $p_j = \max(x_j, \max_{i = 1}^n \{ans_i \vert l_i \le x_j \le r_i\})$.↵
↵
We will use the scanline method from the end. Events: $l_i$, $b_i$, $r_i$, $x_j$.↵
↵
We notice that events of type $r_i$ are not important to us when scanning from the end (according to statement number 1). It is important for us that we process events of type $b_i$ first, then events of type $x_j$, and then events of type $l_i$ (closing the segment in the scanline).↵
↵
We will go through the events of the scanline, processing them in the order of $b_i$, then events of type $x_j$, and then events of type $l_i$.↵
↵
We assume that there is a data structure that allows us to add elements, remove elements, and quickly output the maximum.↵
↵
↵
- For each event of type $b_i$, update the value of $ans_i$ — take the maximum value of $ans$ of all open segments from the structure.↵
↵
- For each event of type $x_j$, update the value of $p_j$ — take the maximum value of $ans$ of all open segments from the structure, as well as $x_j$.↵
↵
- For each event of type $l_i$, remove $ans_i$ from the structure.↵
↵
↵
We notice that to solve this problem, we can use the std::multiset} container, which automatically sorts elements in ascending order. We can store in $multiset$ $ans_i$ of all open segments. And then, when processing events, extract the maximum from $multiset$, all operations are performed in $O(\log n)$. This allows us to solve the problem in $O((n + q) \log n)$ time and $O(n)$ memory.↵
</spoiler>↵
↵
↵
<spoiler summary="Author's code">↵
```c++↵
#include <iostream>↵
#include <vector>↵
#include <set>↵
#include <iomanip>↵
#include <cmath>↵
#include <algorithm>↵
#include <map>↵
#include <stack>↵
#include <cassert>↵
#include <unordered_map>↵
#include <bitset>↵
#include <random>↵
#include <unordered_set>↵
#include <chrono>↵
↵
using namespace std;↵
↵
#define all(a) a.begin(), a.end()↵
↵
void solve() {↵
int n;↵
cin >> n;↵
↵
vector<int> ans(n);↵
vector<tuple<int, int, int>> events;↵
for (int i = 0 ; i < n ; i++) {↵
int l, r, a, b;↵
cin >> l >> r >> a >> b;↵
ans[i] = b;↵
events.emplace_back(b, 1, i);↵
events.emplace_back(l, -1, i);↵
}↵
int q;↵
cin >> q;↵
vector<int> queries(q);↵
for (int i = 0 ; i < q ; i++) {↵
int x;↵
cin >> x;↵
queries[i] = x;↵
events.emplace_back(x, 0, i);↵
}↵
↵
sort(all(events));↵
reverse(all(events));↵
multiset<int> s;↵
for (auto [x, type, ind] : events) {↵
if (type == 1) {↵
if (!s.empty()) {↵
ans[ind] = *s.rbegin();↵
}↵
s.insert(ans[ind]);↵
} else if (type == 0) {↵
if (!s.empty()) {↵
queries[ind] = max(queries[ind], *s.rbegin());↵
}↵
} else {↵
s.extract(ans[ind]);↵
}↵
}↵
↵
for (auto el : queries)↵
cout << el << " ";↵
cout << "\n";↵
}↵
↵
signed main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t = 1;↵
cin >> t;↵
while (t--)↵
solve();↵
↵
return 0;↵
}↵
↵
```↵
</spoiler>↵
↵
[problem:1859E]↵
↵
<spoiler summary="Hints">↵
↵
<spoiler summary="Hint 1">↵
Maybe we can relax some conditions?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Do we really need to always correctly calculate all sums?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Optimize the obvious dp.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
↵
Let's call the value of a segment $[l; r]$ $f(l, r) = abs(a_l - b_r) + abs(a_r - b_l)$.↵
↵
Let's write $dp[n1][k1]$ — maximum value of segments of total length $k1$ that end before $n1$.↵
↵
The obvious way to recalc is the following:↵
↵
$dp[n1][k1] = max(dp[n1 - 1][k1], dp[n1 - l][k1 - l] + f(n1 - l + 1, n1), 1 \le l \le k1)$.↵
↵
This works in $O(NK^2)$ and is too slow.↵
↵
Now let's consider the following: instead of getting the absolute value of segment $[l; r]$, we consider the maximum of the following four combinations: $b_l - a_r + b_r - a_l$, $b_l - a_r - b_r + a_l$, $-b_l + a_r + b_r - a_l$, $-b_l + a_r - b_r + a_l$. We can see that this always gives us the correct answer to the absolute value, since we check all of the possibilities.↵
↵
Now we can look at out dp states as a table, and notice that we recalc over the diagonal (we recalc over all states that have the same value of n1 — k1). ↵
↵
Now, for each "diagonal", we maintain four maximum combinations: $dp[n1][k1] + b_{k1} + a_{k1}, dp[n1][k1] - b_{k1} + a_{k1}, dp[n1][k1] + b_{k1} - a_{k1}, dp[n1][k1] - b_{k1} - a_{k1}$, and when we want to recalc state $dp[n2][k2]$, we just consider all of the four possibilities.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Author's code">↵
```c++↵
#include <iostream>↵
#include <vector>↵
using namespace std;↵
const long long INF = 1e18;↵
#define int long long↵
↵
void solve() {↵
int N = 0, K = 0; cin >> N >> K;↵
vector<int> a;↵
vector<int> b;↵
a.assign(N, 0);↵
b.assign(N, 0);↵
for (int i = 0; i < N; ++i) {↵
cin >> a[i];↵
}↵
for (int i = 0; i < N; ++i) {↵
cin >> b[i];↵
}↵
vector<long long> mx1; // max of (b_l + a_l) + corresponding dp↵
vector<long long> mx2; // max of (b_l - a_l) + corresponding dp↵
vector<long long> mn1; // min of (b_l + a_l) + corresponding dp↵
vector<long long> mn2; // min of (b_l - a_l) + corresponding dp↵
vector<vector<long long>> dp;↵
mx1.assign(N + 1, -INF); mx2.assign(N + 1, -INF);↵
mn1.assign(N + 1, INF); mn2.assign(N + 1, INF);↵
dp.assign(N + 1, vector<long long>(K + 1, 0));↵
for (int i = 0; i <= N; ++i) {↵
for (int j = 0; j <= min(i, K); ++j) {↵
if (i != 0) dp[i][j] = dp[i - 1][j];↵
int diag_val = i - j;↵
if (i != 0) {↵
dp[i][j] = max(dp[i][j], b[i - 1] + a[i - 1] - mn1[diag_val]);↵
dp[i][j] = max(dp[i][j], -b[i - 1] - a[i - 1] + mx1[diag_val]);↵
dp[i][j] = max(dp[i][j], a[i - 1] - b[i - 1] - mn2[diag_val]);↵
dp[i][j] = max(dp[i][j], b[i - 1] - a[i - 1] + mx2[diag_val]);↵
}↵
if (i != N) {↵
mn1[diag_val] = min(mn1[diag_val], b[i] + a[i] - dp[i][j]);↵
mx1[diag_val] = max(mx1[diag_val], b[i] + a[i] + dp[i][j]);↵
mn2[diag_val] = min(mn2[diag_val], b[i] - a[i] - dp[i][j]);↵
mx2[diag_val] = max(mx2[diag_val], b[i] - a[i] + dp[i][j]);↵
}↵
}↵
}↵
cout << dp[N][K] << "\n";↵
}↵
↵
↵
signed main() {↵
int T = 1;↵
cin >> T;↵
while (T--) {↵
solve();↵
}↵
}↵
↵
↵
```↵
</spoiler>↵
↵
