#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<>,
rb_tree_tag, tree_order_statistics_node_update>
ordered_set;
#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>
#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif
const ll inf=1e15;
const ll maxn=5e5+5;
const ll mod=1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll arr[maxn];
stack<ll> s;
vector<ii> v;
struct node{
ll s,e,m,ab,c,abc;
node *l, *r;
node(ll _s, ll _e){
s=_s,e=_e,m=(s+e)>>1,ab=0,c=0,abc=0;
if (s!=e) l=new node(s,m),r=new node(m+1,e);
}
void upd(ll x, ll v, ll type){
if (s==e){
if (type==1){
ab=v;
} else c=v;
abc=ab+c;
return;
}
if (x>m) r->upd(x,v,type);
else l->upd(x,v,type);
ab=max(l->ab,r->ab),c=max(l->c,r->c);
abc=max({l->abc,r->abc,l->ab+r->c});
}
ll query(ll x, ll y){
iii t=process(x,y);
return get<2>(t);
}
iii process(ll x, ll y){
if (x<=s && e<=y) return {ab,c,abc};
if (x>m) return r->process(x,y);
if (y<=m) return l->process(x,y);
ll lab,lc,labc,rab,rc,rabc;
tie(lab,lc,labc)=l->process(x,y);
tie(rab,rc,rabc)=r->process(x,y);
iii t={max(lab,rab),max(lc,rc),max({labc,rabc,lab+rc})};
return t;
}
}*root;
ll ans[maxn];
vector<iii> q;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n;
cin>>n;
root=new node(1,n);
for (int i=1;i<=n;i++){
cin>>arr[i];
root->upd(i,arr[i],2);
}
for (int i=1;i<=n;i++){
while (s.size() && arr[s.top()]<=arr[i]){
if (2*i-s.top()<=n) //check that it is in range
v.emplace_back(s.top(),i);
s.pop();
}
if (s.size()){
if (2*i-s.top()<=n)
v.emplace_back(s.top(),i);
}
s.emplace(i);
}
sort(v.rbegin(),v.rend());
ll qu,l,r;
cin>>qu;
for (int i=1;i<=qu;i++){
cin>>l>>r;
q.emplace_back(l,r,i);
}
sort(q.rbegin(),q.rend());
ll ptr=0;
for (auto [l,r,idx]:q){
//cerr<<l<<' '<<r<<endl;
while (ptr!=v.size() && l<=v[ptr].first){
ll a,b;
tie(a,b)=v[ptr];
//cerr<<a<<' '<<b<<endl;
root->upd(2*b-a,arr[a]+arr[b],1);
ptr++;
}
ans[idx]=root->query(l,r);
}
for (int i=1;i<=qu;i++) cout<<ans[i]<<endl;
return 0;
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:99:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | while (ptr!=v.size() && l<=v[ptr].first){
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
45476 KB |
Output is correct |
| 2 |
Correct |
91 ms |
41156 KB |
Output is correct |
| 3 |
Correct |
89 ms |
43200 KB |
Output is correct |
| 4 |
Correct |
146 ms |
47488 KB |
Output is correct |
| 5 |
Correct |
131 ms |
47256 KB |
Output is correct |
| 6 |
Correct |
127 ms |
46784 KB |
Output is correct |
| 7 |
Correct |
130 ms |
46784 KB |
Output is correct |
| 8 |
Correct |
129 ms |
44992 KB |
Output is correct |
| 9 |
Correct |
128 ms |
46268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
