#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 505050
#define MAXS 20
#define INF 1e9
#define bb ' '
#define ln '\n'
#define Ln '\n'
#ifdef _MSC_VER
# include <intrin.h>
# define __builtin_popcount __popcnt
#endif
#define MOD 1000000007
struct segtree {
int s;
vector<int> tree, lazy, l, r;
void init(int x = 1) {
if (x >= s) {
l[x] = r[x] = x - s + 1;
return;
}
init(x * 2);
init(x * 2 + 1);
tree[x] = max(tree[x + 1], tree[x * 2 + 1]);
l[x] = l[x * 2];
r[x] = r[x * 2 + 1];
}
segtree() {}
segtree(int N) {
s = 1 << (int)ceil(log2(N));
tree = lazy = l = r = vector<int>(2 * s + 1);
}
void prop(int x) {
if (x >= s) return;
for (auto c : { 2 * x, 2 * x + 1 }) {
tree[c] += lazy[x];
lazy[c] += lazy[x];
}
lazy[x] = 0;
}
void update(int low, int high, int x, int loc = 1) {
prop(loc);
if (low == l[loc] && high == r[loc]) {
tree[loc] += x;
lazy[loc] += x;
}
else {
if (high <= r[loc * 2]) update(low, high, x, loc * 2);
else if (low >= l[loc * 2 + 1]) update(low, high, x, loc * 2 + 1);
else update(low, r[loc * 2], x, loc * 2), update(l[loc * 2 + 1], high, x, loc * 2 + 1);
tree[loc] = max(tree[loc * 2], tree[loc * 2 + 1]);
}
}
int query(int low, int high, int loc = 1) {
prop(loc);
if (low == l[loc] && high == r[loc]) return tree[loc];
if (high <= r[loc * 2]) return query(low, high, loc * 2);
if (low >= l[loc * 2 + 1]) return query(low, high, loc * 2 + 1);
return max(query(low, r[loc * 2], loc * 2), query(l[loc * 2 + 1], high, loc * 2 + 1));
}
};
int A[MAX];
pii query[MAX];
vector<int> st[MAX], qst[MAX];
int ans[MAX];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N;
cin >> N;
int i;
stack<int> s;
segtree seg(N);
for (i = 1; i <= N; i++) cin >> A[i], seg.tree[i + seg.s - 1] = A[i];
seg.init();
for (i = 1; i <= N; i++) {
while (s.size()) {
st[s.top()].push_back(i);
if (A[s.top()] > A[i]) break;
else s.pop();
}
s.push(i);
}
int Q;
cin >> Q;
int a, b;
for (i = 1; i <= Q; i++) {
cin >> a >> b;
query[i] = pii(a, b);
qst[a].push_back(i);
}
set<pii> vpi;
vpi.emplace(0, 0);
vpi.emplace(N + 1, INF);
for (i = N; i >= 1; i--) {
for (auto v : st[i]) {
int e = 2 * v - i;
if (e > N) continue;
int X = A[i] + A[v];
auto it = vpi.upper_bound(pii(e, INF));
it--;
if (it->second > X) continue;
if (it->first == e) {
int xx = it->second;
int r = next(it)->first;
seg.update(e, r - 1, X - xx);
vpi.erase(it);
vpi.emplace(e, X);
continue;
}
int p = it->second;
auto it2 = next(it);
vector<pii> er;
for (; it2 != vpi.end(); it2++) {
if (it2->second > X) break;
auto it3 = next(it2);
seg.update(it2->first, it3->first - 1, p - it2->second);
er.push_back(*it2);
}
for (auto v : er) vpi.erase(v);
it2 = next(it);
seg.update(e, it2->first - 1, X - it->second);
vpi.emplace(e, X);
}
for (auto q : qst[i]) ans[q] = seg.query(query[q].first, query[q].second);
}
for (i = 1; i <= Q; i++) cout << ans[i] << ln;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
24020 KB |
Output is correct |
| 2 |
Correct |
13 ms |
24060 KB |
Output is correct |
| 3 |
Correct |
16 ms |
24064 KB |
Output is correct |
| 4 |
Correct |
17 ms |
24080 KB |
Output is correct |
| 5 |
Incorrect |
13 ms |
24020 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
24020 KB |
Output is correct |
| 2 |
Correct |
13 ms |
24060 KB |
Output is correct |
| 3 |
Correct |
16 ms |
24064 KB |
Output is correct |
| 4 |
Correct |
17 ms |
24080 KB |
Output is correct |
| 5 |
Incorrect |
13 ms |
24020 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
460 ms |
41288 KB |
Output is correct |
| 2 |
Correct |
221 ms |
50380 KB |
Output is correct |
| 3 |
Correct |
543 ms |
41892 KB |
Output is correct |
| 4 |
Correct |
466 ms |
41380 KB |
Output is correct |
| 5 |
Correct |
466 ms |
41264 KB |
Output is correct |
| 6 |
Correct |
457 ms |
40644 KB |
Output is correct |
| 7 |
Correct |
502 ms |
40544 KB |
Output is correct |
| 8 |
Correct |
467 ms |
40540 KB |
Output is correct |
| 9 |
Correct |
464 ms |
40824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
24020 KB |
Output is correct |
| 2 |
Correct |
13 ms |
24060 KB |
Output is correct |
| 3 |
Correct |
16 ms |
24064 KB |
Output is correct |
| 4 |
Correct |
17 ms |
24080 KB |
Output is correct |
| 5 |
Incorrect |
13 ms |
24020 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
