Submission #37146

#	Time	Username	Problem	Language	Result	Execution time	Memory
37146		chonka	Money (IZhO17_money)	C++98	100 / 100	916 ms	33272 KiB

money

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

#define MAXN 1000007

int n ;
int a[ MAXN ] ;

int nxt[ MAXN ] ;
int prv[ MAXN ] ;

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 pos , int val ) {
        if ( IR < pos || pos < IL ) { return ; }
        if ( IL == IR ) { tr[ where ] += val ; return ; }
        int mid = ( IL + IR ) / 2 ;
        if ( pos <= mid ) {
            update ( 2 * where , IL , mid , pos , val ) ;
        }
        else {
            update ( 2 * where + 1 , mid + 1 , IR , pos , val ) ;
        }
        tr[ where ] = tr[ 2 * where ] + tr[ 2 * where + 1 ] ;
    }
    int query ( int where , int IL , int IR , int CURL , int CURR ) {
        if ( CURL > CURR ) { return 0 ; }
        if ( IR < CURL || CURR < IL ) { return 0 ; }
        if ( CURL <= IL && IR <= CURR ) { return tr[ where ] ; }
        int mid = ( IL + IR ) / 2 ;
        return ( query ( 2 * where , IL , mid , CURL , CURR ) + query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ;
    }
};

Tree w ;

void input ( ) {
    scanf ( "%d" , &n ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d" , &a[ i ] ) ;
    }
}

void solve ( ) {
    int lim = 1000000 ;
    w.init ( 1 , 1 , lim ) ;
    int i ;
    int ans = 0 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        int j ;
        int mn , mx ;
        mx = mn = a[ i ] ;
        for ( j = i ; j <= n ; j ++ ) {
            if ( i != j && a[ j ] < a[ j - 1 ] ) { break ; }
            if ( mn > a[ j ] ) { mn = a[ j ] ; }
            if ( mx < a[ j ] ) { mx = a[ j ] ; }
            if ( w.query ( 1 , 1 , lim , mn + 1 , mx - 1 ) != 0 ) { break ; }
        }
        ans ++ ;
        for ( int t = i ; t < j ; t ++ ) {
            w.update ( 1 , 1 , lim , a[ t ] , 1 ) ;
        }
        i = j - 1 ;
    }
    printf ( "%d\n" , ans ) ;
}

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

Compilation message (stderr)

money.cpp: In function 'void input()':
money.cpp:47:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d" , &n ) ;
                         ^
money.cpp:50:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &a[ i ] ) ;
                                  ^

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55