Submission #37164

#	Time	Username	Problem	Language	Result	Execution time	Memory
37164		chonka	Simple game (IZhO17_game)	C++98	100 / 100	326 ms	25460 KiB

game

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

#define MAXN 1000007

int n , q ;
int a[ MAXN ] ;

int lim = 1000000 ;

class Tree {
    public :
    int tr[ 5 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        tr[ where ] = 0 ;
        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 ( IR < CURL || CURR < IL ) { return ; }
        if ( CURL <= IL && IR <= CURR ) {
            tr[ where ] += val ;
            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 ( IR < pos || pos < IL ) { return 0 ; }
        if ( IL == IR ) { return tr[ where ] ; }
        int mid = ( IL + IR ) / 2 ;
        int ret = 0 ;
        if ( pos <= mid ) { ret = query ( 2 * where , IL , mid , pos ) ; }
        else { ret = query ( 2 * where + 1 , mid + 1 , IR , pos ) ; }
        ret += tr[ where ] ;
        return ret ;
    }
};
Tree w ;

void input ( ) {
    scanf ( "%d%d" , &n , &q ) ;
    int i ;
    w.init ( 1 , 1 , lim ) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d" , &a[ i ] ) ;
        if ( i != 1 ) {
            w.update ( 1 , 1 , lim , min ( a[ i - 1 ] , a[ i ] ) , max ( a[ i - 1 ] , a[ i ] ) , 1 ) ;
        }
    }
}

void solve ( ) {
    int i ;
    int type , x , y ;
    for ( i = 1  ; i <= q ; i ++ ) {
        scanf ( "%d" , &type ) ;
        if ( type == 1 ) {
            scanf ( "%d%d" , &x , &y ) ;
            if ( x != 1 ) {
                w.update ( 1 , 1 , lim , min ( a[ x ] , a[ x - 1 ] ) , max ( a[ x ] , a[ x - 1 ] ) , -1 ) ;
                w.update ( 1 , 1 , lim , min ( y , a[ x - 1 ] ) , max ( y , a[ x - 1 ] ) , 1 ) ;
            }
            if ( x != n ) {
                w.update ( 1 , 1 , lim , min ( a[ x ] , a[ x + 1 ] ) , max ( a[ x ] , a[ x + 1 ] ) , -1 ) ;
                w.update ( 1 , 1 , lim , min ( y , a[ x + 1 ] ) , max ( y , a[ x + 1 ] ) , 1 ) ;
            }
            a[ x ] = y ;
        }
        else {
            scanf ( "%d" , &x ) ;
            printf ( "%d\n" , w.query ( 1 , 1 , lim , x ) ) ;
        }
    }
}

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

Compilation message (stderr)

game.cpp: In function 'void input()':
game.cpp:46:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d" , &n , &q ) ;
                                ^
game.cpp:50:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &a[ i ] ) ;
                                  ^
game.cpp: In function 'void solve()':
game.cpp:61:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &type ) ;
                                ^
game.cpp:63:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ( "%d%d" , &x , &y ) ;
                                        ^
game.cpp:75:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ( "%d" , &x ) ;
                                 ^

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51