Submission #941137

#	Time	Username	Problem	Language	Result	Execution time	Memory
941137		atom	Simple game (IZhO17_game)	C++17	0 / 100	9 ms	35676 KiB

game

#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];

    bool sub2 = 1;
    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};
            sub2 = 0;
        }
        else {
            int x; cin >> x;
            queries[i] = {cmd, x};
        }
    }

    // sub1
    // if (n <= 1000 && q <= 1000) {
    //     vector <int> cnt(N, 0);
    //     for (int i = 1; i <= n; ++i) cnt[h[i]]++;
    //     for (int i = 1; i <= q; ++i) {
    //         if (queries[i][0] == 1) {
    //             cnt[h[queries[i][1]]]--;
    //             h[queries[i][1]] = queries[i][2];
    //             cnt[h[queries[i][1]]]++;
    //         }
    //         else {
    //             int ans = 0;
    //             int H = queries[i][1];
    //             for (int j = 2; j <= n; ++j)
    //                 if ((h[j - 1] < H && H < h[j]) || (h[j - 1] > H && H > h[j]))
    //                     ++ans;
    //             cout << ans << "\n";
    //         }
    //     }
    // }
    // else if (sub2) {
    //     // Fenwick
    //     vector <int> cnt(N);
    //     vector <int> prf(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--;
    //         if (l <= r) {
    //             prf[l]++;
    //             prf[r + 1]--;
    //         }
    //     }
    //     for (int i = 1; i < N; ++i) prf[i] += prf[i - 1];
    //     for (int i = 1; i <= q; ++i) {
    //         cout << (cnt[queries[i][1]] + prf[queries[i][1]]) << "\n";
    //     }
    // }
    // else 
    // {  
        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 (i > 1) {
                    int l = h[i - 1], r = h[i];
                    if (l > r) swap(l, r);
                    st.upd(l + 1, r - 1, -1);
                }
                if (i < n) {
                    int l = h[i], r = h[i + 1];
                    if (l > r) swap(l, r);
                    st.upd(l + 1, r - 1, -1);
                }

                h[x] = y;

                cnt[h[x]]++;
                if (i > 1) {
                    int l = h[i - 1], r = h[i];
                    if (l > r) swap(l, r);
                    st.upd(l + 1, r - 1, 1);
                }
                if (i < n) {
                    int l = h[i], r = h[i + 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";
            }
        // }
    }
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:68:10: warning: variable 'sub2' set but not used [-Wunused-but-set-variable]
   68 |     bool sub2 = 1;
      |          ^~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51