### three_nil's blog

By three_nil, history, 2 months ago,

Given an array A of length N and a number B find the number of subarrays A[l....r] such that A[l]+A[r] and max(A[l...r]) are congruent modulo B
1<=N,B<=500000
1<=A[i]<=1e9
The contest of which this question is has ended.

• +7

 » 2 months ago, # |   0 Your pretty funny. Problem link?
•  » » 2 months ago, # ^ |   +3 https://www.interviewbit.com/contest/code-drift-2-pointers/ 4th question of this contest.
•  » » » 2 months ago, # ^ |   0 I can't access the original statement, but that doesn't sound like a 2 pointers problem.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +3 Here are the link to the question's image. Problem Statement Sample test Yeah it didn't seemed two pointers to me also . I thought of segment tree with lazy propagation but wasn't able to come up with the solution.
 » 2 months ago, # |   0 I don't know any solution which uses two pointer technique. I would solve this problem by iterating over maximums, that is for every element $A[i]$ find range $[L,R]$ in which $A[i]$ is maximum. Now for every element this range can be split into parts $[L,i]$ and $[i+1,R]$, just iterate on the smaller range, that is if we have fixed $A[l]$ we just need to find the count of $(A[i]-A[l])$ under modulo $B$ in the range $[i,R]$. This solution has time complexity of $O(Nlog^2(N))$
•  » » 2 months ago, # ^ |   0 How is this solution $O(Nlog^2(N))$. If we are iterating on $l$ for a given elements on worst it can be $O(n^2)$. Consider a increasing sequence. The $l$ for every element will from $1$ to $i$ , thus leading to $O(n^2)$. Correct me if I misunderstood something.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 No, we are not always iterating on $l$. If i-L>R-i we will then iterate $j$ in $[L, i]$ as my left border. Otherwise, iterate $j$ in $[i, R]$ as the right border. Iterating on smaller part guarantees $O(Nlog(N))$ iterations.
•  » » » » 2 months ago, # ^ |   0 We can get rid of extra $log$, by doing MO on big ranges. But still, for $n \le 5*10^5$ it would be TL.
•  » » » » » 2 months ago, # ^ |   0 Actually $O(Nlog^2(N))$ is fine, for $N=5*10^5$ there are $2*10^8$ operations in the worst case. I had submitted the same solution and it works fine.
•  » » » » » » 2 months ago, # ^ |   0 Damn man, I had the same thought but didn't implement it. I thought it would be N**2 in worst case. By the way what rank did u get in that contest
•  » » » » 6 weeks ago, # ^ |   +21 Can you please explain or give some intuition why it is O(NlogN)?
•  » » » » » 6 weeks ago, # ^ |   +4 Take a look at the editorial of 1156E - Special Segments of Permutation, it is the very same idea. Tutorial is loading...
•  » » » » » » 6 weeks ago, # ^ |   +3 Thank you!There is an another solution — https://codeforces.com/blog/entry/66827?#comment-509216
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 for every element A[i] find range [L,R] in which A[i] is maximumIs there any standard algorithm to do this? Also can you please share a pastebin link of your AC submission.
•  » » » 2 months ago, # ^ |   0 use monotonic queue from left and right each time
•  » » » 6 weeks ago, # ^ |   0 you can use stack to maintain the next greater and smaller element to find the range in which it is maximum..
 » 2 months ago, # |   0 Sorry bro. If I knew, I would have helped you.