Hello Codeforces! I need help. I can't solve this problem for 24 points (this problem), if anyone has an idea, you can write a comment. Thank you in advance
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Name |
---|
here is the editorial by Benq
thx, but I need 24 point
Solution for 4th subtask:
Let us fix j and now need to find i and k. Now we have to consider 2 cases.
first case: If element at position j is 2 we need to find rightmost index of 1 in range
[1, j]
, and let it be i, then leftmost index of 1 in range[j+1, n]
, let it be k (you can find them with segment tree). We will need to add to answer $$$(k-j-1)*(j-i)$$$. Why do we add it?[i+1, j]
and[j+1, k-1]
are maximum ranges we with the same elements, we do simple combinatorics by multyplying themsecond case: If element at position j is 1 we do the same as in the first case but instead of finding indexes of 1 we look for indexes of 2.
And also, we add to answer $$$i*(n-k+1)$$$, it is a case when we need both 1 and 2 in these ranges.
So, we just iterate over j and find rightmost and leftmost indexes in $$$O(logN)$$$, the overal complexity will be $$$O(NlogN)$$$
PS when you don't find rightmost or leftmost indexes you will assume that indexes are 0 and n+1.
Hope you understand and sorry for my poor English.
Thx
For every position $$$u$$$ we can calculate $$$\mathrm{nxt}[u]$$$ — the next position after $$$u$$$ where the array equals $$$a_u$$$. If it doesn't exist, set $$$\mathrm{nxt}[u] = \infty$$$.
Fix $$$i$$$ and start sliding $$$j$$$. For each $$$j$$$ you can calculate the range of $$$k$$$ such that $$$(i, j, k)$$$ is beautiful. The left endpoint of the range is the maximum of $$$\mathrm{nxt}[u]$$$, where the maximum is taken over the rightmost appearances of every element in the range $$$i \ldots j$$$. And the right endpoint is the leftmost $$$r$$$ such that $$$a_r$$$ doesn't appear among $$$a_i \ldots a_j$$$. If you have this data for $$$i, j$$$ then you can calculate it for $$$i, j + 1$$$ in amortized $$$\mathcal{O}(1)$$$ time. Thus you end up with an $$$\mathcal{O}(n^2)$$$ algorithm.