Submission #596241

#	Time	Username	Problem	Language	Result	Execution time	Memory
596241		LucaGreg	Simple game (IZhO17_game)	C++17	100 / 100	75 ms	6808 KiB

game

#include <bits/stdc++.h>
 
using namespace std;
 
int bit[1000010]; 
int h[100010];

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

int query(int i) {
    int soma = 0;
    for(int j = i; j>0; j-=j&-j) {
        soma+=bit[j];
    }
    return soma;
}
 
int main()
{
    int n, m; scanf("%d %d", &n, &m);
    scanf("%d", &h[1]);
    for(int i=2;i<=n;i++){
        scanf("%d", &h[i]);
        update(min(h[i-1], h[i]), 1);
        update(max(h[i-1], h[i])+1, -1);
    }
    for(int i=0;i<m;i++){
        int t; scanf("%d", &t);
        if(t==2){
            int hq; scanf("%d", &hq);
            printf("%d\n", query(hq));
        }else if(t==1){
            int pos, val; scanf("%d %d", &pos, &val);
            if(pos==1){
                //elimina a chain com o vertice seguinte
                update(min(h[pos], h[pos+1]), -1);
                update(max(h[pos], h[pos+1])+1, 1);
                //cria a chain(com a nova altura) com o vertice seguinte 
                update(min(val, h[pos+1]), 1);
                update(max(val, h[pos+1])+1, -1);
            }else if(pos==n){
                //elimina a chain com o vertice anterior 
                update(min(h[pos], h[pos-1]), -1);
                update(max(h[pos], h[pos-1])+1, 1);
                //cria a chain(com a nova altura) com o vertice anterior 
                update(min(val, h[pos-1]), 1);
                update(max(val, h[pos-1])+1, -1);
            }else{
                //elimina a chain com o vertice seguinte
                update(min(h[pos], h[pos+1]), -1);
                update(max(h[pos], h[pos+1])+1, 1);
                //elimina a chain com o vertice anterior
                update(min(h[pos], h[pos-1]), -1);
                update(max(h[pos], h[pos-1])+1, 1);
                //cria a chain(com a nova altura) com o vertice seguinte 
                update(min(val, h[pos+1]), 1);
                update(max(val, h[pos+1])+1, -1);
                //cria a chain(com a nova altura) com o vertice anterior 
                update(min(val, h[pos-1]), 1);
                update(max(val, h[pos-1])+1, -1);
            }
            h[pos] = val;
        }
    }
    
    return 0;
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:24:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     int n, m; scanf("%d %d", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~~
game.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d", &h[1]);
      |     ~~~~~^~~~~~~~~~~~~
game.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d", &h[i]);
      |         ~~~~~^~~~~~~~~~~~~
game.cpp:32:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         int t; scanf("%d", &t);
      |                ~~~~~^~~~~~~~~~
game.cpp:34:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |             int hq; scanf("%d", &hq);
      |                     ~~~~~^~~~~~~~~~~
game.cpp:37:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |             int pos, val; scanf("%d %d", &pos, &val);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~

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