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.

# | User | Rating |
---|---|---|

1 | tourist | 3565 |

2 | Benq | 3540 |

3 | Petr | 3519 |

4 | maroonrk | 3503 |

5 | jiangly | 3391 |

6 | ecnerwala | 3363 |

7 | Radewoosh | 3349 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 198 |

2 | Errichto | 195 |

3 | rng_58 | 190 |

4 | awoo | 186 |

5 | SecondThread | 185 |

6 | Um_nik | 182 |

7 | vovuh | 177 |

8 | Ashishgup | 176 |

9 | antontrygubO_o | 174 |

10 | -is-this-fft- | 173 |

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**

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/07/2021 05:25:39 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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-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.

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://codeforces.com/blog/entry/66827?#comment-509216

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.

use monotonic queue from left and right each time

you can use stack to maintain the next greater and smaller element to find the range in which it is maximum..

Sorry bro. If I knew, I would have helped you.