#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int mxN = 5e5 + 5;
int n, a[mxN];
vector <int> pos[mxN];
pair <int, int> t[mxN * 4];
void Build(int v = 1, int L = 1, int R = n) {
if (L == R) {
t[v] = {a[L], -1};
return;
}
int M = (L + R) / 2;
Build(v * 2, L, M);
Build(v * 2 + 1, M + 1, R);
if (t[v * 2].f >= t[v * 2 + 1].f)
t[v] = {t[v * 2].f, max(t[v * 2].s, t[v * 2 + 1].f)};
else
t[v] = {t[v * 2 + 1].f, max(t[v * 2 + 1].s, t[v * 2].f)};
}
pair <int, int> Get(int l, int r, int v = 1, int L = 1, int R = n) {
if (l <= L && R <= r)
return t[v];
if (l > R || r < L)
return {-1, -1};
int M = (L + R) / 2;
auto left = Get(l, r, v * 2, L, M);
auto right = Get(l, r, v * 2 + 1, M + 1, R);
if (left.f >= right.f)
return {left.f, max(left.s, right.f)};
return {right.f, max(right.s, left.f)};
}
int main() {
ios :: sync_with_stdio(false), cin.tie(nullptr);
cin >> n;
vector <int> vec;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
vec.push_back(a[i]);
}
sort(vec.begin(), vec.end());
for (int i = 1; i <= n; ++i) {
int x = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
pos[x].push_back(i);
}
Build();
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
auto opt = Get(l, r);
ll ans = 0;
int x = lower_bound(vec.begin(), vec.end(), opt.f) - vec.begin();
int y = lower_bound(vec.begin(), vec.end(), opt.s) - vec.begin();
{ // max R <= r
int R = pos[x][upper_bound(pos[x].begin(), pos[x].end(), r) - pos[x].begin() - 1];
R = max(R, pos[y][upper_bound(pos[y].begin(), pos[y].end(), r) - pos[y].begin() - 1]);
{ // middle, mid < R
int mid;
if (a[R] == opt.f)
mid = pos[y][lower_bound(pos[y].begin(), pos[y].end(), R) - pos[y].begin() - 1];
else
mid = pos[x][lower_bound(pos[x].begin(), pos[x].end(), R) - pos[x].begin() - 1];
// now I should find optimal L
int lb = max(l, mid - (R - mid)), rb = mid - 1;
if (rb >= lb)
ans = 1ll * Get(lb, rb).f + opt.f + opt.s;
}
{ // min L >= l
int L;
if (a[R] == opt.f)
L = pos[y][lower_bound(pos[y].begin(), pos[y].end(), l) - pos[y].begin()];
else
L = pos[x][lower_bound(pos[x].begin(), pos[x].end(), l) - pos[x].begin()];
// now I should find optimal mid
// R - mid >= mid - L
// R + L >= 2 * mid
int lb = L + 1, rb = (L + R) / 2;
if (rb >= lb)
ans = max(ans, 1ll * Get(lb, rb).f + opt.f + opt.s);
}
}
{ // min L >= l
int L = pos[y][lower_bound(pos[y].begin(), pos[y].end(), l) - pos[y].begin()];
L = min(L, pos[x][lower_bound(pos[x].begin(), pos[x].end(), l) - pos[x].begin()]);
{ // middle, mid >= L
int mid;
if (a[L] == opt.f)
mid = pos[y][upper_bound(pos[y].begin(), pos[y].end(), L) - pos[y].begin()];
else
mid = pos[x][upper_bound(pos[x].begin(), pos[x].end(), L) - pos[x].begin()];
// now I should find optimal
// R - mid >= L - mid
int lb = mid + (mid - L), rb = r;
if (rb >= lb)
ans = max(ans, 1ll * Get(lb, rb).f + opt.f + opt.s);
}
{ // max R <= r
int R;
if (a[R] == opt.f)
R = pos[y][upper_bound(pos[y].begin(), pos[y].end(), r) - pos[y].begin() - 1];
else
R = pos[x][upper_bound(pos[x].begin(), pos[x].end(), r) - pos[x].begin() - 1];
// now I should find optimal mid
// R - mid >= mid - L
// R + L >= 2 * mid
int lb = L + 1, rb = (L + R) / 2;
if (rb >= lb)
ans = max(ans, 1ll * Get(lb, rb).f + opt.f + opt.s);
}
}
cout << ans << '\n';
}
return 0;
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:113:12: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
113 | if (a[R] == opt.f)
| ~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
12140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
12140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
24168 KB |
Output is correct |
| 2 |
Correct |
62 ms |
25832 KB |
Output is correct |
| 3 |
Correct |
61 ms |
25832 KB |
Output is correct |
| 4 |
Incorrect |
126 ms |
25964 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
12140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
