Submission #1210739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210739		Double_Slash	Sterilizing Spray (JOI15_sterilizing)	C++20	10 / 100	427 ms	31792 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n, q, K;
struct Node {
    int val[30]{}, lazy = 0;
    Node *lc{}, *rc;

    void pull() { for (int j = 30; j--;) val[j] = lc->val[j] + rc->val[j]; }

    Node(int l, int r) {
        if (l < r) {
            int m = (l + r) >> 1;
            lc = new Node{l, m};
            rc = new Node{m + 1, r};
        }
    }

    void push() {
        for (int i = 0; i < 30; ++i) val[i] = i + lazy < 30 ? val[i + lazy] : 0;
        if (lc) lc->lazy += lazy, rc->lazy += lazy;
        lazy = 0;
    }

    void update(int l, int r, int i, int v) {
        push();
        if (i < l or i > r) return;
        if (l == r) {
            for (int j = 0; j < 30; v /= K) val[j++] = v % K;
            return;
        }
        int m = (l + r) >> 1;
        lc->update(l, m, i, v);
        rc->update(m + 1, r, i, v);
        pull();
    }

    void update(int l, int r, int ul, int ur, int v) {
        push();
        if (ul > r or ur < l) return;
        if (l >= ul and r <= ur) {
            lazy += v;
            push();
            return;
        }
        int m = (l + r) >> 1;
        lc->update(l, m, ul, ur, v);
        rc->update(m + 1, r, ul, ur, v);
        pull();
    }

    ll query(int l, int r, int ql, int qr) {
        if (ql > r or qr < l) return 0;
        push();
        if (l >= ql and r <= qr) {
            ll ans = 0;
            for (int j = 0, k = 1; j < 30; ++j, k *= K) ans += k * val[j];
            return ans;
        }
        int m = (l + r) >> 1;
        return lc->query(l, m, ql, qr) + rc->query(m + 1, r, ql, qr);
    }
};

struct St {
    vector<ll> st;

    St() : st(n << 1) {}

    void update(int i, int v) {
        for (st[i += n] = v; i >>= 1;) st[i] = st[i << 1] + st[i << 1 | 1];
    }

    int query(int l, int r) {
        ll ret = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ret += st[l++];
            if (r & 1) ret += st[--r];
        }
        return ret;
    }
};

int main() {
    cin >> n >> q >> K;
    if (K > 1) {
        Node root{1, n};
        for (int i = 1; i <= n; ++i) {
            int x;
            cin >> x;
            root.update(1, n, i, x);
        }
        while (q--) {
            int s, t, u;
            cin >> s >> t >> u;
            if (s == 1) root.update(1, n, t, u);
            else if (s == 2) root.update(1, n, t, u, 1);
            else cout << root.query(1, n, t, u) << endl;
        }
    } else {
        St st;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            st.update(i, x);
        }
        while (q--) {
            int s, t, u;
            cin >> s >> t >> u;
            if (s == 1) st.update(t - 1, u);
            else if (s == 3) cout << st.query(t - 1, u) << endl;
        }
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 75