//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define full(x,n) x,x+n+1
#define full(x) x.begin(),x.end()
#define finish return 0
#define putb push_back
#define f first
#define s second
//logx(a^n)=loga(a^n)/logx(a)
//logx(a*b)=logx(a)+logx(b)
//logx(y)=log(y)/log(x)
//logb(n)=loga(n)/loga(b)
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define putf push_front
#define gainb pop_back
//(a+b)^n=sum of C(n,i)*a^i*b^(n-i) 0<=i<=n
//(a-b)^n=sum of C(n,i)*a^i*b^(n-i) for even i-for odd i
#define gainf pop_front
#define len(x) (int)x.size()
// 1/b%mod=b^(m-2)%mod
// (a>>x)&1==0
// a^b=(a+b)-2(a&b)
typedef double db;
typedef long long ll;
//sum of squares n*(n+1)*(2n+1)/6
//sum of cubes [n*(n+1)/2]^2
//sum of squares for odds n*(4*n*n-1)/3
//sum of cubes for odds n*n*(2*n*n-1)
const int ary=5e5+5;
const int mod=1e9+7;
const ll inf=1e18;
using namespace std;
using namespace __gnu_pbds;
int n,a[ary],q,t[4*ary];
ll ans;
void build(int v=1,int tl=1,int tr=n){
if(tl==tr){
t[v]=a[tl];
return;
}
int tm=(tl+tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
t[v]=max(t[v*2],t[v*2+1]);
}
pair<int,int> getL(int l,int r,int v=1,int tl=1,int tr=n){
if(r<tl||tr<l){
return {0,0};
}
int tm=(tl+tr)/2;
if(l<=tl&&tr<=r){
if(tl==tr){
return {tl,a[tl]};
}
if(t[v*2]>=t[v*2+1]){
return getL(l,r,v*2,tl,tm);
}
return getL(l,r,v*2+1,tm+1,tr);
}
pair<int,int> x=getL(l,r,v*2,tl,tm);
pair<int,int> y=getL(l,r,v*2+1,tm+1,tr);
if(x.s>=y.s){
return x;
}
return y;
}
pair<int,int> getR(int l,int r,int v=1,int tl=1,int tr=n){
if(r<tl||tr<l){
return {0,0};
}
int tm=(tl+tr)/2;
if(l<=tl&&tr<=r){
if(tl==tr){
return {tl,a[tl]};
}
if(t[v*2]<=t[v*2+1]){
return getR(l,r,v*2+1,tm+1,tr);
}
return getR(l,r,v*2,tl,tm);
}
pair<int,int> x=getR(l,r,v*2,tl,tm);
pair<int,int> y=getR(l,r,v*2+1,tm+1,tr);
if(x.s<=y.s){
return y;
}
return x;
}
void sana(int l,int r,pair<int,ll> ip,pair<int,ll> id){
if(ip.f>l){
ans=max(ans,id.s+ip.s+getL(max(l,ip.f-id.f+ip.f),ip.f-1).s);
}
if(ip.f+1<id.f){
ans=max(ans,id.s+ip.s+getL(ip.f+1,ip.f+(id.f-ip.f)/2).s);
}
if(id.f+id.f-ip.f<=r){
ans=max(ans,id.s+ip.s+getL(id.f+id.f-ip.f,r).s);
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build();
cin>>q;
while(q--){
ans=0;
int l,r;
cin>>l>>r;
pair<int,ll> id=getL(l,r),ip;
if(id.f>l){
ip=getL(l,id.f-1);
sana(l,r,ip,id);
ip=getR(l,id.f-1);
sana(l,r,ip,id);
}
if(id.f<r){
ip=getL(id.f+1,r);
sana(l,r,id,ip);
ip=getR(id.f+1,r);
sana(l,r,id,ip);
}
id=getR(l,r);
if(id.f>l){
ip=getL(l,id.f-1);
sana(l,r,ip,id);
ip=getR(l,id.f-1);
sana(l,r,ip,id);
}
if(id.f<r){
ip=getL(id.f+1,r);
sana(l,r,id,ip);
ip=getR(id.f+1,r);
sana(l,r,id,ip);
}
cout<<ans<<"\n";
}
}
Compilation message
jumps.cpp:7: warning: "full" redefined
7 | #define full(x) x.begin(),x.end()
|
jumps.cpp:6: note: this is the location of the previous definition
6 | #define full(x,n) x,x+n+1
|
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
25 ms |
3180 KB |
Output is correct |
| 2 |
Correct |
24 ms |
3180 KB |
Output is correct |
| 3 |
Correct |
24 ms |
3180 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
3200 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
