Submission #38670

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38670	2018-01-05T19:21:24 Z	chonka	Trading (IZhO13_trading)	C++	100 / 100	316 ms	9352 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	9352 KB	Output is correct
2	Correct	0 ms	9352 KB	Output is correct
3	Correct	0 ms	9352 KB	Output is correct
4	Correct	0 ms	9352 KB	Output is correct
5	Correct	0 ms	9352 KB	Output is correct
6	Correct	0 ms	9352 KB	Output is correct
7	Correct	159 ms	9352 KB	Output is correct
8	Correct	176 ms	9352 KB	Output is correct
9	Correct	179 ms	9352 KB	Output is correct
10	Correct	189 ms	9352 KB	Output is correct
11	Correct	226 ms	9352 KB	Output is correct
12	Correct	256 ms	9352 KB	Output is correct
13	Correct	243 ms	9352 KB	Output is correct
14	Correct	263 ms	9352 KB	Output is correct
15	Correct	283 ms	9352 KB	Output is correct
16	Correct	253 ms	9352 KB	Output is correct
17	Correct	259 ms	9352 KB	Output is correct
18	Correct	299 ms	9352 KB	Output is correct
19	Correct	289 ms	9352 KB	Output is correct
20	Correct	316 ms	9352 KB	Output is correct