oj.uz

답안 #732089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
732089 2023-04-28T11:27:04 Z LucaIlie 3단 점프 (JOI19_jumps) C++17
0 / 100
 458 ms 59952 KB 
#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;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 458 ms 59952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# 결과 실행 시간 메모리 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 -