#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 = 5e5 + 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 |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 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 |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
275 ms |
13584 KB |
Output is correct |
12 |
Correct |
253 ms |
13496 KB |
Output is correct |
13 |
Correct |
253 ms |
13592 KB |
Output is correct |
14 |
Correct |
260 ms |
13552 KB |
Output is correct |
15 |
Correct |
255 ms |
13636 KB |
Output is correct |
16 |
Correct |
269 ms |
12988 KB |
Output is correct |
17 |
Correct |
253 ms |
13016 KB |
Output is correct |
18 |
Correct |
250 ms |
12956 KB |
Output is correct |
19 |
Correct |
261 ms |
13580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
133 ms |
16460 KB |
Output is correct |
2 |
Correct |
76 ms |
15716 KB |
Output is correct |
3 |
Correct |
88 ms |
14956 KB |
Output is correct |
4 |
Correct |
133 ms |
16640 KB |
Output is correct |
5 |
Correct |
133 ms |
16548 KB |
Output is correct |
6 |
Correct |
127 ms |
16568 KB |
Output is correct |
7 |
Correct |
146 ms |
16488 KB |
Output is correct |
8 |
Correct |
134 ms |
16536 KB |
Output is correct |
9 |
Correct |
135 ms |
16564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
275 ms |
13584 KB |
Output is correct |
12 |
Correct |
253 ms |
13496 KB |
Output is correct |
13 |
Correct |
253 ms |
13592 KB |
Output is correct |
14 |
Correct |
260 ms |
13552 KB |
Output is correct |
15 |
Correct |
255 ms |
13636 KB |
Output is correct |
16 |
Correct |
269 ms |
12988 KB |
Output is correct |
17 |
Correct |
253 ms |
13016 KB |
Output is correct |
18 |
Correct |
250 ms |
12956 KB |
Output is correct |
19 |
Correct |
261 ms |
13580 KB |
Output is correct |
20 |
Correct |
133 ms |
16460 KB |
Output is correct |
21 |
Correct |
76 ms |
15716 KB |
Output is correct |
22 |
Correct |
88 ms |
14956 KB |
Output is correct |
23 |
Correct |
133 ms |
16640 KB |
Output is correct |
24 |
Correct |
133 ms |
16548 KB |
Output is correct |
25 |
Correct |
127 ms |
16568 KB |
Output is correct |
26 |
Correct |
146 ms |
16488 KB |
Output is correct |
27 |
Correct |
134 ms |
16536 KB |
Output is correct |
28 |
Correct |
135 ms |
16564 KB |
Output is correct |
29 |
Incorrect |
684 ms |
43536 KB |
Output isn't correct |
30 |
Halted |
0 ms |
0 KB |
- |