| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3856 |
| 2 | jiangly | 3747 |
| 3 | orzdevinwang | 3706 |
| 4 | jqdai0815 | 3682 |
| 5 | ksun48 | 3591 |
| 6 | gamegame | 3477 |
| 7 | Benq | 3468 |
| 8 | Radewoosh | 3462 |
| 9 | ecnerwala | 3451 |
| 10 | heuristica | 3431 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | -is-this-fft- | 162 |
| 3 | Dominater069 | 160 |
| 4 | Um_nik | 158 |
| 5 | atcoder_official | 156 |
| 6 | Qingyu | 152 |
| 6 | djm03178 | 152 |
| 6 | adamant | 152 |
| 9 | luogu_official | 149 |
| 10 | awoo | 147 |
Hello Codeforces — ers,
I have this problem need to solve
Given an array a with N integers (1 <= N <= 500000)
Given Q queries (1 <= Q <= 100000), for each query, we have 2 integers L and R, we have to find the maximum value of a[x] + a[y] + a[z] with sastifies:
. L <= x < y < z <= R . y — x < z — y
Thanks a lot :D
Persistent segment tree probably. You can find the idea at cp-algo advanced segment tree section.
of course I know Persistent Segment tree, but how to solve it :D :D :D. The main idea ?
Iwo items have to be in the lower half and one in the upper. I guess this would be the idea if its not Im sorry i wasnt able to help
Two queries for the halves amd when the range length is odd you would take the lover half to be even
It's obvious that if there exists $$$x < i < y$$$ such that $$$a_i \ge \min(a_x,a_y)$$$, we can replace $$$x$$$ with $$$i$$$(or replace $$$y$$$ with $$$i$$$).
So all the possible $$$(x,y)$$$ satisfies the condition that $$$\min(a_x,a_y) > \max_{x<i<y} a_i$$$.
It can be proved that there exists only $$$O(n)$$$ pairs of legal $$$(x,y)$$$.
And the rest of the problem can be solved with segment tree offline(persistent segment tree is not needed).
You can refer to https://www.luogu.com.cn/problem/P11392.
Oh thank you a lot :D :D :D
I did not think about posible (x, y) just satisfies min(ax, ay) > max(ai)
https://oj.uz/problem/view/JOI19_jumps