### vaaven's blog

By vaaven, 6 weeks ago, translation,

1793A - Yet Another Promotion was authored and prepared by Ormlis

1793B - Fedya and Array was authored and prepared by TheEvilBird

1793C - Dora and Search was authored by fedoseev.timofey and prepared by vaaven

1793D - Moscow Gorillas was authored and prepared by Gornak40

1793E - Velepin and Marketing was authored and prepared by Tikhon228

1793F - Rebrending was authored by Tikhon228 and prepared by vaaven

## 1793A - Yet Another Promotion

Let $n = (m + 1) \cdot q + r$.

Note that you need to use a promotion if $a \cdot m \leq b \cdot (m + 1)$. In this case, we will buy potatoes $q$ times for the promotion. The remaining potatoes (or all if the promotion is unprofitable) can be bought at $\min(a, b)$ per kilogram.

$q \cdot \min(a \cdot m, b \cdot (m + 1)) + r \cdot \min(a, b)$

Thus this solution works in $\mathcal{O}(1)$

Code

## 1793B - Fedya and Array

Note that the local minimums and maximums will alternate, and there will be the same number of them $k$. Let's call the $i$-th local maximum by $a_i$, the $i$-th local minimum by $b_i$. Without loss of generality, consider that $a_i$ goes before $b_i$. To get $b_i$ from $a_i$ we need to write out $a_i - b_i$ numbers, to get $a_{(i + 1) \bmod k}$ from $b_i$ we need to write out $a_{(i + 1) \bmod k} - b_i$ numbers.

Thus, $(a_1 - b_1) + (a_2 - b_1) + (a_2 - b_2) + \ldots + (a_k - b_k) + (a_1 - b_k) =$

$= 2 \cdot (a_1 + a_2 + \ldots + a_k) - 2 \cdot (b_1 + b_2 + \ldots + b_k) = 2 \cdot (A - B) = n$

The array $[y, y + 1, y + 2, \ldots, x - 1, x, x - 1, x - 2, \ldots, y + 1]$ will satisfy the condition.

Code

## 1793C - Dora and Search

Suppose we want to check whether the entire array satisfies the claim. If this is the case, then we can output the entire array as an answer. Otherwise, one of the two extreme elements does not meet our requirements. From this we can conclude that all segments containing an element that does not meet our requirements will also be incorrect, because this extreme element will remain the minimum/maximum.

The algorithm follows from the fact above: let's look at the sub-section $[l; r]$, which is initially equal to $[1; n]$. If $a_l = \min(a_{l}, a_{l+1}, \ldots, a_{r})$ or $a_l = \max(a_l, a_{l +1}, \ldots, a_r)$, then we proceed to the segment $[l+1; r]$. A similar reasoning is also needed for $a_r$. Thus, either after some iterations we will get the required sub-section, or we will get $l == r$ and the answer will be $-1$.

Final asymptotics: $\mathcal{O}(n\log n)$ or $\mathcal{O}(n)$ depending on the implementation.

Code

## 1793D - Moscow Gorillas

Denote by $pos_x$ the index of the number $x$ in the permutation. Subsegments with $\operatorname{MEX}>1$ are as follows $1 \le l \le pos_1 \le r \le n$.

Denote by: $l_x = \min{[pos_1, pos_2, \ldots, pos_x]}$, $r_x=\max{[pos_1, pos_2, \ldots, os_x]}$.

Subsegments with $\operatorname{MEX}>x$ are as follows $1 \le l \le l_x \le r_x \le r \le n$. Let's find all subsegments with $\operatorname{MEX}=x$.

If $pos_{x + 1} < l_x$, then the subsegments with $\operatorname{MEX}=x+1$ are as follows $pos_{x+1} < l \le l_x \le r_x \le r \le n$

If $l_x \le pos_{x + 1} \le r_x$, then there is no subsegment with $\operatorname{MEX}=x+1$

If $r_x <pos_{x+1}$, then the subsegments with $\operatorname{MEX}=x+1$ are as follows $1 \le l \le l_x \le r_x \le r < pos_{x+1}$

It remains only to intersect the sets of such subsegments for $p$ and $q$, which is done trivially.

Code

## 1793E - Velepin and Marketing

Let's sort people by their group size requirement. Suppose we have such a person $i$ that he is not satisfied, and we have a person $j > i$ who is satisfied. Then we can replace person $j$ in his group with $i$ and the answer for us will not be worse. It follows that for a particular $k$ the answer is some prefix of the people we can make satisfied.

Let us also prove that there exists some arrangement of groups that covers the same prefix, and that each group is a continuous segment. Let's take some correct partitioning into groups. Then each group will be a set of unconnected segments. Let's take the leftmost such segment. Note that we can swap it to the nearest segment of the same group to the right without breaking anything.

Thus we obtained that we can look for a solution in the form of partitioning each prefix into valid groups, which are segments. We will solve this problem using dynamic programming.

Let $dp[i]$ -- the maximum number of groups into which $i$th prefix can be partitioned, so that everyone is satisfied (and no elements beyond the prefix can be used). Dynamics base: $dp[0] = 0$ (empty prefix maximum can be divided into 0 groups). Transition: for $i$th person his group must have size at least $a[i]$, so the transition looks like this $dp[i] = \underset{0 \leqslant j \leqslant i - a[i]}{\max} dp[j] + 1$. But what if $a[i] > i$? Then we can't dial the $i$th prefix. Then we put $dp[i] = -\infty$. This dynamics can be calculated using prefix maximums. This part of the solution works for $\mathcal{O}(n)$.

Earlier we said that the answer would be some prefix of people who would be satisfied. If we can partition the prefix into some number of groups, then that answer can be the prefix for all $k \leqslant dp[i] + n - i$. (we partition our prefix into $dp$, and the rest of the people one by one into the group)

If we can't make the whole prefix satisfied ($dp[i] = -\infty$), then we need to add people from outside. Thus, the maximum number of groups we can split into if $i$th prefix is completely satisfied is $n - a[i] + 1$.

Note that if by some prefix we can score $k$, then we can also score $k - 1$ (combining two groups into one). Then we need to find the largest prefix that fits the given $k$ in the query. This can be done by an array of suffix maximums over $\mathcal{O}(q)$ total. The final asymptotic of the solution is $\mathcal{O}(n \log n + q)$.

Code

## 1793F - Rebrending

Let's go through all the elements from left to right. The main task will be to support the current version of $dp[i]$ -- the minimum difference of $a_i$ with the elements to the right of it that we managed to consider. Let us correctly calculate $dp$ for the first $r$ elements. Let's move on to $r + 1$. Let's show how to update the answer for all $j < i$, such that $a[j] > a[i]$. For $j < i$, such that $a[j] <a[i]$ is solved similarly.

Let's take the first element $a[j]$ to the left of $i$, such that $a[j] > a[i]$. Note that if there is $l<j < i$ such that $a[l] > a[j]> a[i]$, then we will not update $dp[l]$ for it, because $|a[l] - a[j]| < |a[l] - a[i]|$. Also, we will not update the answer for $l$ such that $|a[l] - a[j]| < |a[l] - a[i]|$, that is, if $a[l] > a[i] + \frac{a[j] - a[i]}{2}$. Therefore, further we will be interested only in the numbers from the segment $\left[a[i], a[i] + \frac{a[j] - a[i]}{2}\right]$.

Let's note that we have reduced the length of the segment by $2$ times. That is, there will be no more such iterations than $\mathcal{O}(\log n)$. You can find the rightmost number belonging to a segment using the segment tree. The answer for the segment $l_i, r_i$ will be $\underset{l_i\leqslant j<r}{\min} dp[l]$ at the moment $r_i$. This can also be efficiently found using the segment tree. The final asymptotics of the solution is $\mathcal{O}(n\log^2 n + q\log n)$.

There is also a solution for $\mathcal{O}(n\sqrt{n} + q\log q)$ that passes all the tests.

Code

• +130

 » 6 weeks ago, # |   +3 is this contest rated?
 » 6 weeks ago, # | ← Rev. 2 →   0 [deleted]
•  » » 6 weeks ago, # ^ |   0 [deleted]
 » 6 weeks ago, # | ← Rev. 2 →   0 You want:Rated: Unrated:
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   +2 Edit: the ratings have been updated!!
•  » » 6 weeks ago, # ^ |   +72 if copy F: rated else unrated
•  » » 6 weeks ago, # ^ |   0 Though I solved F, I think it shoud be unrated. But now it is rated.
 » 6 weeks ago, # |   +9 Did anyone solved F using Mo's algo (specific sqrt decomposition) ? I made some failed attempts using sets with a TC of $\mathcal{O}(n\sqrt{n}\log{n})$
•  » » 6 weeks ago, # ^ |   +29 Yes, check out my submission. Super fast set for integers and super fast IO were used to pass TL, overall complexity is $O(C\cdot (N+Q)\sqrt{N})$, where $C$ is some small constant of fast set.
•  » » » 6 weeks ago, # ^ |   0 Wow, that's kinda amazing. Do you have a template / resource for this super fast set and super fast IO, that you can share with me ?It's actually hard for me to wrap my head around it...
•  » » » » 6 weeks ago, # ^ |   0 Both templates are in the code or wdym by that. IO was taken from someone's submission here, fast set was written by me based on 64-nary tree.
•  » » » » 6 weeks ago, # ^ |   +27 Practice on infoarena and this won't feel that amazing.
•  » » » » » 6 weeks ago, # ^ |   +8 What is infoarena dude ?
•  » » » 6 weeks ago, # ^ |   +5 Could you describe your solution, please?
•  » » » » 6 weeks ago, # ^ |   +5 It's something like this: link
•  » » » 6 weeks ago, # ^ |   0 in your MO you are not using optimizations,maybe it would have been easier to pass TL if you used tricks that are making NO even faster?
•  » » » » 6 weeks ago, # ^ |   +15 What optimizations you are talking about?
•  » » » » » 5 weeks ago, # ^ |   0 the sorting of the blocks, (you have it commented), also you may have used the best comparator that i really do not remember and will include a link when i find it
•  » » » » » » 5 weeks ago, # ^ |   0 It is not an usual MO where you can move left and right pointers as you want, so the comparator you're talking about won't work here.
 » 6 weeks ago, # |   0 Could someone help identify the mistake in my code for problem D?193336874
 » 6 weeks ago, # |   0 Problem C : Dora and Search Video Editorial Link : https://youtu.be/l5GgWZmsZ98 Happy Coding
 » 6 weeks ago, # |   +8 Problem E is a cleverly-designed dp problem with easy implementation and requirement for thinking ability. However, it's ruined by a duplicate problem F, otherwise more contestants could solve it.
 » 6 weeks ago, # |   0 first time i got to solve D in contest and i was just 10 seconds away from submitting it :(
•  » » 6 weeks ago, # ^ |   +1 same here ;(
•  » » 6 weeks ago, # ^ |   +4 Also was super close to submitting D. Bricked B hard :(
 » 6 weeks ago, # |   +4 Can somebody explain to me this statement from the solution for problem F: That is, there will be no more such iterations than O(logn)? Also, I think it should have been |a[l]-a[j]| instead of |a[l]isa[j]| and [a[i],a[i]+(a[j]−a[i])/2] instead of [a[i],a[i]+(a[j]−a[l])/2].
•  » » 6 weeks ago, # ^ |   +8 Every time comes a new $i$ , we try to update all the $dp_j$ that $ja_i$ ($<$ the same).We first find the nearest such $j$ and update it. As we know, elements greater than $a_j$ are ignored, so the range we consider now is $[a_i,a_j]$ . Also, the elements greater than the center of the range are ignored. So the next $a_j$ we find is in $\left[a_i,a_i+\frac{a_j-a_i}{2}\right]$(the left half of the old range).We find the nearest such $j$ again. This can be done as a maximum query on a weight segment tree. Now we have a new $j$ , and then repeat the process above. Note that each time we find a new $j$, the length of the range is halved. So the whole process will stop in $O(log\ v)$ . Here $v$ is the range of array $a$ , and we know $v=n$ .And your correction is right. vaaven please check that.
 » 6 weeks ago, # |   +1 Only got a micro positive delta but luckily became expert from specialist narrowly :)
•  » » 6 weeks ago, # ^ |   0 congratz)
 » 6 weeks ago, # |   0 Can sqrt-decomposition solve the problem F? I got a TLE and don't know how to optimize
•  » » 6 weeks ago, # ^ |   +3 Yes, and it runs really fast.
 » 6 weeks ago, # |   0 Can't I just put 'n' to place 'q' in problem a tutorial?
 » 6 weeks ago, # |   0 Can anyone Please explain Problem B . It is really Confusing.
•  » » 6 weeks ago, # ^ |   0 Read my code here. U might understand. https://codeforces.com/contest/1793/submission/193333638
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 start answer array from maximum_sum and keep subtracting 1 until you got minimum_sum, as now you have both maximum and minimum sum now keep adding 1 until you get maximum_sum-1 because you have to make it circular so absolute difference between last element and 1st element have to be 1
 » 6 weeks ago, # | ← Rev. 2 →   +7 I'll try to specify the 2nd paragraph of E.From para#1 we know that in the sorted array, it is always possible that all the satisfied people form a prefix of this array. But in this prefix, maybe a group is separated into a set of unconnected segments. Now we'll prove that all these segments from the same group can be connected.Let's pick two segments from one of the groups, calling the left segment $A$ , and the right one $B$ . We now try to keep moving $A$ to the right until $A$ connects with $B$ . While $A$ moving right, it squeezes other elements to the left. From para#1 we know if you throw an element to the left, it won't be worse. So don't worry about these squeezed elements. As for $A$ , it will stop as soon as it meets $B$ . We know people in $B$ are all satisfied, because all the people in the whole prefix are satisfied. We also know the whole array is sorted, so the elements in $A$ will not be greater than $B$ . And, we only move segments and not change the length, so the group size always stays the same. So people in $B$ stay satisfied, people in $A$ with lower requirement (than $B$) also stay satisfied. Nothing is wrong.Now we can connect together any two segments from the same group by moving the left one to the right. The remaining task is only to repeat this operation.Therefore, we have proved that, each group in this prefix can be a continuous segment.
•  » » 6 weeks ago, # ^ |   +4 Thank you very much, I finally understand what editorial is trying to say .....
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 Actually the above explanation is not completely correct and also misleading as we can not always squeeze elements to the left. There is something missing in it due to which it gives false impressions. As it took me quite a lot of time to understand it,i would try my best to explain my argument here : first we sort the requirement vector a : a1,a2,a3,...,an in a non-decreasing order of ai's i.e. now for all 1<=i,j<=n , i=aj>=ai and index j is no longer satisfied as bj=x, and number of x's in b = u=ai , v>=aj , u>=ak . We can write the 1st and 3rd conditions together as u>=ak and ai<=aj<=ak. Hence we have u>=ak , v>=aj , ai<=aj<=ak ----- * Now let's analyse what happens when we swap the values of b for indices i and j(in order to bring the two x's together : we want to bring all the separated segments belonging to a same group together into a continuous segment) : array a : ai , aj , ak array b : y , x , xnow since the index k is unchanged, it is still satisfied. index i is still satisfied by the same argument as in proof 1 : number of y's in b = v>=aj>=ai (from *) and index j(the most confusing one) is also still satisfied(all this was possible because of the presence of the index k=ak>=aj(from *). Hence we can perform the swap without breaking anything. Hence we can always bring together two different indices(that are not initially together) belonging to the same group by making swaps from left to right as shown above and hence we are done!
•  » » » 6 weeks ago, # ^ |   +5 I'm sorry but I have to say your text is hard to read... Anyway, I know what you are talking about. That's exactly the same as what I tried to say. Maybe my words such as "move the segment" and "squeeze" caused some misunderstandings. I'll clarify my idea."Moving a segment" only moves the arrangement of groups, not the elements themselves. For example, $\Big[(1,2),[3,4],(5,6)\Big]\rightarrow\Big[[1],(2,3),[4],(5,6)\Big]$ . In fact, this step swaps the arrangement of groups between the two indexes $1$ and $3$ . That is the same as your proof.Anyway, thanks for your discussion.
 » 6 weeks ago, # |   +52 F can be solved using sqrt decomposition in $O((n+q)\sqrt n)$ with a small constant.Notice that a pair $l,r$ can contribute to the answer only if $r-l\leq \sqrt n$ or $|a_r-a_l|\leq \sqrt n$, and there are only $O(n\sqrt n)$ of them. So we can find the answers offline, sorted by increasing $r$, and each time we add an element to the right, we update the answers in the segtree, but this will be $O((n\sqrt n+q)\log n)$, which is too slow.But we have a trick here, notice that we have $O(n\sqrt n)$ updates and only $O(q)$ queries in the segtree, we can trade query time complexity for update time complexity using sqrt decomposition. Therefore the total time complexity is $O((n+q)\sqrt n)$.Here is the submission 193306318 (it is really short).
•  » » 6 weeks ago, # ^ | ← Rev. 4 →   0 What do you mean by "can contribute to the answer"? What if the statement is false? How is the answer calculated? update: You have already precalculated answers for each block of size sqrt(n).
•  » » 3 weeks ago, # ^ |   0 actually it seems that number of segments that might contribute to the answer are only O(n) instead of O(n * root(n)). I am not able to prove it but it does seems like the case.
 » 6 weeks ago, # |   0 In problem B, there isn't any restriction to the (x — y) difference. But when I try to hack solutions using the case x, y = {1e9, -1e9}, the validator says "Invalid Case". Why?You may say; "It is impossible / incredibly hard to find a solution to that case". That's what I thought when I was trying to solve this problem. Yes, there is a restriction on the sum of 'n', but that doesn't mean (x — y) is also restricted.Looking forward to your opinions about that.
•  » » 6 weeks ago, # ^ |   0 It is a implicit restriction, due to the limit on N this case has no valid solution. I agree that this is misleading... maybe they didn't make it clear to avoid giving a hint
•  » » 6 weeks ago, # ^ |   +3 Well, x — y means one of your n's will be equal to x-y. That means the original restriction on the sum of n's indirectly restricts the value of x and y
•  » » » 6 weeks ago, # ^ |   0 It doesn't. Because there isn't anything like "It is guaranteed that the answer exists" in the statement. Or "It is guaranteed that answer exists with n <= 2e5".
•  » » » » 6 weeks ago, # ^ |   0 I meant it comes from the sketch of the optimal solution, I dont see the problem, is part of being a competitor to check the implicit constraints too and I think it's brilliant how they did it here, it made me doubt a lot
•  » » 6 weeks ago, # ^ |   +8 The problem statement says: It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$It was proven in the editorial that in any valid solution, $n = 2 \cdot (x - y)$.Here, the "gurantee" means that an input is valid only if the sum of $n$ in the answer will not exceed $2 \cdot 10^5$. Any input that doesn't satisfy this will be deemed invalid, even if it satisfies the $-10^9 \le x, y \le 10^9$ requirement.This can be understood incorrectly, because the word "gurantee" is very ambiguous here. You should read more about it here.
•  » » 6 weeks ago, # ^ |   +5 i think its fine the way they did it, and to some extent reduced the guessing on the problem, if they instead say sum of x-y doesnt exceed 1e5, solution would be obvious
 » 6 weeks ago, # |   0 Can anyone tell me why wrong answer is coming for Test 6 in problem D?Link to Submission
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 52 3 1 4 52 3 1 4 5
 » 6 weeks ago, # |   +11 Why can't the explanations be more elaborate? Aren't they supposed to induce more interest? I always feel these tutorials require a lot of cognitive effort, does anybody feel the same?
 » 5 weeks ago, # |   0 I can't find what's wrong with my code for problem F, which uses the same approach as in the editorial. My submission — 194098249. Can anyone please point out the mistake?
 » 5 weeks ago, # | ← Rev. 2 →   0 Different idea for problem F (that is hopefully easier to find).Consider a 1d array $dp$ of size $N$. Through various iterations, our array $dp$ keeps changing.In the first iteration, $dp[i]$ is the minimum absolute difference between $a[i]$ and some other element in indices in the range $N - 1 \dots i$. In the second iteration, $dp[i]$ is the minimum absolute difference between $a[i]$ and some other element in indices in the range $N - 2 \dots i$. More generally, at the $x$th iteration, $dp[i]$ is the minimum absolute difference between $a[i]$ and some other element in indices in the range $N - x \dots i$. It is not hard to see that for a query $(l, r)$, all we need to do is find $\text{min}_{l \le x \le r} dp[x]$ on the $N - l$th iteration of $dp$. Since we can process the queries offline, we can process the queries in decreasing order of $l$--or in increasing order of "iteration."So now the question becomes how to actually construct $dp$. At the beginning, at the $0$th iteration, $dp$ is simply an array where all elements are infinity (or some extremely large number). So we just need to figure out how to update and go from the i — 1th iteration to the ith iteration. What changes? Not much.Lots of stuff that is within $\sqrt{N}$ of index may change. We can apply these changes manually. What about stuff that is farther than $\sqrt{N}$ of index $i$? Only $O(\sqrt{N})$ of them change. The thing is that $dp[x]$ gets really small when $|x - i| > \sqrt{N}$. In fact, when $|x - i| > \sqrt{N}$, $dp[x] < \sqrt{N}$. So basically, most of the dp values are quite small (and probably won't change). The only $dp$ values that may be affected are ones where $a[x]$ is really close to $a[l]$ (in fact, within $\sqrt{N}$ of $a[l]$). So now we know how to update $dp$ $O(\sqrt{N})$ times each iteration.Now, the rest is just answering queries, which we can do once we slap on a segment tree to $dp$.194176722Final Complexity: $O(N \sqrt N \log N + Q \log N)$
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I'm sorry, but you modified $dp$ $O(\sqrt{N})$ times on each iteration, and on each modfication you need to update it in the segment tree. As a result, the complexity should be $O((N\sqrt{N}+Q)\log N$ instead of what you mentioned.
•  » » » 4 weeks ago, # ^ |   0 You are right. I updated the post.
 » 4 weeks ago, # |   0 How to solve task B if x-y=1, for example, x=3 and y=2?If follow the proposed solution, the answer is: n=2*(3-2)=2; numbers: 2 3. But this is incorrect, because the list length must be n>=3. Is there a solution for this case?
•  » » 4 weeks ago, # ^ |   0 I see my assumption n>=3 is not correct in view of a circular list. The list (2, 3) implies that 2 is minimum among its left neighbor 3 and right neighbor also 3. And 3 is maximum among its neighbors 2 and 2.So the answer (2, 3) seems OK for the max=3 and min=2 case.
 » 4 weeks ago, # |   0 vaaven What is the $O(n\sqrt{n}+q\log q)$ solution? Please tell us.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +5 Code#include "bits/stdc++.h" #define rep(i, n) for(int i = 0; i < (n); ++i) #define repr(i, n) for(int i = (n - 1); i >= 0; --i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define ar array using namespace std; typedef long long ll; using vi = vector; using vvi = vector; using vl = vector; using pi = pair; const int INFi = 2e9; const ll INF = 2e18; const int maxN = 6e5; const int K = 350; void solve() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; vi a(n); rep(i, n) cin >> a[i]; vi pos(n); rep(i, n) { a[i]--; pos[a[i]] = i; } vvi qs(n); vi l(q), r(q); vi ans(q, -1); rep(i, q) { cin >> l[i] >> r[i]; l[i]--; r[i]--; qs[r[i]].push_back(i); } vi dp(K, -1); vi dp2(n, INFi); int len = 1; while(len * K - (K - 1) <= n) len++; for(int i = 0; i < n; ++i) { for(int j = max(a[i] - K + 1, 0); j < min(n, a[i] + K); ++j) { if (pos[j] < i) dp[abs(j - a[i])] = max(dp[abs(j - a[i])], pos[j]); } for(int j = i - 1; j >= max(i - len, 0); --j) { dp2[j] = min(dp2[j], min(dp2[j + 1], abs(a[i] - a[j]))); } sort(all(qs[i]), [&] (const int &x, const int &y) { return l[x] < l[y]; }); int j = 0; rep(t, K) { while(j < qs[i].size() && l[qs[i][j]] <= dp[t]) { ans[qs[i][j++]] = t; } } while (j < qs[i].size()) { ans[qs[i][j]] = dp2[l[qs[i][j]]]; j++; } } rep(i, q) { cout << ans[i] << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; // cin >> t; rep(_, t) { solve(); } return 0; } We can split our quieries in two groups. $r - l > \sqrt{n}$ and $r - l \leqslant \sqrt{n}$. Let's solve the task for each queries in order of increasing $r_i$. For second group of queries it's really easy to solve this task, because after moving $r$ to $r + 1$ we need to recalculate nearest element only for $\sqrt{n}$ elements. For first group we can do similar dp but not for elements but for answers. This will work in $\mathcal{O}(n \sqrt n + q\sqrt{n})$. To reach $\mathcal{O}(n \sqrt n + q \log q)$ we need to sort queries for each $r$ in order of decrease $l$ and understand that answer deacrese. That's why we can use smart pointer and our solution will work in $\mathcal{O}(n \sqrt n + q \log q)$.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 This sorting task can be done in linear time. First sort the queries in deceasing $l$. This can be done with counting sort. After this, put each query to its $r_i$ bucket. Because this doesn't change the relative position for queries whose $r_i$ are the same, so we finished the sorting in linear time.Complexity is $O(n\sqrt{n}+q)$ now.ps: Thank you for this solution. I learnt a lot.
•  » » » » 4 weeks ago, # ^ | ← Rev. 4 →   +5 Yeah, we know about $\mathcal{O}(n\sqrt{n} + q)$ solution, but we are too lazy to сode a counting sort ¯ \ _ (ツ) _ / ¯
 » 4 weeks ago, # |   0 Hi, can you please tell me the test I'm missing for problem A: wrong answer 1202nd numbers differ — expected: '666666667', found: '1000000000'
•  » » 4 weeks ago, # ^ |   0 Nvm, I found the issue.
 » 8 days ago, # |   0 It took me a really long time to understand the E editorial. Anyone else on the same boat?