oj.uz

Submission #596241

# Submission time Handle Problem Language Result Execution time Memory
596241 2022-07-14T14:00:47 Z LucaGreg Simple game (IZhO17_game) C++17
100 / 100
 75 ms 6808 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 4052 KB Output is correct
3 Correct 3 ms 4032 KB Output is correct
4 Correct 3 ms 4052 KB Output is correct
5 Correct 2 ms 4052 KB Output is correct
6 Correct 2 ms 4052 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 4052 KB Output is correct
3 Correct 3 ms 4032 KB Output is correct
4 Correct 3 ms 4052 KB Output is correct
5 Correct 2 ms 4052 KB Output is correct
6 Correct 2 ms 4052 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 40 ms 1676 KB Output is correct
9 Correct 48 ms 6732 KB Output is correct
10 Correct 49 ms 6744 KB Output is correct
11 Correct 44 ms 1528 KB Output is correct
12 Correct 44 ms 2832 KB Output is correct
13 Correct 43 ms 2708 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 4052 KB Output is correct
3 Correct 3 ms 4032 KB Output is correct
4 Correct 3 ms 4052 KB Output is correct
5 Correct 2 ms 4052 KB Output is correct
6 Correct 2 ms 4052 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 40 ms 1676 KB Output is correct
9 Correct 48 ms 6732 KB Output is correct
10 Correct 49 ms 6744 KB Output is correct
11 Correct 44 ms 1528 KB Output is correct
12 Correct 44 ms 2832 KB Output is correct
13 Correct 43 ms 2708 KB Output is correct
14 Correct 60 ms 6760 KB Output is correct
15 Correct 61 ms 6740 KB Output is correct
16 Correct 75 ms 6808 KB Output is correct
17 Correct 59 ms 6772 KB Output is correct
18 Correct 58 ms 6704 KB Output is correct