Submission #1210737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210737		Double_Slash	Sterilizing Spray (JOI15_sterilizing)	C++20	0 / 100	370 ms	31788 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};
            pull();
        } else {
            cin >> val[0];
            for (int j = 1; j < 30; ++j) {
                val[j] = val[j - 1] / K;
                val[j - 1] %= K;
            }
        }
    }

    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);
    }
};

int main() {
    cin >> n >> q >> K;
    Node root{1, n};
    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;
    }
}

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