#include<bits/stdc++.h>
#define task "C"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 1e6 + 5;
const ll INF = 1e18 + 5;
int n, q;
int a[MAXN];
struct TQuery
{
int l, r, id;
};
TQuery qu[MAXN];
void Input()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
cin >> q;
for (int i = 1; i <= q; i++)
{
cin >> qu[i].l >> qu[i].r;
qu[i].id = i;
}
}
pair<ll, int> st[4 * MAXN];
ll lazy[4 * MAXN];
pair<ll, int> Comb(const pair<ll, int>& l, const pair<ll, int>& r)
{
return make_pair(max(l.fi, r.fi), max(l.se, r.se));
}
void Build(int id, int l, int r)
{
if (l == r)
{
st[id] = {a[l], a[l]};
return;
}
int mid = (l + r) / 2;
Build(2 * id, l, mid);
Build(2 * id + 1, mid + 1, r);
st[id] = Comb(st[2 * id], st[2 * id + 1]);
}
pair<int, int> seg[MAXN];
int nseg = 0;
void down(int id)
{
ll& t = lazy[id];
if (!t)
return;
st[2 * id].fi = max(st[2 * id].fi, st[2 * id].se + t);
st[2 * id + 1].fi = max(st[2 * id + 1].fi, st[2 * id + 1].se + t);
lazy[2 * id] = max(lazy[2 * id], t);
lazy[2 * id + 1] = max(lazy[2 * id + 1], t);
t = 0;
return;
}
void Update(int id, int l, int r, int u, int v, ll val)
{
if (u > v)
return;
if (r < u || v < l)
return;
if (u <= l && r <= v)
{
st[id].fi = max(st[id].fi, val + st[id].se);
lazy[id] = max(lazy[id], val);
return;
}
down(id);
int mid = (l + r) / 2;
Update(2 * id, l, mid, u, v, val);
Update(2 * id + 1, mid + 1, r, u, v, val);
st[id] = Comb(st[2 * id], st[2 * id + 1]);
}
ll Get(int id, int l, int r, int u, int v)
{
if (r < u || v < l)
return 0;
if (u <= l && r <= v)
{
return st[id].fi;
}
down(id);
int mid = (l + r) / 2;
return max(Get(2 * id, l, mid, u, v), Get(2 * id + 1, mid + 1, r, u, v));
}
int ans[MAXN];
void Solve()
{
Build(1, 1, n);
stack<int> S;
for (int i = n; i >= 1; i--)
{
while (!S.empty() && a[i] > a[S.top()])
{
seg[++nseg] = make_pair(i, S.top());
S.pop();
}
if (!S.empty())
seg[++nseg] = make_pair(i, S.top());
S.push(i);
}
sort(qu + 1, qu + q + 1, [](const auto& i, const auto& j)
{
return i.l > j.l;
});
sort(seg + 1, seg + nseg + 1, [](const auto& i, const auto& j)
{
return i.fi > j.fi;
});
int j = 1;
for (int i = 1; i <= q; i++)
{
while (j <= nseg && seg[j].fi >= qu[i].l)
{
Update(1, 1, n, 2 * seg[j].se - seg[j].fi, n, a[seg[j].se] + a[seg[j].fi]);
j++;
}
ans[qu[i].id] = Get(1, 1, n, qu[i].l, qu[i].r);
}
for (int i = 1; i <= q; i++)
cout << ans[i] << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(task".INP","r"))
{
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
Input();
Solve();
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
147 | freopen(task".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
272 ms |
13608 KB |
Output is correct |
12 |
Correct |
246 ms |
13608 KB |
Output is correct |
13 |
Correct |
267 ms |
13588 KB |
Output is correct |
14 |
Correct |
257 ms |
13572 KB |
Output is correct |
15 |
Correct |
251 ms |
13600 KB |
Output is correct |
16 |
Correct |
275 ms |
12976 KB |
Output is correct |
17 |
Correct |
247 ms |
13004 KB |
Output is correct |
18 |
Correct |
256 ms |
12992 KB |
Output is correct |
19 |
Correct |
248 ms |
13528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
137 ms |
16560 KB |
Output is correct |
2 |
Correct |
75 ms |
15804 KB |
Output is correct |
3 |
Correct |
76 ms |
14968 KB |
Output is correct |
4 |
Correct |
130 ms |
16520 KB |
Output is correct |
5 |
Correct |
130 ms |
16560 KB |
Output is correct |
6 |
Correct |
126 ms |
16560 KB |
Output is correct |
7 |
Correct |
134 ms |
16532 KB |
Output is correct |
8 |
Correct |
151 ms |
16536 KB |
Output is correct |
9 |
Correct |
128 ms |
16476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
272 ms |
13608 KB |
Output is correct |
12 |
Correct |
246 ms |
13608 KB |
Output is correct |
13 |
Correct |
267 ms |
13588 KB |
Output is correct |
14 |
Correct |
257 ms |
13572 KB |
Output is correct |
15 |
Correct |
251 ms |
13600 KB |
Output is correct |
16 |
Correct |
275 ms |
12976 KB |
Output is correct |
17 |
Correct |
247 ms |
13004 KB |
Output is correct |
18 |
Correct |
256 ms |
12992 KB |
Output is correct |
19 |
Correct |
248 ms |
13528 KB |
Output is correct |
20 |
Correct |
137 ms |
16560 KB |
Output is correct |
21 |
Correct |
75 ms |
15804 KB |
Output is correct |
22 |
Correct |
76 ms |
14968 KB |
Output is correct |
23 |
Correct |
130 ms |
16520 KB |
Output is correct |
24 |
Correct |
130 ms |
16560 KB |
Output is correct |
25 |
Correct |
126 ms |
16560 KB |
Output is correct |
26 |
Correct |
134 ms |
16532 KB |
Output is correct |
27 |
Correct |
151 ms |
16536 KB |
Output is correct |
28 |
Correct |
128 ms |
16476 KB |
Output is correct |
29 |
Correct |
908 ms |
47500 KB |
Output is correct |
30 |
Correct |
661 ms |
56588 KB |
Output is correct |
31 |
Correct |
650 ms |
54560 KB |
Output is correct |
32 |
Correct |
825 ms |
58524 KB |
Output is correct |
33 |
Correct |
813 ms |
58592 KB |
Output is correct |
34 |
Correct |
833 ms |
56228 KB |
Output is correct |
35 |
Correct |
805 ms |
55888 KB |
Output is correct |
36 |
Correct |
823 ms |
56140 KB |
Output is correct |
37 |
Correct |
806 ms |
57440 KB |
Output is correct |
38 |
Correct |
629 ms |
58608 KB |
Output is correct |
39 |
Correct |
643 ms |
58476 KB |
Output is correct |
40 |
Correct |
615 ms |
55316 KB |
Output is correct |
41 |
Correct |
609 ms |
54668 KB |
Output is correct |
42 |
Correct |
630 ms |
54736 KB |
Output is correct |
43 |
Correct |
625 ms |
56496 KB |
Output is correct |
44 |
Correct |
650 ms |
58660 KB |
Output is correct |
45 |
Correct |
639 ms |
58492 KB |
Output is correct |
46 |
Correct |
646 ms |
55340 KB |
Output is correct |
47 |
Correct |
656 ms |
55208 KB |
Output is correct |
48 |
Correct |
695 ms |
54948 KB |
Output is correct |
49 |
Correct |
657 ms |
57012 KB |
Output is correct |
50 |
Correct |
819 ms |
58520 KB |
Output is correct |
51 |
Correct |
741 ms |
58564 KB |
Output is correct |
52 |
Correct |
747 ms |
56068 KB |
Output is correct |
53 |
Correct |
757 ms |
55760 KB |
Output is correct |
54 |
Correct |
830 ms |
55812 KB |
Output is correct |
55 |
Correct |
767 ms |
57396 KB |
Output is correct |