#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);
}
inline void prop(int x) {
if (!x) return;
if (x >= s) return;
for (auto c : { 2 * x, 2 * x + 1 }) {
tree[c] += lazy[x];
lazy[c] += lazy[x];
}
lazy[x] = 0;
}
inline 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]);
}
}
inline 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];
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;
vector<int> qv;
for (i = 1; i <= Q; i++) {
qv.push_back(i);
cin >> a >> b;
query[i] = pii(a, b);
}
sort(qv.begin(), qv.end(), [&](int i, int j) { return query[i].first < query[j].first; });
set<pii> vpi;
vpi.emplace(0, 0);
vpi.emplace(N + 1, INF);
int ptr = Q - 1;
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) {
auto pv = prev(it);
int xx = it->second;
int r = next(it)->first;
seg.update(e, r - 1, pv->second - xx);
vpi.erase(it);
it = pv;
}
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);
}
while (ptr >= 0 && query[qv[ptr]].first == i) ans[qv[ptr]] = seg.query(query[qv[ptr]].first, query[qv[ptr]].second), ptr--;
}
for (i = 1; i <= Q; i++) cout << ans[i] << ln;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12116 KB |
Output is correct |
2 |
Correct |
6 ms |
12116 KB |
Output is correct |
3 |
Correct |
8 ms |
12116 KB |
Output is correct |
4 |
Correct |
6 ms |
12116 KB |
Output is correct |
5 |
Correct |
7 ms |
12116 KB |
Output is correct |
6 |
Correct |
7 ms |
12116 KB |
Output is correct |
7 |
Correct |
6 ms |
12200 KB |
Output is correct |
8 |
Correct |
7 ms |
12116 KB |
Output is correct |
9 |
Correct |
9 ms |
12216 KB |
Output is correct |
10 |
Correct |
6 ms |
12116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12116 KB |
Output is correct |
2 |
Correct |
6 ms |
12116 KB |
Output is correct |
3 |
Correct |
8 ms |
12116 KB |
Output is correct |
4 |
Correct |
6 ms |
12116 KB |
Output is correct |
5 |
Correct |
7 ms |
12116 KB |
Output is correct |
6 |
Correct |
7 ms |
12116 KB |
Output is correct |
7 |
Correct |
6 ms |
12200 KB |
Output is correct |
8 |
Correct |
7 ms |
12116 KB |
Output is correct |
9 |
Correct |
9 ms |
12216 KB |
Output is correct |
10 |
Correct |
6 ms |
12116 KB |
Output is correct |
11 |
Correct |
609 ms |
25580 KB |
Output is correct |
12 |
Correct |
615 ms |
25604 KB |
Output is correct |
13 |
Correct |
622 ms |
25596 KB |
Output is correct |
14 |
Correct |
621 ms |
25512 KB |
Output is correct |
15 |
Correct |
617 ms |
25580 KB |
Output is correct |
16 |
Correct |
597 ms |
24868 KB |
Output is correct |
17 |
Correct |
568 ms |
24856 KB |
Output is correct |
18 |
Correct |
609 ms |
24940 KB |
Output is correct |
19 |
Correct |
598 ms |
25448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
511 ms |
27632 KB |
Output is correct |
2 |
Correct |
214 ms |
36740 KB |
Output is correct |
3 |
Correct |
509 ms |
28288 KB |
Output is correct |
4 |
Correct |
489 ms |
27688 KB |
Output is correct |
5 |
Correct |
492 ms |
27708 KB |
Output is correct |
6 |
Correct |
487 ms |
27684 KB |
Output is correct |
7 |
Correct |
479 ms |
27804 KB |
Output is correct |
8 |
Correct |
515 ms |
27816 KB |
Output is correct |
9 |
Correct |
468 ms |
27804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12116 KB |
Output is correct |
2 |
Correct |
6 ms |
12116 KB |
Output is correct |
3 |
Correct |
8 ms |
12116 KB |
Output is correct |
4 |
Correct |
6 ms |
12116 KB |
Output is correct |
5 |
Correct |
7 ms |
12116 KB |
Output is correct |
6 |
Correct |
7 ms |
12116 KB |
Output is correct |
7 |
Correct |
6 ms |
12200 KB |
Output is correct |
8 |
Correct |
7 ms |
12116 KB |
Output is correct |
9 |
Correct |
9 ms |
12216 KB |
Output is correct |
10 |
Correct |
6 ms |
12116 KB |
Output is correct |
11 |
Correct |
609 ms |
25580 KB |
Output is correct |
12 |
Correct |
615 ms |
25604 KB |
Output is correct |
13 |
Correct |
622 ms |
25596 KB |
Output is correct |
14 |
Correct |
621 ms |
25512 KB |
Output is correct |
15 |
Correct |
617 ms |
25580 KB |
Output is correct |
16 |
Correct |
597 ms |
24868 KB |
Output is correct |
17 |
Correct |
568 ms |
24856 KB |
Output is correct |
18 |
Correct |
609 ms |
24940 KB |
Output is correct |
19 |
Correct |
598 ms |
25448 KB |
Output is correct |
20 |
Correct |
511 ms |
27632 KB |
Output is correct |
21 |
Correct |
214 ms |
36740 KB |
Output is correct |
22 |
Correct |
509 ms |
28288 KB |
Output is correct |
23 |
Correct |
489 ms |
27688 KB |
Output is correct |
24 |
Correct |
492 ms |
27708 KB |
Output is correct |
25 |
Correct |
487 ms |
27684 KB |
Output is correct |
26 |
Correct |
479 ms |
27804 KB |
Output is correct |
27 |
Correct |
515 ms |
27816 KB |
Output is correct |
28 |
Correct |
468 ms |
27804 KB |
Output is correct |
29 |
Correct |
2324 ms |
59732 KB |
Output is correct |
30 |
Correct |
1590 ms |
82404 KB |
Output is correct |
31 |
Correct |
2392 ms |
61100 KB |
Output is correct |
32 |
Correct |
2328 ms |
59692 KB |
Output is correct |
33 |
Correct |
2326 ms |
59728 KB |
Output is correct |
34 |
Correct |
2667 ms |
59100 KB |
Output is correct |
35 |
Correct |
2451 ms |
58972 KB |
Output is correct |
36 |
Correct |
2528 ms |
58964 KB |
Output is correct |
37 |
Correct |
2540 ms |
59608 KB |
Output is correct |
38 |
Correct |
2242 ms |
59844 KB |
Output is correct |
39 |
Correct |
2052 ms |
59740 KB |
Output is correct |
40 |
Correct |
1973 ms |
58048 KB |
Output is correct |
41 |
Correct |
1983 ms |
57808 KB |
Output is correct |
42 |
Correct |
2025 ms |
57720 KB |
Output is correct |
43 |
Correct |
1932 ms |
58712 KB |
Output is correct |
44 |
Correct |
2064 ms |
59816 KB |
Output is correct |
45 |
Correct |
2017 ms |
59704 KB |
Output is correct |
46 |
Correct |
2015 ms |
58136 KB |
Output is correct |
47 |
Correct |
2073 ms |
58028 KB |
Output is correct |
48 |
Correct |
2096 ms |
58148 KB |
Output is correct |
49 |
Correct |
2074 ms |
59248 KB |
Output is correct |
50 |
Correct |
2126 ms |
59684 KB |
Output is correct |
51 |
Correct |
2125 ms |
59808 KB |
Output is correct |
52 |
Correct |
2111 ms |
58848 KB |
Output is correct |
53 |
Correct |
2075 ms |
58940 KB |
Output is correct |
54 |
Correct |
2186 ms |
58836 KB |
Output is correct |
55 |
Correct |
2116 ms |
59640 KB |
Output is correct |