oj.uz

Submission #576914

# Submission time Handle Problem Language Result Execution time Memory
576914 2022-06-13T19:04:33 Z Lawliet Simple game (IZhO17_game) C++17
100 / 100
 190 ms 9596 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 1e6 + 10;
 
int n, m, v[MAX], op, seg[4 * MAX], x, y, h;
 
void update(int p, int q, int ini, int fim, int pos, int val){
    if(fim < p || q < ini) return;
    if(p <= ini && fim <= q){
        seg[pos] += val;
       
        return;
    }
   
    int m = (ini + fim) / 2;
   
    update(p, q, ini, m, 2 * pos, val);
    update(p, q, m + 1, fim, 2 * pos + 1, val);
   
    return;
}
 
int query(int id, int ini, int fim, int pos){
    if(id < ini || fim < id) return 0;
    if(ini == fim) return seg[pos];
   
    int m = (ini + fim) / 2;
    int a = query(id, ini, m, 2 * pos);
    int b = query(id, m + 1, fim, 2 * pos + 1);
   
    return seg[pos] + a + b;
}
 
int main(){
    scanf("%d %d", &n, &m);
   
    for(int i = 1; i <= n; i++){
        scanf("%d", &v[i]);
       
        if(i > 1){
            int a = min(v[i], v[i - 1]);
            int b = max(v[i], v[i - 1]);
           
            update(a, b, 0,MAX, 1, 1);
        }
    }
   
    for(int i = 1; i <= m; i++){
        scanf("%d", &op);
       
        if(op == 1){
            scanf("%d %d", &x, &y);
           
            if(x > 1){
                int a = min(v[x], v[x - 1]);
                int b = max(v[x], v[x - 1]);
               
                update(a, b, 0, MAX, 1, - 1);
               
                a = min(y, v[x - 1]);
                b = max(y, v[x - 1]);
               
                update(a, b, 0, MAX, 1, 1);
            }
            if(x < n){
                int a = min(v[x], v[x + 1]);
                int b = max(v[x], v[x + 1]);
               
                update(a, b, 0, MAX, 1, - 1);
               
                a = min(y, v[x + 1]);
                b = max(y, v[x + 1]);
               
                update(a, b, 0, MAX, 1, 1);
            }
           
            v[x] = y;
           
            continue;
        }
       
        scanf("%d", &h);
       
        printf("%d\n", query(h, 0,MAX, 1));
    }
   
    return 0;
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
game.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%d", &v[i]);
      |         ~~~~~^~~~~~~~~~~~~
game.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d", &op);
      |         ~~~~~^~~~~~~~~~~
game.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |             scanf("%d %d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~
game.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%d", &h);
      |         ~~~~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 5 ms 6336 KB Output is correct
4 Correct 4 ms 6484 KB Output is correct
5 Correct 5 ms 6464 KB Output is correct
6 Correct 4 ms 6612 KB Output is correct
7 Correct 2 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 5 ms 6336 KB Output is correct
4 Correct 4 ms 6484 KB Output is correct
5 Correct 5 ms 6464 KB Output is correct
6 Correct 4 ms 6612 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 57 ms 1028 KB Output is correct
9 Correct 113 ms 9512 KB Output is correct
10 Correct 113 ms 9596 KB Output is correct
11 Correct 49 ms 912 KB Output is correct
12 Correct 83 ms 1612 KB Output is correct
13 Correct 78 ms 1412 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 5 ms 6336 KB Output is correct
4 Correct 4 ms 6484 KB Output is correct
5 Correct 5 ms 6464 KB Output is correct
6 Correct 4 ms 6612 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 57 ms 1028 KB Output is correct
9 Correct 113 ms 9512 KB Output is correct
10 Correct 113 ms 9596 KB Output is correct
11 Correct 49 ms 912 KB Output is correct
12 Correct 83 ms 1612 KB Output is correct
13 Correct 78 ms 1412 KB Output is correct
14 Correct 175 ms 9332 KB Output is correct
15 Correct 176 ms 9264 KB Output is correct
16 Correct 183 ms 9200 KB Output is correct
17 Correct 190 ms 9372 KB Output is correct
18 Correct 175 ms 9264 KB Output is correct