oj.uz

Submission #445964

# Submission time Handle Problem Language Result Execution time Memory
445964 2021-07-20T09:38:18 Z dxz05 Simple game (IZhO17_game) C++14
100 / 100
 209 ms 6920 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 3e2;

int f[MAXN];

void add(int i, int x){
    while (i < MAXN){
        f[i] += x;
        i += (-i & i);
    }
}

void add(int l, int r, int x){
    if (l > r) swap(l, r);
    add(l, x);
    add(r + 1, -x);
}

int get(int i){
    int res = 0;
    while (i > 0){
        res += f[i];
        i -= (-i & i);
    }
    return res;
}

int a[MAXN];
int main(){
    ios_base::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++){
        cin >> a[i];
        if (i > 1) add(a[i - 1], a[i], 1);
    }

    while (q--){
        int t;
        cin >> t;
        if (t == 1){
            int i, x;
            cin >> i >> x;
            if (i > 1){
                add(a[i - 1], a[i], -1);
                add(a[i - 1], x, 1);
            }
            if (i < n){
                add(a[i], a[i + 1], -1);
                add(x, a[i + 1], 1);
            }
            a[i] = x;
        } else {
            int h;
            cin >> h;
            cout << get(h) << endl;
        }
    }

    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 4 ms 4164 KB Output is correct
4 Correct 4 ms 4172 KB Output is correct
5 Correct 4 ms 4044 KB Output is correct
6 Correct 3 ms 4044 KB Output is correct
7 Correct 3 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 4 ms 4164 KB Output is correct
4 Correct 4 ms 4172 KB Output is correct
5 Correct 4 ms 4044 KB Output is correct
6 Correct 3 ms 4044 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 193 ms 1656 KB Output is correct
9 Correct 206 ms 6840 KB Output is correct
10 Correct 209 ms 6920 KB Output is correct
11 Correct 192 ms 1560 KB Output is correct
12 Correct 196 ms 2792 KB Output is correct
13 Correct 202 ms 2804 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 4 ms 4164 KB Output is correct
4 Correct 4 ms 4172 KB Output is correct
5 Correct 4 ms 4044 KB Output is correct
6 Correct 3 ms 4044 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 193 ms 1656 KB Output is correct
9 Correct 206 ms 6840 KB Output is correct
10 Correct 209 ms 6920 KB Output is correct
11 Correct 192 ms 1560 KB Output is correct
12 Correct 196 ms 2792 KB Output is correct
13 Correct 202 ms 2804 KB Output is correct
14 Correct 166 ms 6828 KB Output is correct
15 Correct 171 ms 6860 KB Output is correct
16 Correct 165 ms 6772 KB Output is correct
17 Correct 165 ms 6724 KB Output is correct
18 Correct 153 ms 6768 KB Output is correct