#include <bits/stdc++.h>
using namespace std;
const int N = 500001;
int a[N];
pair<pair<int, int>, int> que[N];
int resenje[N];
int b[N];
pair<int, int> c[N];
int seg[2 * N - 1][2];
int lazy[2 * N - 1];
int n;
int index = 0;
void build(int u, int l, int r) {
if (l == r) {
seg[u][1] = a[l];
return;
}
int mid = l + r >> 1;
build(u * 2 + 1, l, mid);
build(u * 2 + 2, mid + 1, r);
seg[u][1] = max(seg[u * 2 + 1][1], seg[u * 2 + 2][1]);
}
void upd(int u, int x) {
seg[u][0] = max(seg[u][0], x + seg[u][1]);
lazy[u] = max(lazy[u], x);
}
void shift(int u) {
lazy[u * 2 + 1] = lazy[u];
lazy[u * 2 + 2] = lazy[u];
seg[u * 2 + 1][0] = max(seg[u * 2 + 1][0], seg[u * 2 + 1][1] + lazy[u]);
seg[u * 2 + 2][0] = max(seg[u * 2 + 2][0], seg[u * 2 + 2][1] + lazy[u]);
lazy[u] = 0;
}
void update(int u, int l, int r, int L, int R, int x) {
if (r < L || l > R)
return;
if (l >= L && r <= R) {
upd(u, x);
return;
}
if (lazy[u])
shift(u);
int mid = l + r >> 1;
update(u * 2 + 1, l, mid, L, R, x);
update(u * 2 + 2, mid + 1, r, L, R, x);
seg[u][0] = max(seg[u * 2 + 1][0], seg[u * 2 + 2][0]);
}
void Update(int x, int y) {
for (int i = y - 1; i >= x; i--) {
if (b[i] != -1) {
int l = 2 * b[i] - i;
if (l < n) {
update(0, 0, n - 1, l, n - 1, a[i] + a[b[i]]);
}
}
while (c[index].first == i) {
int l = 2 * c[index].second - c[index].first;
if (l < n) {
update(0, 0, n - 1, l, n - 1, a[c[index].first] + a[c[index].second]);
}
index++;
}
}
}
int out(int u, int l, int r, int L, int R) {
if (r < L || l > R)
return 0;
if (l >= L && r <= R) {
return seg[u][0];
}
if (lazy[u])
shift(u);
int mid = l + r >> 1;
return max(out(u * 2 + 1, l, mid, L, R), out(u * 2 + 2, mid + 1, r, L, R));
}
void veca(int n) {
stack<pair<int, int>> s;
s.push(make_pair(a[0], 0));
for (int i = 1; i < n; i++) {
pair<int, int> top = s.top();
while (!s.empty() && top.first <= a[i]) {
b[top.second] = i;
s.pop();
if (!s.empty())
top = s.top();
}
s.push(make_pair(a[i], i));
}
while (!s.empty()) {
pair<int, int> top = s.top();
b[top.second] = -1;
s.pop();
}
}
bool cmp1(pair<int, int> x, pair<int, int> y) {
if (x.first > y.first)
return true;
if (x.second < y.second)
return true;
return false;
}
void veca1(int n) {
stack<pair<int, int>> s;
s.push(make_pair(a[n - 1], n - 1));
for (int i = n - 2; i >= 0; i--) {
pair<int, int> top = s.top();
while (!s.empty() && top.first <= a[i]) {
c[top.second].first = i;
c[top.second].second = top.second;
s.pop();
if (!s.empty())
top = s.top();
}
s.push(make_pair(a[i], i));
}
while (!s.empty()) {
pair<int, int> top = s.top();
c[top.second].first = -1;
s.pop();
}
sort(c, c + n, cmp1);
}
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
return a.first.first >= b.first.first;
}
void solve() {
int q;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
cin >> q;
for (int i = 0; i < q; i++) {
cin >> que[i].first.first >> que[i].first.second;
que[i].second = i;
}
veca(n);
veca1(n);
sort(que, que + q, cmp);
build(0, 0, n - 1);
for (int i = 0; i < q; i++) {
if (i == 0)
Update(que[i].first.first - 1, n);
else
Update(que[i].first.first - 1, que[i - 1].first.first - 1);
resenje[que[i].second] = out(0, 0, n - 1, que[i].first.first - 1, que[i].first.second - 1);
}
for (int i = 0; i < q; i++)
cout << resenje[i] << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
Compilation message
jumps.cpp:13:5: error: 'int index' redeclared as different kind of entity
13 | int index = 0;
| ^~~~~
In file included from /usr/include/string.h:431,
from /usr/include/c++/9/cstring:42,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:48,
from jumps.cpp:1:
/usr/include/strings.h:61:1: note: previous declaration 'const char* index(const char*, int)'
61 | index (const char *__s, int __c) __THROW
| ^~~~~
jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:20:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
20 | int mid = l + r >> 1;
| ~~^~~
jumps.cpp: In function 'void update(int, int, int, int, int, int)':
jumps.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | int mid = l + r >> 1;
| ~~^~~
jumps.cpp: In function 'void Update(int, int)':
jumps.cpp:62:23: error: invalid types 'std::pair<int, int> [500001][<unresolved overloaded function type>]' for array subscript
62 | while (c[index].first == i) {
| ^
jumps.cpp:63:32: error: invalid types 'std::pair<int, int> [500001][<unresolved overloaded function type>]' for array subscript
63 | int l = 2 * c[index].second - c[index].first;
| ^
jumps.cpp:63:50: error: invalid types 'std::pair<int, int> [500001][<unresolved overloaded function type>]' for array subscript
63 | int l = 2 * c[index].second - c[index].first;
| ^
jumps.cpp:65:56: error: invalid types 'std::pair<int, int> [500001][<unresolved overloaded function type>]' for array subscript
65 | update(0, 0, n - 1, l, n - 1, a[c[index].first] + a[c[index].second]);
| ^
jumps.cpp:65:76: error: invalid types 'std::pair<int, int> [500001][<unresolved overloaded function type>]' for array subscript
65 | update(0, 0, n - 1, l, n - 1, a[c[index].first] + a[c[index].second]);
| ^
jumps.cpp:67:18: error: no post-increment operator for type
67 | index++;
| ^~
jumps.cpp: In function 'int out(int, int, int, int, int)':
jumps.cpp:80:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
80 | int mid = l + r >> 1;
| ~~^~~
