#include<bits/stdc++.h>
using namespace std;
#define pb emplace_back
const int maxn = 5e5 + 3;
const int INF = 1e9;
void MAX(int &a, int b) {
if (a < b) a = b;
}
int a[maxn];
struct seg_tree {
vector<int> t, t2, lazy;
seg_tree() {
t.resize(4 * maxn);
t2.resize(4 * maxn);
lazy.resize(4 * maxn);
}
void pushdown(int v) {
int val = lazy[v];
MAX(t[2 * v], val);
MAX(t[2 * v + 1], val);
MAX(lazy[2 * v], val);
MAX(lazy[2 * v + 1], val);
}
void build(int v = 1, int l = 1, int r = maxn - 1) {
if (l == r) {
t2[v] = a[l];
return;
}
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
t2[v] = max(t2[2 * v], t2[2 * v + 1]);
}
void update(int l, int r, int val, int v = 1, int tl = 1, int tr = maxn - 1) {
if (tl > r || tr < l) return;
if (tl >= l && tr <= r) {
MAX(t[v], val);
MAX(lazy[v], val);
return;
}
pushdown(v);
int m = (tl + tr) / 2;
update(l, r, val, 2 * v, tl, m);
update(l, r, val, 2 * v + 1, m + 1, tr);
t[v] = max(t[2 * v], t[2 * v + 1]);
}
int get(int l, int r, int v = 1, int tl = 1, int tr = maxn - 1) {
if (tl > r || tr < l) return 0;
if (tl >= l && tr <= r) return t[v] + t2[v];
pushdown(v);
int m = (tl + tr) / 2;
return max(get(l, r, 2 * v, tl, m), get(l, r, 2 * v + 1, m + 1, tr));
}
} IT;
int n, q, R[maxn], res[maxn];
vector<pair<int,int>> que[maxn];
stack<int> st;
vector<int> L[maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen("TRIPLE.INP", "r")) {
freopen("TRIPLE.INP", "r", stdin);
freopen("TRIPLE.OUT", "w", stdout);
}
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
IT.build();
st.push(0); a[0] = INF;
for (int i = 1; i <= n; i++) {
while (a[i] > a[st.top()])
st.pop();
L[st.top()].pb(i);
st.push(i);
}
cin >> q;
for (int i = 1, l, r; i <= q; i++) {
cin >> l >> r;
que[l].pb(r, i);
}
stack<int>().swap(st);
st.push(n + 1); a[n + 1] = INF;
for (int i = n; i >= 1; i--) {
while (a[i] > a[st.top()])
st.pop();
R[i] = st.top();
IT.update(2 * R[i] - i, n, a[i] + a[R[i]]);
for (int j : L[i])
IT.update(2 * j - i, n, a[i] + a[j]);
st.push(i);
for (auto it : que[i])
res[it.second] = IT.get(i, it.first);
}
for (int i = 1; i <= q; i++)
cout << res[i] << '\n';
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:71:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | freopen("TRIPLE.INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:72:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | freopen("TRIPLE.OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
52824 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
52724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
52824 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
52724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
178 ms |
57112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
52824 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
52724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
