oj.uz

Submission #829987

# Submission time Handle Problem Language Result Execution time Memory
829987 2023-08-18T16:51:35 Z vjudge1 Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 525 ms 59332 KB 
#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] : 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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Incorrect 3 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 373 ms 30004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 4368 KB Output is correct
2 Correct 111 ms 25760 KB Output is correct
3 Correct 135 ms 25936 KB Output is correct
4 Correct 287 ms 15312 KB Output is correct
5 Correct 470 ms 58112 KB Output is correct
6 Correct 484 ms 58080 KB Output is correct
7 Incorrect 489 ms 58208 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 30920 KB Output is correct
2 Correct 345 ms 31608 KB Output is correct
3 Correct 217 ms 26808 KB Output is correct
4 Correct 313 ms 20308 KB Output is correct
5 Correct 489 ms 59332 KB Output is correct
6 Correct 493 ms 59324 KB Output is correct
7 Correct 516 ms 59276 KB Output is correct
8 Correct 525 ms 59324 KB Output is correct
9 Correct 423 ms 59204 KB Output is correct
10 Correct 426 ms 59244 KB Output is correct
11 Correct 416 ms 59176 KB Output is correct
12 Correct 457 ms 59216 KB Output is correct