As per Cristofor's request I am making an editorial on the problems I solved:

**Room Temperature:**

**Hint 1**

Does the exact temperature to each officer matter??

**Hint 2**

What if every officer wore an infinite amount of jackets??

**Hint 3**

In that case only the Mod matters.

**Solution**

We first initialize the answer we are going to print to infinity (1e18), then we make an Array $$$B$$$, containing the set of $$$A_i mod T$$$ and then we itterate over every $$$B_i$$$ and set the answer to $$$min(ans, max(a[i - 1] - a[i] + k, a[n - 1] - a[i]))$$$, we add that $$$T$$$ as if (s)he took a jacket off. Time complexity: $$$O(N).$$$

**Construction Project:**

**Hint 1**

Think of 2 dijkstras.

**Solution**

We first assign two arrays, $$$DistanceFromS$$$ and $$$DistanceFromT$$$, then we do two dijkstras filling the two arrays, then for every element in the $$$DistanceFromS$$$ we do binary search to find the lower bound of $$$K \geq DistanceFromS_i + L$$$ if there exists one, that means we can make a road connecting the two points. Time complexity: $$$O(N*Log(N)).$$$

**Marathon Race:**

**Spoiler**

didn't solve this lol

**wasa855's Solution**

For problem 3, first consider how to answer one question. Balls at the same position can be merged, then consider the entire process in reverse order, The last ball collected must be one of the balls on left or right side of the end point, and the last $$$K$$$ balls collected must form an interval. Enumerate the last ball collected(at most 2 different balls possible), the observation leads a DP that $$$fl,r$$$ indicates if we collect the balls between $$$l-th$$$ to the $$$r-th$$$ position at the end of entire process, what is the minimal time to collect them. It answers a question in $$$O(n^2)$$$time, where n is the different places that have balls. If we calculate all $$$n$$$ beginning position, we can answer a question in $$$O(Log(N))$$$ time.

Another observation is that if we have n different positions that have balls, the minimal time is at least $$$N^2/2$$$, so we only need to solve the task for $$$N \leq 1000$$$, previous $$$O(N)$$$ solution works.

**Proof by Dominater069**

Assume you pick up anything in the middle right now, but you will pass this point atleast once more (when you go from leftmost to rightmost or vice versa), its just optimal to pick it up then.

(DK How to link comments sorry), wasa855 Dominater069

**Gift Exchange:**

**Grade**

This only gets you the first 4 subtasks (50 grades)

**Hint 1**

Brute force approach works.

**Hint 2**

Think of sorting the arrays.

**Solution**

We make another two arrays of pairs, to keep track of the element and it's index, and sort both of them. Now to building the last answer, we itterate through every element in the arrays and check if (after sorted) there exists someone giving a gift to himself, since that's not allowed we check if we can exchange gifts with someone 1 index lower or higher, if we can't then the answer is no, and if we can we swap them. After that we itterate in the final two arrays and check if $$$A_i \geq B_i$$$, if it isn't then answer is No otherwise we print Yes. Time complexity $$$O(N*Log(N)*Q), I think segment can get you a 100 But I haven't learned it.$$$

**Implementation**

```
int n, q, a[500010], b[500010];
void solve() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
cin >> q;
while (q--) {
vector<pair<int, int>> v, v2;
int l, r;
cin >> l >> r;
--l;
for (int i = l; i < r; ++i) v.pb({ b[i],i }), v2.pb({ a[i],i });
sort(all(v)); sort(all(v2));
bool flag = true;
for (int i = 0; i < v.size(); ++i) {
if (v[i].ss == v2[i].ss) {
if (i && v2[i - 1].ff >= v[i].ff) swap(v[i - 1], v[i]);
else if (i < v.size() - 1 && v2[i].ff >= v[i + 1].ff) swap(v[i], v[i + 1]);
else { flag = false; break; }
}
}
for (int i = 0;i < v.size();i++) {
if (v2[i].ff < v[i].ff) { flag = false; break; }
}
if (flag) cout << "Yes\n";
else cout << "No\n";
}
}
```

**Hint for Subtask 5**

I think greedy approach works

**For the last problem "Road Service" I didn't understand what was written so I couldn't solve it lol**

Auto comment: topic has been updated by _Spongey (previous revision, new revision, compare).Hello!

I am sorry for only noticing this now. Nice blog! I am currently collecting all of the solutions I can find on past JOI blogs where people only give vague ideas that don’t always help that much, so these are actually helpful!

Thank you for making this blog, I appreciate it! Upvoted!

Cirstofor