Submission #593961

#	Time	Username	Problem	Language	Result	Execution time	Memory
593961		hyakup	Simple game (IZhO17_game)	C++17	100 / 100	64 ms	6796 KiB

game

#include <bits/stdc++.h>
using namespace std;


const int maxn = 100010, maxh = 1000010; 
int height[maxn], bit[maxh];
int n, q; 


void update( int i, int v ){
    
    for( int j = i; j < maxh; j += j&-j) bit[j] += v;
    
}


int query( int i){
    
    int soma = 0;
    
    for( int j = i; j > 0; j -= j&-j) soma += bit[j];
    
    return soma;
}

int main(){
    
    scanf("%d %d", &n, &q);
    
    for( int i = 0; i < maxh; i++) bit[i] = 0;
    
    for( int i = 1; i <= n; i++) scanf("%d",  &height[i]);
    
    for( int i = 1; i < n; i++){
        
        update( min(height[i], height[i + 1]), 1 );
        update( max(height[i], height[i + 1]) + 1, -1 );
        
    }
    
    for( int i = 0; i < q; i++){
        
        int type; scanf("%d", &type);
        
        if( type == 1 ){
            
            int pos, val; scanf("%d %d", &pos, &val);
            
            if( pos < n ){
                
                update( min(height[pos], height[pos + 1]), -1 );
                update( max(height[pos], height[pos + 1]) + 1, 1 );
                
                update( min(val, height[pos + 1]), 1 );
                update( max(val, height[pos + 1]) + 1, -1 );
                
            }
            
            if( pos > 1 ){
                
                update( min(height[pos], height[pos - 1]), -1 );
                update( max(height[pos], height[pos - 1]) + 1, 1 );
                
                update( min(val, height[pos - 1]), 1 );
                update( max(val, height[pos - 1]) + 1, -1 );
        
            }
            
            height[pos] = val;
        }
        
        if( type == 2 ){
            int h; scanf("%d", &h);
            
            printf("%d\n", query(h));
            
        }
    }
    
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
game.cpp:32:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     for( int i = 1; i <= n; i++) scanf("%d",  &height[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~
game.cpp:43:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         int type; scanf("%d", &type);
      |                   ~~~~~^~~~~~~~~~~~~
game.cpp:47:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |             int pos, val; scanf("%d %d", &pos, &val);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~
game.cpp:73:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |             int h; scanf("%d", &h);
      |                    ~~~~~^~~~~~~~~~

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