#include <bits/stdc++.h>
using namespace std;
struct ab {
int a, b;
};
const int inf = 4e8;
struct info {
int maxAB, maxC, maxABC;
info operator * ( const info &x ) const {
info ans;
ans.maxAB = max( maxAB, x.maxAB );
ans.maxC = max( maxC, x.maxC );
ans.maxABC = max( maxABC, x.maxABC );
return ans;
}
info operator + ( const info &x ) const {
if ( x.maxC == -inf ) {
if ( x.maxAB > maxAB )
return { x.maxAB, -inf, max( maxABC, x.maxABC ) };
return *this;
}
info ans;
ans.maxAB = max( maxAB, x.maxAB );
ans.maxC = max( maxC, x.maxC );
ans.maxABC = max( max( maxABC, x.maxABC ), maxAB + x.maxC );
return ans;
}
void operator += ( const info &x ) {
*this = *this + x;
}
};
struct update {
int l, r;
info val;
};
struct query {
int l, r, p;
};
const int MAX_N = 5e5;
const int MAX_Q = 5e5;
int v[MAX_N + 1], ans[MAX_Q];
vector<ab> pairs;
vector<update> updates[MAX_N + 1];
vector<query> queries[MAX_N + 1];
struct SegTree {
info segTree[4 * MAX_N], lazy[4 * MAX_N];
void init( int v, int l, int r ) {
lazy[v] = segTree[v] = { -inf, -inf, -inf };
if ( l == r )
return;
int mid = (l + r) / 2;
init( v * 2 + 1, l, mid );
init( v * 2 + 2, mid + 1, r );
}
void update( int v, int l, int r, int lu, int ru, info val ) {
segTree[v] += lazy[v];
if ( l != r ) {
lazy[v * 2 + 1] += lazy[v];
lazy[v * 2 + 2] += lazy[v];
}
if ( l > ru || r < lu )
return;
if ( lu <= l && r <= ru ) {
segTree[v] += val;
if ( l != r ) {
lazy[v * 2 + 1] += val;
lazy[v * 2 + 2] += val;
}
return;
}
int mid = (l + r) / 2;
update( v * 2 + 1, l, mid, lu, ru, val );
update( v * 2 + 2, mid + 1, r, lu, ru, val );
segTree[v] = segTree[v * 2 + 1] * segTree[v * 2 + 2];
}
info query( int v, int l, int r, int lq, int rq ) {
segTree[v] += lazy[v];
if ( l != r ) {
lazy[v * 2 + 1] += lazy[v];
lazy[v * 2 + 2] += lazy[v];
}
if ( l > rq || r < lq )
return { -inf, -inf, -inf };
if ( lq <= l && r <= rq ) {
//printf( "query %d %d %d %d %d\n", l, r, segTree[v].maxAB, segTree[v].maxC, segTree[v].maxABC );
return segTree[v];
}
int mid = (l + r) / 2;
return query( v * 2 + 1, l, mid, lq, rq ) * query( v * 2 + 2, mid + 1, r, lq, rq );
}
};
SegTree maxJump;
int main() {
int n;
cin >> n;
for ( int i = 1; i <= n; i++ )
cin >> v[i];
stack <int> s;
for ( int i = 1; i <= n; i++ ) {
while ( !s.empty() && v[i] >= v[s.top()] ) {
pairs.push_back( { s.top(), i } );
s.pop();
}
if ( !s.empty() )
pairs.push_back( { s.top(), i } );
s.push( i );
}
for ( ab x: pairs )
updates[2 * x.b - x.a].push_back( { 1, x.a, { v[x.a] + v[x.b], -inf, -inf } } );//, printf( "%d %d\n", x.a, x.b );
for ( int i = 1; i <= n; i++ )
updates[i].push_back( { 1, i, { -inf, v[i], -inf } } );
int q;
cin >> q;
for ( int i = 0; i < q; i++ ) {
int l, r;
cin >> l >> r;
queries[r].push_back( { l, n, i } );
}
maxJump.init( 0, 1, n );
for ( int i = 1; i <= n; i++ ) {
for ( update u: updates[i] )
maxJump.update( 0, 1, n, u.l, u.r, u.val );//, printf( "u %d %d %d %d %d\n", i, u.l, u.r, u.val.maxAB, u.val.maxC);
for ( query q: queries[i] )
ans[q.p] = maxJump.query( 0, 1, n, q.l, q.r ).maxABC;//, printf( "q %d %d %d %d\n", i, q.l, q.r, q.p );
}
for ( int i = 0; i < q; i++ )
cout << ans[i] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23804 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23804 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
458 ms |
59952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23804 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
