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.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.04.2026 14:03:41 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
Your pretty funny. Problem link?
https://www.interviewbit.com/contest/code-drift-2-pointers/
4th question of this contest.
I can't access the original statement, but that doesn't sound like a 2 pointers problem.
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.
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))$$$
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.
No, we are not always iterating on $$$l$$$.
If
i-L>R-iwe 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.
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.
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.
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
Can you please explain or give some intuition why it is
O(NlogN)?Take a look at the editorial of 1156E - Special Segments of Permutation, it is the very same idea.
Thank you!
There is an another solution — https://mirror.codeforces.com/blog/entry/66827?#comment-509216
for every element A[i] find range [L,R] in which A[i] is maximum
Is there any standard algorithm to do this? Also can you please share a pastebin link of your AC submission.