#include <bits/stdc++.h>
using namespace std;
const int nmax = 5e5 + 5;
const int nextpow = 1 << 20;
const int inf = 1e9;
int n;
vector<int> v;
namespace AINT {
struct Node {
int vab, x, sum;
Node operator +(const Node& a) const {
return Node{max(vab, a.vab), max(x, a.x), max(sum, a.sum)};
}
void tag(const int& a) {
if(vab < a)
vab = a, sum = a + x;
}
} aint[nextpow], iden = Node{-inf, -inf, -inf};
int lazy[nextpow];
void apply(int node, int cl, int cr) {
if(lazy[node] == -1)
return;
aint[node].tag(lazy[node]);
if(cl != cr) {
lazy[2 * node] = max(lazy[node], lazy[2 * node]);
lazy[2 * node + 1] = max(lazy[node], lazy[2 * node + 1]);
}
lazy[node] = -1;
}
void prop(int node, int cl, int cr) {
apply(node, cl, cr);
if(cl == cr)
return;
int mid = cl + cr >> 1;
apply(2 * node, cl, mid);
apply(2 * node + 1, mid + 1, cr);
}
void upd(int l, int r, int val, int node = 1, int cl = 0, int cr = n) {
if(cr < l || r < cl)
return;
prop(node, cl, cr);
if(l <= cl && cr <= r) {
//cout << "cine " << l << ' ' << cl << ' ' << cr << ' ' << r << " +" << val << '\n';
lazy[node] = val;
prop(node, cl, cr);
return;
}
int mid = cl + cr >> 1;
upd(l, r, val, 2 * node, cl, mid);
upd(l, r, val, 2 * node + 1, mid + 1, cr);
aint[node] = aint[2 * node] + aint[2 * node + 1];
}
Node query(int l, int r, int node = 1, int cl = 0, int cr = n) {
prop(node, cl, cr);
if(cr < l || r < cl)
return iden;
if(l <= cl && cr <= r) {
//cout << "cum " << l << ' ' << cl << ' ' << cr << ' ' << r << ' ' << aint[node].x << ' ' << aint[node].vab << ' ' << aint[node].sum << '\n';
return aint[node];
}
int mid = cl + cr >> 1;
Node rez = query(l, r, 2 * node, cl, mid) + query(l, r, 2 * node + 1, mid + 1, cr);
return rez;
}
int qry(int l, int r) {
return query(l, r).sum;
}
void construct(int node = 1, int cl = 0, int cr = n) {
aint[node] = iden;
if(cl == cr) {
aint[node].x = v[cl];
return;
}
int mid = cl + cr >> 1;
construct(2 * node, cl, mid);
construct(2 * node + 1, mid + 1, cr);
aint[node] = aint[2 * node] + aint[2 * node + 1];
return;
}
};
vector<tuple<int,int,int> > rez;
vector<int> qs[nmax];
static void candid(int l, int r) {
int sim = r + (r - l);
if(sim >= n)
return;
//cout << l << ' ' << r << ' ' <<sim << ' ' << n << '\n';
AINT::upd(sim, n, v[l] + v[r]);
return;
}
int main() {
int q;
cin >> n;
v.resize(n);
#define stack deobiceicineintreaba
vector<int> stack;
for(auto &x : v) cin >> x;
stack.push_back(n);
v.push_back(-3e8 -5);
AINT::construct();
v.back() *= -1;
//cerr << v.size() << '\n',
cin >> q;
rez.resize(q);
int i = 0;
for(auto &[a, b, c] : rez)
cin >> a >> b, --a, --b, c = 0, qs[a].push_back(i++);
int l, r, val;
for(int i = n - 1; i >= 0; i--) {
do {
//cerr << stack.size() << ' ' << stack.back() << '\n';
candid(i, stack.back());
} while((v[stack.back()] < v[i] ? stack.pop_back(), true : false));
stack.push_back(i);
for(auto x : qs[i]) {
tie(l, r, val) = rez[x];
val = AINT::qry(l, r);
//cout << val << '\n';
rez[x] = {l, r, val};
}
}
for(auto [a, b, c] : rez)
cout << c << '\n';
}
Compilation message
jumps.cpp: In function 'void AINT::prop(int, int, int)':
jumps.cpp:38:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid = cl + cr >> 1;
| ~~~^~~~
jumps.cpp: In function 'void AINT::upd(int, int, int, int, int, int)':
jumps.cpp:52:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid = cl + cr >> 1;
| ~~~^~~~
jumps.cpp: In function 'AINT::Node AINT::query(int, int, int, int, int)':
jumps.cpp:65:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid = cl + cr >> 1;
| ~~~^~~~
jumps.cpp: In function 'void AINT::construct(int, int, int)':
jumps.cpp:78:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | int mid = cl + cr >> 1;
| ~~~^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:114:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
114 | for(auto &[a, b, c] : rez)
| ^
jumps.cpp:130:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
130 | for(auto [a, b, c] : rez)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
12056 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
12056 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
299 ms |
22772 KB |
Output is correct |
| 2 |
Correct |
215 ms |
24576 KB |
Output is correct |
| 3 |
Correct |
219 ms |
22668 KB |
Output is correct |
| 4 |
Correct |
317 ms |
22692 KB |
Output is correct |
| 5 |
Correct |
340 ms |
22728 KB |
Output is correct |
| 6 |
Incorrect |
292 ms |
22048 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
12056 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
