/******************************************************************************
Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby,
C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, HTML, CSS, JS
Code, Compile, Run and Debug online from anywhere in world.
*******************************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define maxn 500000
int seg[4*maxn], lz[4*maxn], ma[4*maxn], arr[maxn];
void pushup(int x){
int s1 = 2*x, s2 = 2*x+1;
seg[x] = max(seg[x], lz[x]+ma[x]);
lz[s1]=max(lz[s1], lz[x]);
lz[s2]=max(lz[s2], lz[x]);
lz[x] = 0;
seg[x] = max(max(seg[x],seg[s1]), seg[s2]);
}
void update(int x, int l, int r, int a, int b, int v){
if(a<=l&&b>=r){
lz[x] = max(lz[x],v);
pushup(x);
}
else{
int s1 = 2*x, s2 = 2*x+1;
int m = (l+r)/2;
if(a<=m)update(s1, l, m, a, min(b, m), v);
if(b>m)update(s2, m+1, r, max(m+1, a), b, v);
pushup(x);
}
}
int query(int x, int l, int r, int a, int b){
if(a<=l&&b>=r){
pushup(x);
return seg[x];
}
else{
int s1 = 2*x, s2 = 2*x+1;
int m = (l+r)/2;
int ret = 0;
if(a<=m)ret = max(query(s1, l, m, a, min(b, m)),ret);
if(b>m)ret = max(query(s2, m+1, r, max(m+1, a), b),ret);
pushup(x);
return ret;
}
}
void setUp(int x, int l, int r) {
if(l==r){ma[x] = arr[l];
return;
}
setUp(2*x, l, (l+r)/2);
setUp(2*x+1, ((l+r)/2)+1, r);
ma[x] = max(ma[2*x], ma[2*x+1]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin>>n;
vector<vector<int>> pairs;
for(int i=0; i<n; i++)cin>>arr[i];
deque<int> vals;
deque<int> pos;
for(int i=0; i<n; i++){
vector<int> t; pairs.push_back(t);
while(vals.size()&&vals.back()<=arr[i]){
vals.pop_back();
pos.pop_back();
}
if(vals.size())
pairs[pos.back()].push_back(i);
vals.push_back(arr[i]);
pos.push_back(i);
}
vals.clear(); pos.clear();
for(int i=n-1; i>-1; i--){
while(vals.size()&&vals.back()<=arr[i]){
vals.pop_back();
pos.pop_back();
}
if(vals.size())
pairs[i].push_back(pos.back());
vals.push_back(arr[i]);
pos.push_back(i);
}
int q; cin>>q;
vector<vector<int>> queries;
for(int i=0; i<n; i++){
vector<int>v;
queries.push_back(v);
}
int answers[q];
for(int i=0; i<q; i++){
int l, r; cin>>l>>r;l--;r--;
queries[l].push_back(r);
queries[l].push_back(i);
}
for(int i=0; i<4*maxn; i++){
lz[i] = 0;
seg[i] = 0;
ma[i]=0;
}
setUp(1, 0, n-1);
for(int i=n-1; i>-1; i--){
for(int p: pairs[i]){
if(p+p-i<n){
update(1, 0, n-1, p+p-i, n-1, arr[i]+arr[p]);
}
}
for(int j=0; j<queries[i].size(); j+=2){
answers[queries[i][j+1]] = query(1, 0, n-1, i, queries[i][j]);
}
}
for(int value: answers)cout<<value<<'\n';
return 0;
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int j=0; j<queries[i].size(); j+=2){
| ~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
23760 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
23760 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
140 ms |
40516 KB |
Output is correct |
| 2 |
Correct |
90 ms |
43704 KB |
Output is correct |
| 3 |
Correct |
100 ms |
43816 KB |
Output is correct |
| 4 |
Correct |
137 ms |
42352 KB |
Output is correct |
| 5 |
Incorrect |
139 ms |
42340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
23760 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
