Submission #732123

#	Time	Username	Problem	Language	Result	Execution time	Memory
732123		LucaIlie	Triple Jump (JOI19_jumps)	C++17	100 / 100	1407 ms	98156 KiB

jumps

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

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