Submission #575560

#	Time	Username	Problem	Language	Result	Execution time	Memory
575560		chonka	Two Antennas (JOI19_antennas)	C++17	100 / 100	648 ms	39436 KiB

antennas

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int MAXN = 200007 ;
const int inf = 1000000007 ;

int n , m ;
int h[ MAXN ] , a[ MAXN ] , b[ MAXN ] ;

pair < int , int > qlist[ MAXN ] ;
int ans[ MAXN ] ;

vector < pair < int , int > > v[ MAXN ] ;
vector < int > to_solve[ MAXN ] ;

class Tree {
public :
    int tr[ 4 * MAXN ] , ret[ 4 * MAXN ] ;
    int lazy[ 4 * MAXN ] ;
    void push_lazy ( int where , int IL , int IR ) {
        ret[ where ] = max ( ret[ where ] , tr[ where ] + lazy[ where ] ) ;
        if ( IL != IR ) {
            lazy[ 2 * where ] = max ( lazy[ 2 * where ] , lazy[ where ] ) ;
            lazy[ 2 * where + 1 ] = max ( lazy[ 2 * where + 1 ] , lazy[ where ] ) ;
        }
        lazy[ where ] = -inf ;
    }
    void init ( int where , int IL , int IR ) {
        tr[ where ] = lazy[ where ] = ret[ where ] = -inf ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
    }
    void upd_pos ( int where , int IL , int IR , int pos , int nw ) {
        push_lazy ( where , IL , IR ) ;
        if ( IR < pos || pos < IL ) { return ; }
        if ( IL == IR ) {
            tr[ where ] = nw ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        upd_pos ( 2 * where , IL , mid , pos , nw ) ;
        upd_pos ( 2 * where + 1 , mid + 1 , IR , pos , nw ) ;
        tr[ where ] = max ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
        ret[ where ] = max ( ret[ 2 * where ] , ret[ 2 * where + 1 ] ) ;
    }
    void upd_range ( int where , int IL , int IR , int CURL , int CURR , int val ) {
        push_lazy ( where , IL , IR ) ;
        if ( IL > IR || CURL > CURR ) { return ; }
        if ( IR < CURL || CURR < IL ) { return ; }
        if ( CURL <= IL && IR <= CURR ) {
            lazy[ where ] = val ;
            push_lazy ( where , IL , IR ) ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        upd_range ( 2 * where , IL , mid , CURL , CURR , val ) ;
        upd_range ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , val ) ;
        tr[ where ] = max ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
        ret[ where ] = max ( ret[ 2 * where ] , ret[ 2 * where + 1 ] ) ;
    }
    int query ( int where , int IL , int IR , int CURL , int CURR ) {
        push_lazy ( where , IL , IR ) ;
        if ( IL > IR || CURL > IR ) { return -inf ; }
        if ( IR < CURL || CURR < IL ) { return -inf ; }
        if ( CURL <= IL && IR <= CURR ) { return ret[ where ] ; }
        int mid = ( IL + IR ) / 2 ;
        return max ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
    }
};
Tree w ;

void input ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> h[ i ] >> a[ i ] >> b[ i ] ;
    }
    cin >> m ;
    for ( int i = 1 ; i <= m ; ++ i ) {
        cin >> qlist[ i ].first >> qlist[ i ].second ;
        ans[ i ] = -inf ;
    }
}

void solve ( ) {
    for ( int iter = 0 ; iter < 2 ; ++ iter ) {
        w.init ( 1 , 1 , n ) ;
        for ( int i = 1 ; i <= n ; ++ i ) {
            int st = i + a[ i ] , en = i + b[ i ] + 1 ;
            if ( st <= n ) {
                v[ st ].push_back ( { i , 1 } ) ;
            }
            if ( en <= n ) {
                v[ en ].push_back ( { i , -1 } ) ;
            }
        }
        for ( int i = 1 ; i <= m ; ++ i ) {
            to_solve[ qlist[ i ].second ].push_back ( i ) ;
        }
        for ( int i = 1 ; i <= n ; ++ i ) {
            for ( auto e : v[ i ] ) {
                int id = e.first , type = e.second ;
                if ( type == 1 ) {
                    w.upd_pos ( 1 , 1 , n , id , -h[ id ] ) ;
                }
                else {
                    w.upd_pos ( 1 , 1 , n , id , -inf ) ;
                }
            }
            int st = i - b[ i ] ;
            int en = i - a[ i ] ;
            if ( st < 1 ) { st = 1 ; }
            if ( en < 0 ) { en = 0 ; }
            w.upd_range ( 1 , 1 , n , st , en , h[ i ] ) ;
            for ( auto id : to_solve[ i ] ) {
                ans[ id ] = max ( ans[ id ] , w.query ( 1 , 1 , n , qlist[ id ].first , i ) ) ;
            }
        }
        for ( int i = 1 ; i < n - i + 1 ; ++ i ) {
            swap ( h[ i ] , h[ n - i + 1 ] ) ;
            swap ( a[ i ] , a[ n - i + 1 ] ) ;
            swap ( b[ i ] , b[ n - i + 1 ] ) ;
        }
        for ( int i = 1 ; i <= m ; ++ i ) {
            int x = qlist[ i ].first , y = qlist[ i ].second ;
            qlist[ i ] = { n - y + 1 , n - x + 1 } ;
        }
        for ( int i = 1 ; i <= n ; ++ i ) {
            v[ i ].clear ( ) ;
            to_solve[ i ].clear ( ) ;
        }
    }
    for ( int i = 1 ; i <= m ; ++ i ) {
        if ( ans[ i ] < 0 ) { ans[ i ] = -1 ; }
        cout << ans[ i ] << "\n" ;
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ;
    /// cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

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