Submission #779752

#	Time	Username	Problem	Language	Result	Execution time	Memory
779752		LucaIlie	Two Antennas (JOI19_antennas)	C++17	100 / 100	657 ms	54052 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

struct update {
    int type, p;
};

struct query {
    int q, l;
};

const int MAX_N = 2e5;
const int MAX_Q = 2e5;
const int INF = 1e9 + 1;
int h[MAX_N], a[MAX_N], b[MAX_N], ans[MAX_Q];
vector<update> updates[2 * MAX_N];
vector<query> queries[MAX_N];

struct segTree {
    struct info {
        int minL, maxL, minR, maxR, maxDelta;

        info operator + ( const info &x ) const {
            return { min( minL, x.minL ), max( maxL, x.maxL ), INF, -INF, max( maxDelta, x.maxDelta ) };
        }
    };

    info segTree[4 * MAX_N];

    void init() {
        for ( int v = 0; v < 4 * MAX_N; v++ )
            segTree[v] = { INF, -INF, INF, -INF, -1 };
    }

    void propag( int v, int l, int r ) {
        if ( segTree[v].minR == INF || segTree[v].minL == INF ) {
            segTree[v].minR = INF;
            segTree[v].maxR = -INF;
            return;
        }

        segTree[v].maxDelta = max( segTree[v].maxDelta, abs( segTree[v].maxR - segTree[v].minL ) );
        segTree[v].maxDelta = max( segTree[v].maxDelta, abs( segTree[v].minR - segTree[v].maxL ) );
        if ( l != r ) {
            segTree[v * 2 + 1].minR = min( segTree[v * 2 + 1].minR, segTree[v].minR );
            segTree[v * 2 + 1].maxR = max( segTree[v * 2 + 1].maxR, segTree[v].maxR );
            segTree[v * 2 + 2].minR = min( segTree[v * 2 + 2].minR, segTree[v].minR );
            segTree[v * 2 + 2].maxR = max( segTree[v * 2 + 2].maxR, segTree[v].maxR );
        }
        segTree[v].minR = INF;
        segTree[v].maxR = -INF;
    }

    void updatePos( int v, int l, int r, int p, int t ) {
        propag( v, l, r );

        if ( l > p || r < p )
            return;

        if ( l == r ) {
            if ( t == 1 )
                segTree[v].minL = segTree[v].maxL = h[p];
            else
                segTree[v].minL = INF, segTree[v].maxL = -INF;
            return;
        }

        int mid = (l + r) / 2;
        updatePos( v * 2 + 1, l, mid, p, t );
        updatePos( v * 2 + 2, mid + 1, r, p, t );
        segTree[v] = segTree[v * 2 + 1] + segTree[v * 2 + 2];
    }

    void updateInterval( int v, int l, int r, int lu, int ru, int val ) {
        propag( v, l, r );

        if ( l > ru || r < lu )
            return;

        if ( lu <= l && r <= ru ) {
            segTree[v].minR = segTree[v].maxR = val;
            propag( v, l, r );
            return;
        }

        int mid = (l + r) / 2;
        updateInterval( v * 2 + 1, l, mid, lu, ru, val );
        updateInterval( 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 ) {
        propag( v, l, r );

        if ( l > rq || r < lq )
            return { INF, -INF, INF, -INF, -1 };

        if ( lq <= l && r <= rq )
            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 antena3;

int main() {
    int n, q;

    cin >> n;
    for ( int i = 0; i < n; i++ ) {
        cin >> h[i] >> a[i] >> b[i];
        updates[i + a[i]].push_back( { 1, i } );
        updates[i + b[i] + 1].push_back( { -1, i } );
    }

    cin >> q;
    for ( int i = 0; i < q; i++ ) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        queries[r].push_back( { i, l } );
    }

    antena3.init();
    for ( int i = 0; i < n; i++ ) {
        for ( update u: updates[i] )
            antena3.updatePos( 0, 0, n - 1, u.p, u.type );
        antena3.updateInterval( 0, 0, n - 1, i - b[i], i - a[i], h[i] );
        for ( query q: queries[i] )
            ans[q.q] = antena3.query( 0, 0, n - 1, q.l, i ).maxDelta;
    }

    for ( int i = 0; i < q; i++ )
        cout << ans[i] << "\n";

    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65