Submission #38669

# Submission time Handle Problem Language Result Execution time Memory
38669 2018-01-05T19:20:56 Z chonka Trading (IZhO13_trading) C++
0 / 100
309 ms 6420 KB
#include<iostream>
#include<stdio.h>
using namespace std ;

#define MAXN 300007
#define inf 1000000007

int n , q ;

class Tree {
    public :
    int tr[ 3 * MAXN ] ;
    bool fl[ 3 * 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 ) ;
                                           ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 6420 KB Output is correct
2 Correct 0 ms 6420 KB Output is correct
3 Correct 0 ms 6420 KB Output is correct
4 Correct 0 ms 6420 KB Output is correct
5 Correct 0 ms 6420 KB Output is correct
6 Correct 3 ms 6420 KB Output is correct
7 Correct 166 ms 6420 KB Output is correct
8 Correct 179 ms 6420 KB Output is correct
9 Correct 199 ms 6420 KB Output is correct
10 Correct 176 ms 6420 KB Output is correct
11 Correct 223 ms 6420 KB Output is correct
12 Correct 249 ms 6420 KB Output is correct
13 Correct 239 ms 6420 KB Output is correct
14 Correct 229 ms 6420 KB Output is correct
15 Correct 309 ms 6420 KB Output is correct
16 Correct 276 ms 6420 KB Output is correct
17 Runtime error 0 ms 6420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -