oj.uz

Submission #941139

# Submission time Handle Problem Language Result Execution time Memory
941139 2024-03-08T07:54:39 Z atom Simple game (IZhO17_game) C++17
100 / 100
 248 ms 43684 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

struct SegmentTree {
    int n;
    vector <int> f, lzy;
    SegmentTree(int _n) : n(_n), f((_n << 2) + 5), lzy((_n << 2) + 5) {};
    int merge(int x, int y) {
        return (x + y);
    }
    void push(int x, int l, int r) {
        if (!lzy[x]) return;
        int m = (l + r) / 2;

        lzy[x << 1] += lzy[x];
        f[x << 1] += lzy[x] * (m - l + 1);

        lzy[x << 1 | 1] += lzy[x];
        f[x << 1 | 1] += lzy[x] * (r - m);

        lzy[x] = 0;
    }
    void upd(int x, int l, int r, int u, int v, int val) {
        if (l > v || r < u) return;
        if (u <= l && r <= v) {
            lzy[x] += val;
            f[x] += val * (r - l + 1);
            return;
        }
        int m = (l + r) >> 1;
        push(x, l, r);
        upd(x << 1, l, m, u, v, val);
        upd(x << 1 | 1, m + 1, r, u, v, val);
        f[x] = merge(f[x << 1], f[x << 1 | 1]);
    }
    int qry(int x, int l, int r, int u, int v) {
        if (l > v || r < u) return 0;
        if (u <= l && r <= v) return f[x];
        int m = (l + r) >> 1;
        push(x, l, r);
        int ql = qry(x << 1, l, m, u, v);
        int qr = qry(x << 1 | 1, m + 1, r, u, v);
        return merge(ql, qr);
    }
    void upd(int l, int r, int val) { upd(1, 1, n, l, r, val); }
    int qry(int l, int r) { return qry(1, 1, n, l, r); }
};

const int N = 1e6 + 5;
signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    int n, q;
    cin >> n >> q;
    vector <int> h(n + 5);
    vector <vector <int>> queries(q + 5);

    for (int i = 1; i <= n; ++i) cin >> h[i];

    for (int i = 1; i <= q; ++i) {
        int cmd; cin >> cmd;
        if (cmd == 1) {
            int x, y; cin >> x >> y;
            queries[i] = {cmd, x, y};
        }
        else {
            int x; cin >> x;
            queries[i] = {cmd, x};
        }
    }

   
    vector <int> cnt(N);
    SegmentTree st(N);
    for (int i = 1; i <= n; ++i) cnt[h[i]]++;
    for (int i = 2; i <= n; ++i) {
        int l = h[i - 1], r = h[i];
        if (l > r) swap(l, r);
        l++, r--;
        st.upd(l, r, 1);
    }
    for (int i = 1; i <= q; ++i) {
        // debug(queries[i]);
        int cmd = queries[i][0];
        int x, y;
        if (cmd == 1) {
            x = queries[i][1]; y = queries[i][2];

            cnt[h[x]]--;
            if (x > 1) {
                int l = h[x - 1], r = h[x];
                if (l > r) swap(l, r);
                st.upd(l + 1, r - 1, -1);
            }
            if (x < n) {
                int l = h[x], r = h[x + 1];
                if (l > r) swap(l, r);
                st.upd(l + 1, r - 1, -1);
            }

            h[x] = y;

            cnt[h[x]]++;
            if (x > 1) {
                int l = h[x - 1], r = h[x];
                if (l > r) swap(l, r);
                st.upd(l + 1, r - 1, 1);
            }
            if (x < n) {
                int l = h[x], r = h[x + 1];
                if (l > r) swap(l, r);
                st.upd(l + 1, r - 1, 1);
            }
        }
        else {
            x = queries[i][1];
            ll ans = cnt[x] + st.qry(x, x);
            cout << ans << "\n";
        }
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35676 KB Output is correct
2 Correct 9 ms 35676 KB Output is correct
3 Correct 10 ms 35676 KB Output is correct
4 Correct 9 ms 35676 KB Output is correct
5 Correct 9 ms 35676 KB Output is correct
6 Correct 9 ms 35664 KB Output is correct
7 Correct 8 ms 35676 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35676 KB Output is correct
2 Correct 9 ms 35676 KB Output is correct
3 Correct 10 ms 35676 KB Output is correct
4 Correct 9 ms 35676 KB Output is correct
5 Correct 9 ms 35676 KB Output is correct
6 Correct 9 ms 35664 KB Output is correct
7 Correct 8 ms 35676 KB Output is correct
8 Correct 59 ms 42492 KB Output is correct
9 Correct 128 ms 43084 KB Output is correct
10 Correct 152 ms 43080 KB Output is correct
11 Correct 49 ms 42064 KB Output is correct
12 Correct 87 ms 43088 KB Output is correct
13 Correct 108 ms 43096 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35676 KB Output is correct
2 Correct 9 ms 35676 KB Output is correct
3 Correct 10 ms 35676 KB Output is correct
4 Correct 9 ms 35676 KB Output is correct
5 Correct 9 ms 35676 KB Output is correct
6 Correct 9 ms 35664 KB Output is correct
7 Correct 8 ms 35676 KB Output is correct
8 Correct 59 ms 42492 KB Output is correct
9 Correct 128 ms 43084 KB Output is correct
10 Correct 152 ms 43080 KB Output is correct
11 Correct 49 ms 42064 KB Output is correct
12 Correct 87 ms 43088 KB Output is correct
13 Correct 108 ms 43096 KB Output is correct
14 Correct 248 ms 43088 KB Output is correct
15 Correct 240 ms 43600 KB Output is correct
16 Correct 244 ms 43684 KB Output is correct
17 Correct 232 ms 43604 KB Output is correct
18 Correct 246 ms 43600 KB Output is correct