Submission #293609

#	Time	Username	Problem	Language	Result	Execution time	Memory
293609		muhammad_hokimiyon	Triple Jump (JOI19_jumps)	C++14	100 / 100	1452 ms	67944 KiB

jumps

#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";
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54