oj.uz

Submission #37164

# Submission time Handle Problem Language Result Execution time Memory
37164 2017-12-21T17:42:55 Z chonka Simple game (IZhO17_game) C++
100 / 100
 326 ms 25460 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25460 KB Output is correct
2 Correct 6 ms 25460 KB Output is correct
3 Correct 9 ms 25460 KB Output is correct
4 Correct 6 ms 25460 KB Output is correct
5 Correct 9 ms 25460 KB Output is correct
6 Correct 9 ms 25460 KB Output is correct
7 Correct 6 ms 25460 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25460 KB Output is correct
2 Correct 6 ms 25460 KB Output is correct
3 Correct 9 ms 25460 KB Output is correct
4 Correct 6 ms 25460 KB Output is correct
5 Correct 9 ms 25460 KB Output is correct
6 Correct 9 ms 25460 KB Output is correct
7 Correct 6 ms 25460 KB Output is correct
8 Correct 76 ms 25460 KB Output is correct
9 Correct 176 ms 25460 KB Output is correct
10 Correct 153 ms 25460 KB Output is correct
11 Correct 66 ms 25460 KB Output is correct
12 Correct 113 ms 25460 KB Output is correct
13 Correct 96 ms 25460 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25460 KB Output is correct
2 Correct 6 ms 25460 KB Output is correct
3 Correct 9 ms 25460 KB Output is correct
4 Correct 6 ms 25460 KB Output is correct
5 Correct 9 ms 25460 KB Output is correct
6 Correct 9 ms 25460 KB Output is correct
7 Correct 6 ms 25460 KB Output is correct
8 Correct 76 ms 25460 KB Output is correct
9 Correct 176 ms 25460 KB Output is correct
10 Correct 153 ms 25460 KB Output is correct
11 Correct 66 ms 25460 KB Output is correct
12 Correct 113 ms 25460 KB Output is correct
13 Correct 96 ms 25460 KB Output is correct
14 Correct 289 ms 25460 KB Output is correct
15 Correct 319 ms 25460 KB Output is correct
16 Correct 326 ms 25460 KB Output is correct
17 Correct 299 ms 25460 KB Output is correct
18 Correct 306 ms 25460 KB Output is correct