oj.uz

Submission #846001

# Submission time Handle Problem Language Result Execution time Memory
846001 2023-09-07T04:15:34 Z zwezdinv Simple game (IZhO17_game) C++17
100 / 100
 43 ms 6984 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define all(x) x.begin(), x.end()
using ll = long long;

struct fenwick {
    int n;
    vector<int> tr;

    fenwick(int n) : n(n), tr(vector<int>(n, 0)) {}
    fenwick() = default;

    void upd(int k, int x) {
        for (; k < n; k = (k | (k + 1))) tr[k] += x;
    }

    int get(int k) {
        int res = 0;
        for (; k >= 0; k = (k & (k + 1)) - 1) res += tr[k];
        return res;
    }

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    int q;
    cin >> q;
    vector<int> a(n);
    fenwick fenw((int)1e6 + 1);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int x = 0; x + 1 < n; ++x) {
        fenw.upd(min(a[x], a[x + 1]), 1);
        fenw.upd(max(a[x], a[x + 1]) + 1, -1);
    }
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, y;
            cin >> x >> y;
            --x;
            if (x + 1 < n) {
                fenw.upd(min(a[x], a[x + 1]), -1);
                fenw.upd(max(a[x], a[x + 1]) + 1, 1);
            }
            if (x - 1 >= 0) {
                fenw.upd(min(a[x], a[x - 1]), -1);
                fenw.upd(max(a[x], a[x - 1]) + 1, 1);
            }
            a[x] = y;
            if (x + 1 < n) {
                fenw.upd(min(a[x], a[x + 1]), 1);
                fenw.upd(max(a[x], a[x + 1]) + 1, -1);
            }
            if (x - 1 >= 0) {
                fenw.upd(min(a[x], a[x - 1]), 1);
                fenw.upd(max(a[x], a[x - 1]) + 1, -1);
            }
        } else {
            int h;
            cin >> h;
            cout << fenw.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 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 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 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 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 31 ms 5644 KB Output is correct
9 Correct 32 ms 6748 KB Output is correct
10 Correct 31 ms 6908 KB Output is correct
11 Correct 29 ms 5456 KB Output is correct
12 Correct 34 ms 6688 KB Output is correct
13 Correct 31 ms 6748 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 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 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 31 ms 5644 KB Output is correct
9 Correct 32 ms 6748 KB Output is correct
10 Correct 31 ms 6908 KB Output is correct
11 Correct 29 ms 5456 KB Output is correct
12 Correct 34 ms 6688 KB Output is correct
13 Correct 31 ms 6748 KB Output is correct
14 Correct 41 ms 6744 KB Output is correct
15 Correct 41 ms 6736 KB Output is correct
16 Correct 41 ms 6784 KB Output is correct
17 Correct 43 ms 6820 KB Output is correct
18 Correct 41 ms 6984 KB Output is correct