oj.uz

Submission #854560

# Submission time Handle Problem Language Result Execution time Memory
854560 2023-09-28T04:22:08 Z The_Samurai Simple game (IZhO17_game) C++17
100 / 100
 48 ms 7260 KB 
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int inf = 1e9, N = 1e6 + 5;

struct Fenwick {
    vector<int> tree;
    int len;

    void init(int n) {
        len = n;
        tree.assign(len + 1, 0);
    }

    void update(int i, int v) {
        i++;
        while (i <= len) {
            tree[i] += v;
            i += i & (-i);
        }
    }

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

    int get(int l, int r) {
        return get(r) - get(l - 1);
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("subsequence.in", "r", stdin);
//    freopen("subsequence.out", "w", stdout);
#endif

    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    Fenwick fw; fw.init(N);
    auto upd = [&](int i, int add) {
        fw.update(min(a[i - 1], a[i]), add);
        fw.update(max(a[i - 1], a[i]) + 1, -add);
    };
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i > 1) upd(i, 1);
    }
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int i, v;
            cin >> i >> v;
            if (i > 1) upd(i, -1);
            if (i < n) upd(i + 1, -1);
            a[i] = v;
            if (i > 1) upd(i, 1);
            if (i < n) upd(i + 1, 1);
        } else {
            int h;
            cin >> h;
            cout << fw.get(h) << '\n';
        }
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 1 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 1 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 26 ms 5212 KB Output is correct
9 Correct 32 ms 6736 KB Output is correct
10 Correct 32 ms 7000 KB Output is correct
11 Correct 25 ms 5464 KB Output is correct
12 Correct 38 ms 6740 KB Output is correct
13 Correct 28 ms 6740 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 1 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 26 ms 5212 KB Output is correct
9 Correct 32 ms 6736 KB Output is correct
10 Correct 32 ms 7000 KB Output is correct
11 Correct 25 ms 5464 KB Output is correct
12 Correct 38 ms 6740 KB Output is correct
13 Correct 28 ms 6740 KB Output is correct
14 Correct 42 ms 7260 KB Output is correct
15 Correct 48 ms 6740 KB Output is correct
16 Correct 45 ms 6796 KB Output is correct
17 Correct 42 ms 6900 KB Output is correct
18 Correct 43 ms 6740 KB Output is correct