#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define task "hopscotch"
#define ppl pair<ll, pll>
using namespace std;
using ll = long long;
const int N = 5e5+55;
const ll mod = 1e15;
const ll base = 350;
const ll inf = 1e12;
ll m, n, t, k, a[N], ans, tong, b[N], c[N], d[N], l[N], r[N], res[N];
vector<pll> adj[N];
vector<ll> kq;
struct BIT
{
vector<ll> fe;
ll n;
BIT(ll _n)
{
n = _n;
fe.resize(n+1, 0);
}
void clear()
{
fill(fe.begin(), fe.end(), 0);
}
void add(ll id, ll x)
{
for(; id <= n; id += id & -id)fe[id] += x;
}
void add(ll l, ll r, ll x)
{
if(l > r)return;
add(l, x);
add(r+1, -x);
}
ll get(ll id)
{
ll total = 0;
for(; id; id -= id & -id)total += fe[id];
return total;
}
};
struct IT
{
vector<ll> st, lazy, vi;
IT(ll _N)
{
n = _N;
st.resize(n*4+4, 0);
lazy.resize(n*4+4, 0);
vi.resize(n*4+4, 0);
}
void build(ll id, ll l, ll r)
{
if(l == r)
{
vi[id] = a[l];
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id] = vi[id] = max(vi[id*2], vi[id*2+1]);
}
void build()
{
build(1, 1, n);
}
void down(ll id)
{
if(!lazy[id])return;
st[id*2] = max(st[id*2], vi[id*2] + lazy[id]);
st[id*2+1] = max(st[id*2+1], vi[id*2+1] + lazy[id]);
lazy[id*2] = max(lazy[id*2], lazy[id]);
lazy[id*2+1] = max(lazy[id*2], lazy[id]);
lazy[id] = 0;
}
void update(ll id, ll l, ll r, ll u, ll v, ll x)
{
if(u <= l && r <= v)
{
st[id] = max(st[id], x+vi[id]);
lazy[id] = max(lazy[id], x);
return;
}
if(u > r || l > v)return;
down(id);
ll mid = (l+r)/2;
update(id*2, l, mid, u, v, x);
update(id*2+1, mid+1, r, u, v, x);
st[id] = max(st[id*2], st[id*2+1]);
}
void update(ll l, ll r, ll x)
{
if(l > r)return;
update(1, 1, n, l, r, x);
}
ll get(ll id, ll l, ll r, ll u, ll v)
{
if(u <= l && r <= v)return st[id];
if( u > r || l > v)return -inf;
down(id);
ll mid = (l+r)/2;
return max(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
}
ll get(ll l, ll r)
{
return get(1, 1, n, l, r);
}
};
vector<pll> v;
struct query
{
ll l, r, id;
bool operator < (const query& q)
{
return (l > q.l);
}
}q[N];
void sol()
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
while(!kq.empty() && a[kq.back()] < a[i])kq.pop_back();
if(!kq.empty())v.pb({kq.back(), i});
kq.pb(i);
}
kq.clear();
for(int i = n; i > 0; i --)
{
while(!kq.empty() && a[kq.back()] < a[i])kq.pop_back();
if(!kq.empty())v.pb({i, kq.back()});
kq.pb(i);
}
cin >> m;
for(int i = 1; i <= m; i ++)
{
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q+1, q+1+m);
sort(v.rbegin(), v.rend());
IT it(n);
it.build();
for(int i = 1, j = 0; i <= m; i ++)
{
while(j < v.size() && v[j].fi >= q[i].l)
{
it.update(v[j].se*2-v[j].fi, n, a[v[j].se]+a[v[j].fi]);
++j;
}
b[q[i].id] = it.get(q[i].l, q[i].r);
}
for(int i = 1; i <= m; i ++)cout << b[i] <<'\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(task".in", "r"))
{
freopen(task".in", "r", stdin);
freopen(task".out", "w", stdout);
}
int ntest = 1;
//cin >> ntest;
while(ntest -- > 0)
sol();
}
/*
5 4
1 2 1
2 3 4
1 4 3
4 3 2
3
1 3 1
1 3 2
1 3 3
*/
Compilation message
jumps.cpp: In function 'void sol()':
jumps.cpp:153:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | while(j < v.size() && v[j].fi >= q[i].l)
| ~~^~~~~~~~~~
jumps.cpp: In function 'int main()':
jumps.cpp:169:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
169 | freopen(task".in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:170:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
170 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11980 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
12108 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11980 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
12108 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
40584 KB |
Output is correct |
| 2 |
Correct |
103 ms |
40932 KB |
Output is correct |
| 3 |
Correct |
92 ms |
38992 KB |
Output is correct |
| 4 |
Correct |
185 ms |
40576 KB |
Output is correct |
| 5 |
Correct |
182 ms |
40488 KB |
Output is correct |
| 6 |
Correct |
177 ms |
39968 KB |
Output is correct |
| 7 |
Correct |
180 ms |
39860 KB |
Output is correct |
| 8 |
Correct |
172 ms |
39820 KB |
Output is correct |
| 9 |
Correct |
183 ms |
40152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11980 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
12108 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
