oj.uz

Submission #72949

# Submission time Handle Problem Language Result Execution time Memory
72949 2018-08-27T09:37:09 Z win11905 Simple game (IZhO17_game) C++11
100 / 100
 138 ms 22652 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
const int MX = 1e6;

int n, m, A[N];
int t[MX];

void update(int x, int v) {
    for(; x <= MX; x += x & -x) t[x-1] += v;
}

int query(int x) {
    int v = 0;
    for(; x; x -= x & -x) v += t[x-1];
    return v;
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", A+i);
    for(int i = 1; i < n; ++i) {
        update(min(A[i], A[i+1]), 1);
        update(max(A[i], A[i+1]), -1);
    } 
    for(int i = 0, a, b, c; i < m; ++i) {
        scanf("%d %d", &a, &b);
        if(a == 1) {
            scanf("%d", &c);
            if(b != 1) {
                update(min(A[b], A[b-1]), -1);
                update(max(A[b], A[b-1]), 1);
                update(min(c, A[b-1]), 1);
                update(max(c, A[b-1]), -1);
            }
            if(b != n) {
                update(min(A[b], A[b+1]), -1);
                update(max(A[b], A[b+1]), 1);
                update(min(c, A[b+1]), 1);
                update(max(c, A[b+1]), -1);
            }
            A[b] = c;
        } else printf("%d\n", query(b)); 
    }
    
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
game.cpp:22:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; ++i) scanf("%d", A+i);
                                 ~~~~~^~~~~~~~~~~
game.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
game.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &c);
             ~~~~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 6 ms 3940 KB Output is correct
3 Correct 7 ms 4076 KB Output is correct
4 Correct 7 ms 4104 KB Output is correct
5 Correct 7 ms 4104 KB Output is correct
6 Correct 9 ms 4232 KB Output is correct
7 Correct 4 ms 4232 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 6 ms 3940 KB Output is correct
3 Correct 7 ms 4076 KB Output is correct
4 Correct 7 ms 4104 KB Output is correct
5 Correct 7 ms 4104 KB Output is correct
6 Correct 9 ms 4232 KB Output is correct
7 Correct 4 ms 4232 KB Output is correct
8 Correct 56 ms 4232 KB Output is correct
9 Correct 85 ms 7996 KB Output is correct
10 Correct 86 ms 9720 KB Output is correct
11 Correct 57 ms 9720 KB Output is correct
12 Correct 72 ms 9720 KB Output is correct
13 Correct 73 ms 9720 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 6 ms 3940 KB Output is correct
3 Correct 7 ms 4076 KB Output is correct
4 Correct 7 ms 4104 KB Output is correct
5 Correct 7 ms 4104 KB Output is correct
6 Correct 9 ms 4232 KB Output is correct
7 Correct 4 ms 4232 KB Output is correct
8 Correct 56 ms 4232 KB Output is correct
9 Correct 85 ms 7996 KB Output is correct
10 Correct 86 ms 9720 KB Output is correct
11 Correct 57 ms 9720 KB Output is correct
12 Correct 72 ms 9720 KB Output is correct
13 Correct 73 ms 9720 KB Output is correct
14 Correct 129 ms 14764 KB Output is correct
15 Correct 138 ms 16892 KB Output is correct
16 Correct 103 ms 18668 KB Output is correct
17 Correct 125 ms 20724 KB Output is correct
18 Correct 124 ms 22652 KB Output is correct