#include <bits/stdc++.h>
using namespace std ;
const int MAX = 5e5 + 10 ;
int arr[MAX] ;
int n ;
pair<int , int> tree[4 * MAX] ;
void update(int node , int l , int r , int idx , int val)
{
if(idx > r || idx < l)
return ;
if(l == r)
{
tree[node] = {val , idx} ;
return ;
}
int mid = (l + r) >> 1 ;
update(node << 1 , l , mid , idx , val) ;
update(node << 1 | 1 , mid+1 , r , idx , val) ;
tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
}
pair<int , int>query(int node , int l , int r , int from , int to)
{
if(from > r || to < l)
return {-1 , -1} ;
if(l >= from && r <= to)
return tree[node] ;
int mid = (l + r) >> 1 ;
pair<int , int>a = query(node << 1 , l , mid , from , to) ;
pair<int , int>b = query(node << 1 | 1 , mid+1 , r , from , to) ;
return max(a , b) ;
}
vector<int>v ;
int calc(int l , int r)
{
v.clear() ;
for(int i = 0 ; i < min(20 , r-l+1) ; ++i)
{
int idx = query(1 , 1 , n , l , r).second ;
v.push_back(idx) ;
update(1 , 1 , n , idx , -1) ;
}
for(auto &i : v)
update(1 , 1 , n , i , arr[i]) ;
sort(v.begin() , v.end()) ;
int ans = 0 ;
for(int i = 0 ; i < v.size() ; ++i)
{
for(int j = i+1 ; j < v.size() ; ++j)
{
int diff = v[j] - v[i] ;
if(v[i] != l)
ans = max(ans , arr[v[i]] + arr[v[j]] + query(1 , 1 , n , max(l , v[i] - diff) , v[i]-1).first) ;
if(v[j] + diff <= r)
ans = max(ans , arr[v[i]] + arr[v[j]] + query(1 , 1 , n , v[j] + diff , r).first) ;
if(v[j] - v[i] > 1)
ans = max(ans , arr[v[i]] + arr[v[j]] + query(1 , 1 , n , v[i]+1 , v[i] + (diff / 2)).first) ;
}
}
return ans ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n ;
for(int i = 1 ; i <= n ; ++i)
cin>>arr[i] ;
for(int i = 1 ; i <= n ; ++i)
update(1 , 1 , n , i , arr[i]) ;
int q ;
cin>>q ;
while(q--)
{
int l , r ;
cin>>l>>r ;
cout<<calc(l , r)<<"\n" ;
}
return 0 ;
}
Compilation message
jumps.cpp: In function 'int calc(int, int)':
jumps.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i = 0 ; i < v.size() ; ++i)
| ~~^~~~~~~~~~
jumps.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int j = i+1 ; j < v.size() ; ++j)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
6 ms |
232 KB |
Output is correct |
| 3 |
Correct |
5 ms |
204 KB |
Output is correct |
| 4 |
Correct |
5 ms |
204 KB |
Output is correct |
| 5 |
Correct |
5 ms |
332 KB |
Output is correct |
| 6 |
Correct |
5 ms |
204 KB |
Output is correct |
| 7 |
Incorrect |
5 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
6 ms |
232 KB |
Output is correct |
| 3 |
Correct |
5 ms |
204 KB |
Output is correct |
| 4 |
Correct |
5 ms |
204 KB |
Output is correct |
| 5 |
Correct |
5 ms |
332 KB |
Output is correct |
| 6 |
Correct |
5 ms |
204 KB |
Output is correct |
| 7 |
Incorrect |
5 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
5196 KB |
Output is correct |
| 2 |
Correct |
75 ms |
5188 KB |
Output is correct |
| 3 |
Correct |
74 ms |
5140 KB |
Output is correct |
| 4 |
Correct |
83 ms |
5220 KB |
Output is correct |
| 5 |
Correct |
78 ms |
5156 KB |
Output is correct |
| 6 |
Incorrect |
73 ms |
5132 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
6 ms |
232 KB |
Output is correct |
| 3 |
Correct |
5 ms |
204 KB |
Output is correct |
| 4 |
Correct |
5 ms |
204 KB |
Output is correct |
| 5 |
Correct |
5 ms |
332 KB |
Output is correct |
| 6 |
Correct |
5 ms |
204 KB |
Output is correct |
| 7 |
Incorrect |
5 ms |
204 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
