Submission #829990

#	Time	Username	Problem	Language	Result	Execution time	Memory
829990		vjudge1	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	513 ms	59692 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;

// 123

int n, q, k;

class segtree_t {
       public:
        segtree_t *left, *right;
        int l, r, m, lazy;
        int64_t val[31];

        segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), lazy(0) {
                if (l == r) return;
                left = new segtree_t(l, m);
                right = new segtree_t(m + 1, r);
        }

        void Rotate(int r) {
                for (int i = 30; i >= 0; i--) {
                        val[i] = i - r >= 0 ? val[i - r] : (k == 1 ? val[i] : 0);
                }
        }

        void Update(int p, int x) {
                if (l == r) {
                        for (int i = 30; i >= 0; i--) val[i] = x, x /= k;
                        lazy = 0;
                        return;
                }
                Down();
                if (p <= m) {
                        left->Update(p, x);
                } else {
                        right->Update(p, x);
                }
                Up();
        }

        void Up() {
                for (int i = 30; i >= 0; i--) {
                        val[i] = left->val[i] + right->val[i];
                }
        }

        void Down() {
                left->lazy += lazy;
                right->lazy += lazy;
                left->Rotate(lazy);
                right->Rotate(lazy);
                lazy = 0;
        }

        void Change(int s, int t) {
                if (l > t || r < s) return;
                if (s <= l && r <= t) {
                        Rotate(1);
                        lazy++;
                        return;
                }
                Down();
                left->Change(s, t);
                right->Change(s, t);
                Up();
        }

        int64_t Get(int s, int t) {
                if (l > t || r < s) return 0;
                if (s <= l && r <= t) return val[30];
                Down();
                return left->Get(s, t) + right->Get(s, t);
        }
};

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cin >> n >> q >> k;
        segtree_t *tree = new segtree_t(1, n);
        for (int i = 1; i <= n; i++) {
                int a;
                cin >> a;
                tree->Update(i, a);
        }
        for (int i = 0; i < q; i++) {
                int _, l, r;
                cin >> _ >> l >> r;
                if (_ == 1) {
                        tree->Update(l, r);
                } else if (_ == 2) {
                        tree->Change(l, r);
                } else {
                        cout << tree->Get(l, r) << '\n';
                }
        }
}

Compilation message (stderr)

sterilizing.cpp: In constructor 'segtree_t::segtree_t(int, int)':
sterilizing.cpp:14:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |         segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), lazy(0) {
      |                                                 ~~^~~

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