#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define dl double long
using namespace std;
const int N = 5e5 + 7;
const int M = 20 + 7;
const ll mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,q;
int a[N];
int ans[N];
int t[4 * N];
int lz[4 * N];
int tt[4 * N];
vector < pair < int , int > > v[N];
void mx( int &x , int y )
{
x = max( x , y );
}
void push( int x )
{
mx( t[x + x] , t[x] );
mx( t[x + x + 1] , t[x] );
mx( tt[x + x] , t[x + x] + lz[x + x] );
mx( tt[x + x + 1] , t[x + x + 1] + lz[x + x + 1] );
mx( tt[x] , tt[x + x] );
mx( tt[x] , tt[x + x + 1] );
}
void build( int x , int l , int r )
{
if( l == r ){
lz[x] = a[l];
return;
}
int m = (l + r) / 2;
build( x + x , l , m );
build( x + x + 1 , m + 1 , r );
mx( lz[x] , lz[x + x] );
mx( lz[x] , lz[x + x + 1] );
}
void upd( int x , int l , int r, int tl , int tr , int val )
{
if( tl > tr )return;
if( l == tl && r == tr ){
mx( t[x] , val );
mx( tt[x] , t[x] + lz[x] );
return;
}
push(x);
int m = (l + r) / 2;
upd( x + x , l , m , tl , min( tr , m ) , val );
upd( x + x + 1 , m + 1 , r , max( tl , m + 1 ) , tr , val );
mx( tt[x] , tt[x + x] );
mx( tt[x] , tt[x + x + 1] );
}
int get( int x , int l , int r , int tl , int tr )
{
if( tl > tr )return 0;
if( l == tl && r == tr ){
return tt[x];
}
int m = (l + r) / 2;
push(x);
return max( get( x + x , l , m , tl , min( tr , m ) ) ,
get( x + x + 1 , m + 1 , r , max( tl , m + 1 ) , tr ) );
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen( "input.txt" , "r" , stdin );
//freopen( "output.txt" , "w" , stdout );
cin >> n;
for( int i = 1; i <= n; i++ ){
cin >> a[i];
}
stack < int > st;
vector < pair < int , int > > pr;
for( int i = 1; i < n; i++ ){
while( !st.empty() && a[st.top()] <= a[i] ){
pr.push_back({ st.top() , i });
st.pop();
}
if( !st.empty() )pr.push_back({ st.top() , i });
st.push(i);
}
build( 1 , 1 , n );
sort( pr.rbegin() , pr.rend() );
cin >> q;
for( int i = 1; i <= q; i++ ){
int l,r;
cin >> l >> r;
v[l].push_back({r , i});
}
for( int i = n , j = 0; i >= 1; i-- ){
while( j < (int)pr.size() && pr[j].fi >= i ){
upd( 1 , 1 , n , pr[j].se + (pr[j].se - pr[j].fi) , n , a[pr[j].fi] + a[pr[j].se] );
j += 1;
}
for( auto x : v[i] ){
ans[x.se] = get( 1 , 1 , n , i , x.fi );
}
}
for( int i = 1; i <= q; i++ ){
cout << ans[i] << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12160 KB |
Output is correct |
2 |
Correct |
9 ms |
12160 KB |
Output is correct |
3 |
Correct |
9 ms |
12160 KB |
Output is correct |
4 |
Correct |
9 ms |
12160 KB |
Output is correct |
5 |
Correct |
9 ms |
12160 KB |
Output is correct |
6 |
Correct |
9 ms |
12160 KB |
Output is correct |
7 |
Correct |
9 ms |
12160 KB |
Output is correct |
8 |
Correct |
9 ms |
12160 KB |
Output is correct |
9 |
Correct |
9 ms |
12160 KB |
Output is correct |
10 |
Correct |
9 ms |
12160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12160 KB |
Output is correct |
2 |
Correct |
9 ms |
12160 KB |
Output is correct |
3 |
Correct |
9 ms |
12160 KB |
Output is correct |
4 |
Correct |
9 ms |
12160 KB |
Output is correct |
5 |
Correct |
9 ms |
12160 KB |
Output is correct |
6 |
Correct |
9 ms |
12160 KB |
Output is correct |
7 |
Correct |
9 ms |
12160 KB |
Output is correct |
8 |
Correct |
9 ms |
12160 KB |
Output is correct |
9 |
Correct |
9 ms |
12160 KB |
Output is correct |
10 |
Correct |
9 ms |
12160 KB |
Output is correct |
11 |
Correct |
383 ms |
30484 KB |
Output is correct |
12 |
Correct |
379 ms |
30328 KB |
Output is correct |
13 |
Correct |
389 ms |
30648 KB |
Output is correct |
14 |
Correct |
399 ms |
30436 KB |
Output is correct |
15 |
Correct |
399 ms |
30460 KB |
Output is correct |
16 |
Correct |
409 ms |
29820 KB |
Output is correct |
17 |
Correct |
407 ms |
29944 KB |
Output is correct |
18 |
Correct |
391 ms |
29816 KB |
Output is correct |
19 |
Correct |
455 ms |
30328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
235 ms |
24040 KB |
Output is correct |
2 |
Correct |
123 ms |
22504 KB |
Output is correct |
3 |
Correct |
123 ms |
23244 KB |
Output is correct |
4 |
Correct |
218 ms |
24048 KB |
Output is correct |
5 |
Correct |
217 ms |
24032 KB |
Output is correct |
6 |
Correct |
248 ms |
23472 KB |
Output is correct |
7 |
Correct |
238 ms |
23396 KB |
Output is correct |
8 |
Correct |
219 ms |
23264 KB |
Output is correct |
9 |
Correct |
240 ms |
23712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12160 KB |
Output is correct |
2 |
Correct |
9 ms |
12160 KB |
Output is correct |
3 |
Correct |
9 ms |
12160 KB |
Output is correct |
4 |
Correct |
9 ms |
12160 KB |
Output is correct |
5 |
Correct |
9 ms |
12160 KB |
Output is correct |
6 |
Correct |
9 ms |
12160 KB |
Output is correct |
7 |
Correct |
9 ms |
12160 KB |
Output is correct |
8 |
Correct |
9 ms |
12160 KB |
Output is correct |
9 |
Correct |
9 ms |
12160 KB |
Output is correct |
10 |
Correct |
9 ms |
12160 KB |
Output is correct |
11 |
Correct |
383 ms |
30484 KB |
Output is correct |
12 |
Correct |
379 ms |
30328 KB |
Output is correct |
13 |
Correct |
389 ms |
30648 KB |
Output is correct |
14 |
Correct |
399 ms |
30436 KB |
Output is correct |
15 |
Correct |
399 ms |
30460 KB |
Output is correct |
16 |
Correct |
409 ms |
29820 KB |
Output is correct |
17 |
Correct |
407 ms |
29944 KB |
Output is correct |
18 |
Correct |
391 ms |
29816 KB |
Output is correct |
19 |
Correct |
455 ms |
30328 KB |
Output is correct |
20 |
Correct |
235 ms |
24040 KB |
Output is correct |
21 |
Correct |
123 ms |
22504 KB |
Output is correct |
22 |
Correct |
123 ms |
23244 KB |
Output is correct |
23 |
Correct |
218 ms |
24048 KB |
Output is correct |
24 |
Correct |
217 ms |
24032 KB |
Output is correct |
25 |
Correct |
248 ms |
23472 KB |
Output is correct |
26 |
Correct |
238 ms |
23396 KB |
Output is correct |
27 |
Correct |
219 ms |
23264 KB |
Output is correct |
28 |
Correct |
240 ms |
23712 KB |
Output is correct |
29 |
Correct |
1422 ms |
62036 KB |
Output is correct |
30 |
Correct |
1206 ms |
58212 KB |
Output is correct |
31 |
Correct |
1222 ms |
60224 KB |
Output is correct |
32 |
Correct |
1452 ms |
62184 KB |
Output is correct |
33 |
Correct |
1422 ms |
62036 KB |
Output is correct |
34 |
Correct |
1400 ms |
59736 KB |
Output is correct |
35 |
Correct |
1384 ms |
59476 KB |
Output is correct |
36 |
Correct |
1387 ms |
59472 KB |
Output is correct |
37 |
Correct |
1388 ms |
60888 KB |
Output is correct |
38 |
Correct |
1006 ms |
67800 KB |
Output is correct |
39 |
Correct |
1012 ms |
67944 KB |
Output is correct |
40 |
Correct |
996 ms |
64596 KB |
Output is correct |
41 |
Correct |
989 ms |
64076 KB |
Output is correct |
42 |
Correct |
996 ms |
64060 KB |
Output is correct |
43 |
Correct |
1004 ms |
65748 KB |
Output is correct |
44 |
Correct |
1104 ms |
67284 KB |
Output is correct |
45 |
Correct |
1069 ms |
67316 KB |
Output is correct |
46 |
Correct |
1052 ms |
64088 KB |
Output is correct |
47 |
Correct |
1078 ms |
63672 KB |
Output is correct |
48 |
Correct |
1067 ms |
63700 KB |
Output is correct |
49 |
Correct |
1059 ms |
65832 KB |
Output is correct |
50 |
Correct |
1154 ms |
65620 KB |
Output is correct |
51 |
Correct |
1172 ms |
65296 KB |
Output is correct |
52 |
Correct |
1162 ms |
63060 KB |
Output is correct |
53 |
Correct |
1152 ms |
62676 KB |
Output is correct |
54 |
Correct |
1162 ms |
62420 KB |
Output is correct |
55 |
Correct |
1192 ms |
64360 KB |
Output is correct |