#include "bits/stdc++.h"
#define ll long long
using namespace std;
template <typename T, typename Lambda>
struct segment_tree {
vector<T> tree;
T neutral;
Lambda join;
int size, real_size;
segment_tree() {}
template <typename L>
segment_tree(int _size, const T &_neutral, const L& f)
: join (f) {
real_size = _size;
size = nxt(_size);
tree = vector<T>(2*size+1);
neutral = _neutral;
}
int nxt(int x) {
int i = 1;
while(i < x) {
i <<= 1;
}
return i;
}
void init(const vector<T> &v) {
for(int i = 0; i < real_size; ++i) {
tree[i + size] = v[i];
}
for(int i = size - 1; i >= 0; --i) {
tree[i] = join(tree[i << 1], tree[i << 1 | 1]);
}
}
void point_update(int id, const T &val) {
// point_update(1, size, id, val, 1);
point_update_iterative(id, val);
}
void point_update_iterative(int id, const T &val) {
id += size - 1;
tree[id] = val;
id >>= 1;
while(id > 0) {
tree[id] = join(tree[id << 1], tree[id << 1 | 1]);
id >>= 1;
}
}
void point_update(int l, int r, int x, const T &val, int p) {
if(l > x || r < x) {
return;
}
if(l == r) {
tree[p] = val;
return;
}
int middle = l + r >> 1;
point_update(l, middle, x, val, p << 1);
point_update(middle+1, r, x, val, p << 1 | 1);
tree[p] = join(tree[p << 1], tree[p << 1 | 1]);
}
T get(int id) {
return query(id, id);
}
T query(int L, int R) {
return query(1, size, L, R, 1);
}
T query_iterative(int L, int R) {
L += size - 1;
R += size - 1;
T ans = neutral;
while(L <= R) {
if(L & 1) {
ans = join(ans, tree[L++]);
}
if(!(R & 1)) {
ans = join(ans, tree[R--]);
}
L >>= 1;
R >>= 1;
}
return ans;
}
T query(int l, int r, int L, int R, int p) {
if(L > r || l > R) return neutral;
if(L <= l && R >= r) return tree[p];
int middle = l + r >> 1;
T lft = query(l, middle, L, R, p << 1);
T rgh = query(middle+1, r, L, R, p << 1 | 1);
return join(lft, rgh);
}
};
const int N = 2e5+10;
ll n, q, a[N], ans[N];
vector<int> candidates[N];
vector<pair<int, int>> queries[N];
struct node {
ll a, b, c;
node() {
a = b = c = 0;
}
node(ll _a, ll _b, ll _c) : a(_a), b(_b), c(_c) {}
};
int main() {
auto join = [](const node &x, const node &y) {
node ans;
ans.a = max(x.a, y.a);
ans.b = max(x.b, y.b);
ans.c = max({x.c, y.c, x.a + y.b});
return ans;
};
cin >> n;
segment_tree<node, decltype(join)> t(n, node(), join);
for(int i = 1; i <= n; ++i) {
cin >> a[i];
node x(0, a[i], a[i]);
t.point_update(i, x);
}
stack<int> st;
for(int i = 1; i <= n; ++i) {
while(!st.empty() && a[st.top()] <= a[i]) {
candidates[st.top()].push_back(i);
st.pop();
}
if(!st.empty()) {
candidates[st.top()].push_back(i);
}
st.push(i);
}
cin >> q;
for(int i = 1; i <= q; ++i) {
int l, r; cin >> l >> r;
queries[l].push_back({r, i});
}
for(int l = n; l >= 1; --l) {
for(int i : candidates[l]) {
int id = 2*i - l;
if(id <= n) {
node x = t.get(id);
x.a = max(x.a, a[i] + a[l]);
x.c = x.a + x.b;
t.point_update(id, x);
}
}
for(pair<int, int> p : queries[l]) {
ans[p.second] = t.query(l, p.first).c;
}
}
for(int i = 1; i <= q; ++i) {
cout << ans[i] << " \n"[i == n];
}
}
Compilation message
jumps.cpp: In instantiation of 'T segment_tree<T, Lambda>::query(int, int, int, int, int) [with T = node; Lambda = main()::<lambda(const node&, const node&)>]':
jumps.cpp:72:32: required from 'T segment_tree<T, Lambda>::query(int, int) [with T = node; Lambda = main()::<lambda(const node&, const node&)>]'
jumps.cpp:154:38: required from here
jumps.cpp:95:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
95 | int middle = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9704 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 5 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 6 |
Correct |
6 ms |
9652 KB |
Output is correct |
| 7 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 8 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 9 |
Correct |
8 ms |
9700 KB |
Output is correct |
| 10 |
Correct |
6 ms |
9676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9704 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 5 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 6 |
Correct |
6 ms |
9652 KB |
Output is correct |
| 7 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 8 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 9 |
Correct |
8 ms |
9700 KB |
Output is correct |
| 10 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 11 |
Runtime error |
324 ms |
39448 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
290 ms |
31844 KB |
Output is correct |
| 2 |
Correct |
198 ms |
31476 KB |
Output is correct |
| 3 |
Correct |
197 ms |
32400 KB |
Output is correct |
| 4 |
Correct |
288 ms |
31768 KB |
Output is correct |
| 5 |
Correct |
282 ms |
31800 KB |
Output is correct |
| 6 |
Correct |
268 ms |
31192 KB |
Output is correct |
| 7 |
Correct |
261 ms |
30916 KB |
Output is correct |
| 8 |
Correct |
266 ms |
31004 KB |
Output is correct |
| 9 |
Correct |
276 ms |
31380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9704 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 4 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 5 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 6 |
Correct |
6 ms |
9652 KB |
Output is correct |
| 7 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 8 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 9 |
Correct |
8 ms |
9700 KB |
Output is correct |
| 10 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 11 |
Runtime error |
324 ms |
39448 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
