///
/// Oh? You're approaching me?
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;
const int N = 500010;
const int inf = 5e8;
int arr[N];
int n, q;
namespace seg{
int lzy[N<<2], mx[N<<2], mxc[N<<2];
void tag(int i, int x){
mx[i] = max(mx[i], mxc[i]+x);
lzy[i] = max(lzy[i], x);
}
void ppg(int i){
if(lzy[i]>-inf){
tag(2*i+1, lzy[i]);
tag(2*i+2, lzy[i]);
lzy[i]=-inf;
}
}
void init(int i=0, int b=0, int e=n){
lzy[i]=-inf; mx[i]=-inf;
if(e-b==1) {mxc[i] = arr[b]; return;}
init(2*i+1,b,(b+e)/2);
init(2*i+2,(b+e)/2,e);
mxc[i] = max(mxc[2*i+1], mxc[2*i+2]);
}
void up(int l, int r, int x, int i=0, int b=0, int e=n){
if(l<=b&&e<=r) return tag(i, x);
if(r<=b||e<=l) return;
ppg(i);
up(l,r,x,2*i+1,b,(b+e)/2);
up(l,r,x,2*i+2,(b+e)/2,e);
mx[i] = max(mx[2*i+1], mx[2*i+2]);
}
int get(int l, int r, int i=0, int b=0, int e=n){
if(l<=b&&e<=r) return mx[i];
if(r<=b||e<=l) return -inf;
ppg(i);
return max(
get(l,r,2*i+1,b,(b+e)/2),
get(l,r,2*i+2,(b+e)/2,e)
);
}
}
//namespace seg{
// int mx[N];
// void init(){
// Loop(i,0,N) mx[i] = -inf;
// }
// int get(int l, int r){
// int ans=0;
// Loop(i,l,r) ans = max(ans,mx[i]);
// return ans;
// }
// void up(int l, int r, int x){
// Loop(i,l,r) mx[i] = max(mx[i],x+arr[i]);
// }
//}
vector<pii> ql[N];
vector<int> cand[N];
int ans[N];
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n;
Loop(i,0,n) cin >> arr[i];
seg::init();
vector<int> st;
Loop(i,0,n){
while(st.size() && arr[st.back()] < arr[i])
st.pop_back();
if(st.size())
cand[st.back()].push_back(i);
st.push_back(i);
}
st.clear();
LoopR(i,0,n){
while(st.size() && arr[st.back()] < arr[i])
st.pop_back();
if(st.size())
cand[i].push_back(st.back());
st.push_back(i);
}
cin >> q;
Loop(i,0,q){
int l, r;
cin >> l >> r; --l;
ql[l].push_back({i,r});
}
LoopR(i,0,n){
for(int j : cand[i]){
// cout << i << ' ' << j << '\n';
if(2*j-i<n) seg::up(2*j-i,n,arr[i]+arr[j]);
}
for(auto [j, r] : ql[i]){
ans[j] = seg::get(i,r);
}
}
Loop(i,0,q) cout << ans[i] << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23800 KB |
Output is correct |
2 |
Correct |
13 ms |
23760 KB |
Output is correct |
3 |
Correct |
13 ms |
23828 KB |
Output is correct |
4 |
Correct |
15 ms |
23760 KB |
Output is correct |
5 |
Correct |
13 ms |
23760 KB |
Output is correct |
6 |
Correct |
13 ms |
23824 KB |
Output is correct |
7 |
Correct |
13 ms |
23824 KB |
Output is correct |
8 |
Correct |
15 ms |
23888 KB |
Output is correct |
9 |
Correct |
16 ms |
23956 KB |
Output is correct |
10 |
Correct |
13 ms |
23760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23800 KB |
Output is correct |
2 |
Correct |
13 ms |
23760 KB |
Output is correct |
3 |
Correct |
13 ms |
23828 KB |
Output is correct |
4 |
Correct |
15 ms |
23760 KB |
Output is correct |
5 |
Correct |
13 ms |
23760 KB |
Output is correct |
6 |
Correct |
13 ms |
23824 KB |
Output is correct |
7 |
Correct |
13 ms |
23824 KB |
Output is correct |
8 |
Correct |
15 ms |
23888 KB |
Output is correct |
9 |
Correct |
16 ms |
23956 KB |
Output is correct |
10 |
Correct |
13 ms |
23760 KB |
Output is correct |
11 |
Correct |
302 ms |
42816 KB |
Output is correct |
12 |
Correct |
318 ms |
42676 KB |
Output is correct |
13 |
Correct |
270 ms |
42864 KB |
Output is correct |
14 |
Correct |
266 ms |
42752 KB |
Output is correct |
15 |
Correct |
335 ms |
42820 KB |
Output is correct |
16 |
Correct |
267 ms |
42176 KB |
Output is correct |
17 |
Correct |
266 ms |
42096 KB |
Output is correct |
18 |
Correct |
255 ms |
42068 KB |
Output is correct |
19 |
Correct |
271 ms |
42684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
135 ms |
39112 KB |
Output is correct |
2 |
Correct |
82 ms |
39560 KB |
Output is correct |
3 |
Correct |
96 ms |
39556 KB |
Output is correct |
4 |
Correct |
148 ms |
39092 KB |
Output is correct |
5 |
Correct |
138 ms |
38996 KB |
Output is correct |
6 |
Correct |
130 ms |
38332 KB |
Output is correct |
7 |
Correct |
136 ms |
38224 KB |
Output is correct |
8 |
Correct |
127 ms |
38172 KB |
Output is correct |
9 |
Correct |
132 ms |
38464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23800 KB |
Output is correct |
2 |
Correct |
13 ms |
23760 KB |
Output is correct |
3 |
Correct |
13 ms |
23828 KB |
Output is correct |
4 |
Correct |
15 ms |
23760 KB |
Output is correct |
5 |
Correct |
13 ms |
23760 KB |
Output is correct |
6 |
Correct |
13 ms |
23824 KB |
Output is correct |
7 |
Correct |
13 ms |
23824 KB |
Output is correct |
8 |
Correct |
15 ms |
23888 KB |
Output is correct |
9 |
Correct |
16 ms |
23956 KB |
Output is correct |
10 |
Correct |
13 ms |
23760 KB |
Output is correct |
11 |
Correct |
302 ms |
42816 KB |
Output is correct |
12 |
Correct |
318 ms |
42676 KB |
Output is correct |
13 |
Correct |
270 ms |
42864 KB |
Output is correct |
14 |
Correct |
266 ms |
42752 KB |
Output is correct |
15 |
Correct |
335 ms |
42820 KB |
Output is correct |
16 |
Correct |
267 ms |
42176 KB |
Output is correct |
17 |
Correct |
266 ms |
42096 KB |
Output is correct |
18 |
Correct |
255 ms |
42068 KB |
Output is correct |
19 |
Correct |
271 ms |
42684 KB |
Output is correct |
20 |
Correct |
135 ms |
39112 KB |
Output is correct |
21 |
Correct |
82 ms |
39560 KB |
Output is correct |
22 |
Correct |
96 ms |
39556 KB |
Output is correct |
23 |
Correct |
148 ms |
39092 KB |
Output is correct |
24 |
Correct |
138 ms |
38996 KB |
Output is correct |
25 |
Correct |
130 ms |
38332 KB |
Output is correct |
26 |
Correct |
136 ms |
38224 KB |
Output is correct |
27 |
Correct |
127 ms |
38172 KB |
Output is correct |
28 |
Correct |
132 ms |
38464 KB |
Output is correct |
29 |
Correct |
887 ms |
82084 KB |
Output is correct |
30 |
Correct |
731 ms |
83588 KB |
Output is correct |
31 |
Correct |
732 ms |
83532 KB |
Output is correct |
32 |
Correct |
901 ms |
82048 KB |
Output is correct |
33 |
Correct |
887 ms |
82176 KB |
Output is correct |
34 |
Correct |
876 ms |
79916 KB |
Output is correct |
35 |
Correct |
874 ms |
79832 KB |
Output is correct |
36 |
Correct |
874 ms |
79592 KB |
Output is correct |
37 |
Correct |
882 ms |
80968 KB |
Output is correct |
38 |
Correct |
636 ms |
87804 KB |
Output is correct |
39 |
Correct |
629 ms |
87840 KB |
Output is correct |
40 |
Correct |
627 ms |
84532 KB |
Output is correct |
41 |
Correct |
620 ms |
84060 KB |
Output is correct |
42 |
Correct |
624 ms |
84052 KB |
Output is correct |
43 |
Correct |
621 ms |
85840 KB |
Output is correct |
44 |
Correct |
675 ms |
87164 KB |
Output is correct |
45 |
Correct |
662 ms |
87220 KB |
Output is correct |
46 |
Correct |
654 ms |
84072 KB |
Output is correct |
47 |
Correct |
650 ms |
83676 KB |
Output is correct |
48 |
Correct |
677 ms |
83632 KB |
Output is correct |
49 |
Correct |
655 ms |
85652 KB |
Output is correct |
50 |
Correct |
738 ms |
85484 KB |
Output is correct |
51 |
Correct |
767 ms |
85320 KB |
Output is correct |
52 |
Correct |
726 ms |
82888 KB |
Output is correct |
53 |
Correct |
740 ms |
82504 KB |
Output is correct |
54 |
Correct |
727 ms |
82548 KB |
Output is correct |
55 |
Correct |
740 ms |
84232 KB |
Output is correct |