#include <bits/stdc++.h>
using namespace std;
const int N = 500000;
int v[N],v2[N],n;
struct query{
int l,r,id;
}v3[N];
int ans[N];
bool cmp(query a,query b){
return a.l < b.l;
}
tuple <int,int,int> seg[4*N];
tuple<int,int,int> operator+(tuple<int,int,int> &a,tuple<int,int,int> &b){
return {max(get<0>(a),get<0>(b)),max(get<1>(a),get<1>(b)),0};
}
///1 2 -> normal,ans
///3 -> lazy max
void build(int l,int r,int node = 1){
if(l == r)seg[node] = {v[l],0,0};
else{
int mij = (l + r)/2;
build(l,mij,node*2);
build(mij + 1,r,node*2 + 1);
seg[node] = seg[node*2] + seg[node*2 + 1];
}
//cout<<l<<' '<<r<<' '<<node<<' '<<get<0>(seg[node])<<'\n';
};
void push(int node,bool single){
if(!get<2>(seg[node]))return;
//cout<<node<<' '<<get<0>(seg[node])<<' '<<get<2>(seg[node])<<' ';
get<1>(seg[node]) = max(get<1>(seg[node]),get<0>(seg[node]) + get<2>(seg[node]));
//cout<<get<1>(seg[node])<<'\n';
if(!single){
get<2>(seg[node*2]) = max(get<2>(seg[node*2]),get<2>(seg[node]));
get<2>(seg[node*2+1]) = max(get<2>(seg[node*2 + 1]),get<2>(seg[node]));
}
get<2>(seg[node]) = 0;
}
void upd(int l,int r,int val,int l2 = 0,int r2 = n - 1,int node = 1){
//if(l2 == 0 && r2 == n - 1)cout<<l<<' '<<r<<' '<<val<<'\n';
push(node,l==r);
if(r2 < l || r < l2)return;
if(l <= l2 && r2 <= r){
//cout<<l2<<' '<<r2<<'\n';
get<2>(seg[node])+=val;
push(node,l==r);
}else{
//cout<<l2<<' '<<r2<<'\n';
int mij = (l2 + r2)/2;
upd(l,r,val,l2,mij,node*2);
upd(l,r,val,mij + 1,r2,node*2 + 1);
seg[node] = seg[node*2] + seg[node*2 + 1];
}
}
tuple <int,int,int> query(int l,int r,int l2 = 0,int r2 = n - 1,int node = 1){
push(node,l==r);
if(r2 < l || r < l2)return {-2e9,-2e9,0};
if(l <= l2 && r2 <= r){
return seg[node];
}else{
int mij = (l2 + r2)/2;
tuple<int,int,int> l3 = query(l,r,l2,mij,node*2);
tuple<int,int,int> r3 = query(l,r,mij + 1,r2,node*2 + 1);
return l3+r3;
}
}
int main(){
int q,i,cnt = -1,p,j;
cin>>n;
for(i = 0;i < n;i++){
cin>>v[i];
}
cin>>q;
for(i = 0;i < q;i++){
cin>>v3[i].l>>v3[i].r;v3[i].id = i;
v3[i].l--;v3[i].r--;
}
build(0,n - 1);
/*for(j = 0;j < 4*n;j++){
cout<<j<<' '<<get<0>(seg[j])<<' '<<get<1>(seg[j])<<' '<<get<2>(seg[j])<<'\n';
}
cout<<'\n';*/
sort(v3,v3 + q,cmp);
p = q - 1;
for(i = n - 1;i >= 0;i--){
while(cnt >= 0 && v[i] >= v[v2[cnt]]){
//cout<<i<<' '<<v2[cnt]<<'\n';
if(v2[cnt]*2 - i <= n - 1){
upd(v2[cnt]*2 - i,n - 1,v[i] + v[v2[cnt]]);
//cout<<v2[cnt]<<' '<<i<<'\n';
/*for(j = 0;j < 4*n;j++){
cout<<j<<' '<<get<0>(seg[j])<<' '<<get<1>(seg[j])<<' '<<get<2>(seg[j])<<'\n';
}
cout<<'\n';*/
}
cnt--;
}
if(cnt >= 0 && v2[cnt]*2 - i <= n - 1){
upd(v2[cnt]*2 - i,n - 1,v[i] + v[v2[cnt]]);
//cout<<v2[cnt]<<' '<<i<<'\n';
/*for(j = 0;j < 4*n;j++){
cout<<j<<' '<<get<0>(seg[j])<<' '<<get<1>(seg[j])<<' '<<get<2>(seg[j])<<'\n';
}
cout<<'\n';*/
}
while(p >= 0 && i == v3[p].l){
ans[v3[p].id] = get<1>(query(v3[p].l,v3[p].r));
//cout<<v3[p].id<<'\n';
p--;
}
///add
v2[++cnt] = i;
}
for(i = 0;i < q;i++)cout<<ans[i]<<'\n';
return 0;
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:68:24: warning: unused variable 'j' [-Wunused-variable]
68 | int q,i,cnt = -1,p,j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
202 ms |
13636 KB |
Output is correct |
| 2 |
Correct |
127 ms |
14256 KB |
Output is correct |
| 3 |
Correct |
149 ms |
13448 KB |
Output is correct |
| 4 |
Correct |
189 ms |
13564 KB |
Output is correct |
| 5 |
Correct |
202 ms |
13472 KB |
Output is correct |
| 6 |
Correct |
180 ms |
13524 KB |
Output is correct |
| 7 |
Correct |
172 ms |
13416 KB |
Output is correct |
| 8 |
Correct |
180 ms |
13600 KB |
Output is correct |
| 9 |
Correct |
198 ms |
13476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
