oj.uz

Submission #593961

# Submission time Handle Problem Language Result Execution time Memory
593961 2022-07-11T18:24:49 Z hyakup Simple game (IZhO17_game) C++17
100 / 100
 64 ms 6796 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4144 KB Output is correct
2 Correct 4 ms 4180 KB Output is correct
3 Correct 3 ms 4180 KB Output is correct
4 Correct 3 ms 4164 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 3 ms 4152 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4144 KB Output is correct
2 Correct 4 ms 4180 KB Output is correct
3 Correct 3 ms 4180 KB Output is correct
4 Correct 3 ms 4164 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 3 ms 4152 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 43 ms 5476 KB Output is correct
9 Correct 47 ms 6728 KB Output is correct
10 Correct 62 ms 6792 KB Output is correct
11 Correct 44 ms 5408 KB Output is correct
12 Correct 47 ms 6488 KB Output is correct
13 Correct 45 ms 6568 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4144 KB Output is correct
2 Correct 4 ms 4180 KB Output is correct
3 Correct 3 ms 4180 KB Output is correct
4 Correct 3 ms 4164 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 3 ms 4152 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 43 ms 5476 KB Output is correct
9 Correct 47 ms 6728 KB Output is correct
10 Correct 62 ms 6792 KB Output is correct
11 Correct 44 ms 5408 KB Output is correct
12 Correct 47 ms 6488 KB Output is correct
13 Correct 45 ms 6568 KB Output is correct
14 Correct 59 ms 6756 KB Output is correct
15 Correct 64 ms 6684 KB Output is correct
16 Correct 62 ms 6780 KB Output is correct
17 Correct 62 ms 6796 KB Output is correct
18 Correct 61 ms 6768 KB Output is correct