#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>
typedef long long llong;
const int NEEDED_ELEMENTS = 30;
const int MAXN = 500000 + 10;
const int INF = 2e9;
int n, q;
int a[MAXN];
struct SegmentTree
{
struct Node
{
int vals[NEEDED_ELEMENTS];
Node()
{
std::fill(vals, vals + NEEDED_ELEMENTS, 0);
}
friend Node operator + (const Node &left, const Node &right)
{
Node res;
int lPtr = 0;
int rPtr = 0;
int ptr = 0;
while (ptr < NEEDED_ELEMENTS)
{
if (a[left.vals[lPtr]] > a[right.vals[rPtr]])
{
res.vals[ptr++] = left.vals[lPtr++];
} else
{
res.vals[ptr++] = right.vals[rPtr++];
}
}
return res;
}
};
Node tree[4*MAXN];
void build(int l, int r, int node)
{
if (l == r)
{
tree[node].vals[0] = l;
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node);
build(mid + 1, r, 2*node + 1);
tree[node] = tree[2*node] + tree[2*node + 1];
}
Node res;
void query(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
res = res + tree[node];
return;
}
int mid = (l + r) / 2;
if (queryL <= mid) query(l, mid, 2*node, queryL, queryR);
if (mid + 1 <= queryR) query(mid + 1, r, 2*node + 1, queryL, queryR);
}
void build()
{
build(1, n, 1);
}
void query(int l, int r)
{
res = Node();
query(1, n, 1, l, r);
}
};
int suffMAX[NEEDED_ELEMENTS];
SegmentTree tree;
void solve()
{
tree.build();
for (int i = 1 ; i <= q ; ++i)
{
int l, r;
int answer = 0;
std::cin >> l >> r;
tree.query(l, r);
SegmentTree::Node res = tree.res;
std::sort(res.vals, res.vals + NEEDED_ELEMENTS);
suffMAX[NEEDED_ELEMENTS - 1] = a[res.vals[NEEDED_ELEMENTS - 1]];
for (int i = NEEDED_ELEMENTS - 2 ; i >= 0 ; --i)
{
suffMAX[i] = std::max(suffMAX[i + 1], a[res.vals[i]]);
}
for (int aPos = 0 ; aPos < NEEDED_ELEMENTS ; aPos++)
{
if (res.vals[aPos] == 0)
{
continue;
}
int cPos = aPos + 2;
for (int bPos = aPos + 1 ; bPos < NEEDED_ELEMENTS ; bPos++)
{
while (cPos < NEEDED_ELEMENTS && res.vals[cPos] < 2 * res.vals[bPos] - res.vals[aPos])
{
cPos++;
}
if (cPos == NEEDED_ELEMENTS)
{
break;
}
answer = std::max(answer, a[res.vals[aPos]] + a[res.vals[bPos]] + suffMAX[cPos]);
}
}
std::cout << answer << '\n';
}
}
void input()
{
std::cin >> n;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> a[i];
}
std::cin >> q;
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
235044 KB |
Output is correct |
2 |
Correct |
65 ms |
235092 KB |
Output is correct |
3 |
Correct |
63 ms |
235108 KB |
Output is correct |
4 |
Correct |
64 ms |
235164 KB |
Output is correct |
5 |
Correct |
63 ms |
235140 KB |
Output is correct |
6 |
Correct |
63 ms |
235200 KB |
Output is correct |
7 |
Correct |
63 ms |
235152 KB |
Output is correct |
8 |
Correct |
66 ms |
235044 KB |
Output is correct |
9 |
Correct |
66 ms |
235152 KB |
Output is correct |
10 |
Correct |
66 ms |
235372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
235044 KB |
Output is correct |
2 |
Correct |
65 ms |
235092 KB |
Output is correct |
3 |
Correct |
63 ms |
235108 KB |
Output is correct |
4 |
Correct |
64 ms |
235164 KB |
Output is correct |
5 |
Correct |
63 ms |
235140 KB |
Output is correct |
6 |
Correct |
63 ms |
235200 KB |
Output is correct |
7 |
Correct |
63 ms |
235152 KB |
Output is correct |
8 |
Correct |
66 ms |
235044 KB |
Output is correct |
9 |
Correct |
66 ms |
235152 KB |
Output is correct |
10 |
Correct |
66 ms |
235372 KB |
Output is correct |
11 |
Correct |
2179 ms |
242860 KB |
Output is correct |
12 |
Correct |
867 ms |
242792 KB |
Output is correct |
13 |
Correct |
865 ms |
242812 KB |
Output is correct |
14 |
Correct |
2165 ms |
243316 KB |
Output is correct |
15 |
Correct |
2127 ms |
242856 KB |
Output is correct |
16 |
Incorrect |
2090 ms |
242132 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
98 ms |
237180 KB |
Output is correct |
2 |
Correct |
86 ms |
235824 KB |
Output is correct |
3 |
Correct |
95 ms |
235856 KB |
Output is correct |
4 |
Correct |
106 ms |
235924 KB |
Output is correct |
5 |
Correct |
95 ms |
235860 KB |
Output is correct |
6 |
Incorrect |
88 ms |
235896 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
235044 KB |
Output is correct |
2 |
Correct |
65 ms |
235092 KB |
Output is correct |
3 |
Correct |
63 ms |
235108 KB |
Output is correct |
4 |
Correct |
64 ms |
235164 KB |
Output is correct |
5 |
Correct |
63 ms |
235140 KB |
Output is correct |
6 |
Correct |
63 ms |
235200 KB |
Output is correct |
7 |
Correct |
63 ms |
235152 KB |
Output is correct |
8 |
Correct |
66 ms |
235044 KB |
Output is correct |
9 |
Correct |
66 ms |
235152 KB |
Output is correct |
10 |
Correct |
66 ms |
235372 KB |
Output is correct |
11 |
Correct |
2179 ms |
242860 KB |
Output is correct |
12 |
Correct |
867 ms |
242792 KB |
Output is correct |
13 |
Correct |
865 ms |
242812 KB |
Output is correct |
14 |
Correct |
2165 ms |
243316 KB |
Output is correct |
15 |
Correct |
2127 ms |
242856 KB |
Output is correct |
16 |
Incorrect |
2090 ms |
242132 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |