#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( max( maxABC, x.maxABC ), maxAB + x.maxC );
return ans;
}
};
struct update {
int pos, val;
};
struct query {
int l, r, p;
};
const int MAX_N = 5e5;
const int MAX_Q = 5e5;
int val[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];
void init( int v, int l, int r ) {
if ( l == r ) {
segTree[v] = { -inf, val[l], -inf };
return;
}
int mid = (l + r) / 2;
init( v * 2 + 1, l, mid );
init( v * 2 + 2, mid + 1, r );
segTree[v].maxC = max( segTree[v * 2 + 1].maxC, segTree[v * 2 + 2].maxC );
}
void update( int v, int l, int r, int pos, int val ) {
if ( l > pos || r < pos )
return;
if ( l == r ) {
segTree[v].maxAB = max( segTree[v].maxAB, val );
segTree[v].maxABC = segTree[v].maxAB + segTree[v].maxC;
return;
}
int mid = (l + r) / 2;
update( v * 2 + 1, l, mid, pos, val );
update( v * 2 + 2, mid + 1, r, pos, val );
segTree[v] = segTree[v * 2 + 1] + segTree[v * 2 + 2];
//printf( "udpate %d %d %d %d %d\n", l, r, segTree[v].maxAB, segTree[v].maxC, segTree[v].maxABC );
}
info query( int v, int l, int r, int lq, int rq ) {
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 >> val[i];
stack <int> s;
for ( int i = 1; i <= n; i++ ) {
while ( !s.empty() && val[i] >= val[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[x.a].push_back( { 2 * x.b - x.a, val[x.a] + val[x.b] } );//, printf( "%d %d\n", x.a, x.b );
int q;
cin >> q;
for ( int i = 0; i < q; i++ ) {
int l, r;
cin >> l >> r;
queries[l].push_back( { l, r, i } );
}
maxJump.init( 0, 1, n );
for ( int i = n; i >= 1; i-- ) {
for ( update u: updates[i] )
maxJump.update( 0, 1, n, u.pos, u.val );//, printf( "u %d %d %d\n", i, u.pos, u.val );
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 |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23800 KB |
Output is correct |
3 |
Correct |
12 ms |
23744 KB |
Output is correct |
4 |
Correct |
12 ms |
23732 KB |
Output is correct |
5 |
Correct |
12 ms |
23764 KB |
Output is correct |
6 |
Correct |
12 ms |
23716 KB |
Output is correct |
7 |
Correct |
13 ms |
23800 KB |
Output is correct |
8 |
Correct |
12 ms |
23800 KB |
Output is correct |
9 |
Correct |
12 ms |
23840 KB |
Output is correct |
10 |
Correct |
12 ms |
23760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23800 KB |
Output is correct |
3 |
Correct |
12 ms |
23744 KB |
Output is correct |
4 |
Correct |
12 ms |
23732 KB |
Output is correct |
5 |
Correct |
12 ms |
23764 KB |
Output is correct |
6 |
Correct |
12 ms |
23716 KB |
Output is correct |
7 |
Correct |
13 ms |
23800 KB |
Output is correct |
8 |
Correct |
12 ms |
23800 KB |
Output is correct |
9 |
Correct |
12 ms |
23840 KB |
Output is correct |
10 |
Correct |
12 ms |
23760 KB |
Output is correct |
11 |
Correct |
423 ms |
46092 KB |
Output is correct |
12 |
Correct |
426 ms |
45836 KB |
Output is correct |
13 |
Correct |
462 ms |
45840 KB |
Output is correct |
14 |
Correct |
447 ms |
46004 KB |
Output is correct |
15 |
Correct |
418 ms |
46084 KB |
Output is correct |
16 |
Correct |
450 ms |
45408 KB |
Output is correct |
17 |
Correct |
515 ms |
45352 KB |
Output is correct |
18 |
Correct |
451 ms |
45196 KB |
Output is correct |
19 |
Correct |
460 ms |
45872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
208 ms |
43092 KB |
Output is correct |
2 |
Correct |
137 ms |
40244 KB |
Output is correct |
3 |
Correct |
175 ms |
41132 KB |
Output is correct |
4 |
Correct |
204 ms |
43060 KB |
Output is correct |
5 |
Correct |
201 ms |
43104 KB |
Output is correct |
6 |
Correct |
204 ms |
42448 KB |
Output is correct |
7 |
Correct |
184 ms |
42340 KB |
Output is correct |
8 |
Correct |
200 ms |
42344 KB |
Output is correct |
9 |
Correct |
202 ms |
42668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23800 KB |
Output is correct |
3 |
Correct |
12 ms |
23744 KB |
Output is correct |
4 |
Correct |
12 ms |
23732 KB |
Output is correct |
5 |
Correct |
12 ms |
23764 KB |
Output is correct |
6 |
Correct |
12 ms |
23716 KB |
Output is correct |
7 |
Correct |
13 ms |
23800 KB |
Output is correct |
8 |
Correct |
12 ms |
23800 KB |
Output is correct |
9 |
Correct |
12 ms |
23840 KB |
Output is correct |
10 |
Correct |
12 ms |
23760 KB |
Output is correct |
11 |
Correct |
423 ms |
46092 KB |
Output is correct |
12 |
Correct |
426 ms |
45836 KB |
Output is correct |
13 |
Correct |
462 ms |
45840 KB |
Output is correct |
14 |
Correct |
447 ms |
46004 KB |
Output is correct |
15 |
Correct |
418 ms |
46084 KB |
Output is correct |
16 |
Correct |
450 ms |
45408 KB |
Output is correct |
17 |
Correct |
515 ms |
45352 KB |
Output is correct |
18 |
Correct |
451 ms |
45196 KB |
Output is correct |
19 |
Correct |
460 ms |
45872 KB |
Output is correct |
20 |
Correct |
208 ms |
43092 KB |
Output is correct |
21 |
Correct |
137 ms |
40244 KB |
Output is correct |
22 |
Correct |
175 ms |
41132 KB |
Output is correct |
23 |
Correct |
204 ms |
43060 KB |
Output is correct |
24 |
Correct |
201 ms |
43104 KB |
Output is correct |
25 |
Correct |
204 ms |
42448 KB |
Output is correct |
26 |
Correct |
184 ms |
42340 KB |
Output is correct |
27 |
Correct |
200 ms |
42344 KB |
Output is correct |
28 |
Correct |
202 ms |
42668 KB |
Output is correct |
29 |
Correct |
1407 ms |
93392 KB |
Output is correct |
30 |
Correct |
1100 ms |
86288 KB |
Output is correct |
31 |
Correct |
1176 ms |
88340 KB |
Output is correct |
32 |
Correct |
1322 ms |
93372 KB |
Output is correct |
33 |
Correct |
1357 ms |
93468 KB |
Output is correct |
34 |
Correct |
1281 ms |
91028 KB |
Output is correct |
35 |
Correct |
1317 ms |
90732 KB |
Output is correct |
36 |
Correct |
1281 ms |
90800 KB |
Output is correct |
37 |
Correct |
1266 ms |
92204 KB |
Output is correct |
38 |
Correct |
1144 ms |
98156 KB |
Output is correct |
39 |
Correct |
1101 ms |
98152 KB |
Output is correct |
40 |
Correct |
999 ms |
94768 KB |
Output is correct |
41 |
Correct |
958 ms |
94256 KB |
Output is correct |
42 |
Correct |
973 ms |
94288 KB |
Output is correct |
43 |
Correct |
1039 ms |
95972 KB |
Output is correct |
44 |
Correct |
1089 ms |
97496 KB |
Output is correct |
45 |
Correct |
1120 ms |
97472 KB |
Output is correct |
46 |
Correct |
1060 ms |
94332 KB |
Output is correct |
47 |
Correct |
1035 ms |
93976 KB |
Output is correct |
48 |
Correct |
1093 ms |
93968 KB |
Output is correct |
49 |
Correct |
1037 ms |
96020 KB |
Output is correct |
50 |
Correct |
1145 ms |
95820 KB |
Output is correct |
51 |
Correct |
1133 ms |
95732 KB |
Output is correct |
52 |
Correct |
1138 ms |
93252 KB |
Output is correct |
53 |
Correct |
1072 ms |
93116 KB |
Output is correct |
54 |
Correct |
1070 ms |
93008 KB |
Output is correct |
55 |
Correct |
1109 ms |
94660 KB |
Output is correct |