Submission #38670

#	Time	Username	Problem	Language	Result	Execution time	Memory
38670		chonka	Trading (IZhO13_trading)	C++98	100 / 100	316 ms	9352 KiB

trading

#include<iostream>
#include<stdio.h>
using namespace std ;

#define MAXN 300007
#define inf 1000000007

int n , q ;

class Tree {
    public :
    int tr[ 5 * MAXN ] ;
    bool fl[ 5 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        tr[ where ] = IL ;
        fl[ where ] = false ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
    }
    void update ( int where , int IL , int IR , int CURL , int CURR , int val ) {
        if ( CURL > CURR ) { return ; }
        if ( IR < CURL || CURR < IL ) { return ; }
        if ( CURL <= IL && IR <= CURR ) {
            tr[ where ] = min ( tr[ where ] , val ) ;
            fl[ where ] = true ;
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        update ( 2 * where , IL , mid , CURL , CURR , val ) ;
        update ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , val ) ;
    }
    int query ( int where , int IL , int IR , int pos ) {
        if ( pos < IL || IR < pos ) { return ( 2 * inf ) ; }
        if ( IL == IR ) {
            return ( pos - tr[ where ] ) ;
        }
        int ret = 0 ;
        if ( fl[ where ] == true ) {
            ret = max ( ret , pos - tr[ where ] ) ;
        }
        int mid = ( IL + IR ) / 2 ;
        if ( pos <= mid ) {
            ret = max ( ret , query ( 2 * where , IL , mid , pos ) ) ;
        }
        else {
            ret = max ( ret , query ( 2 * where + 1 , mid + 1 , IR , pos ) ) ;
        }
        return ret ;
    }
};
Tree w ;

void input ( ) {
    scanf ( "%d%d" , &n , &q ) ;
    w.init ( 1 , 1 , n ) ;
    int i ;
    for ( i = 1 ; i <= q ; i ++ ) {
        int l , r , x ;
        scanf ( "%d%d%d" , &l , &r , &x ) ;
        int pos = l - x ;
        w.update ( 1 , 1 , n , l , r , pos ) ;
    }
}

void solve ( ) {
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        int ret = w.query ( 1 , 1 , n , i ) ;
        printf ( "%d" , ret ) ;
        if ( i == n ) { printf ( "\n" ) ; }
        else { printf ( " " ) ; }
    }
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message (stderr)

trading.cpp: In function 'void input()':
trading.cpp:56:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d" , &n , &q ) ;
                                ^
trading.cpp:61:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d%d%d" , &l , &r , &x ) ;
                                           ^

• Subtask 1: 100 / 100