oj.uz

Submission #829990

# Submission time Handle Problem Language Result Execution time Memory
829990 2023-08-18T16:54:47 Z vjudge1 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 513 ms 59692 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] : (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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 1360 KB Output is correct
4 Correct 6 ms 1108 KB Output is correct
5 Correct 8 ms 2080 KB Output is correct
6 Correct 8 ms 2084 KB Output is correct
7 Correct 8 ms 2004 KB Output is correct
8 Correct 8 ms 2084 KB Output is correct
9 Correct 8 ms 2080 KB Output is correct
10 Correct 9 ms 2072 KB Output is correct
11 Correct 8 ms 2004 KB Output is correct
12 Correct 8 ms 2004 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 28220 KB Output is correct
2 Correct 269 ms 21064 KB Output is correct
3 Correct 315 ms 45812 KB Output is correct
4 Correct 409 ms 58312 KB Output is correct
5 Correct 485 ms 59596 KB Output is correct
6 Correct 513 ms 59692 KB Output is correct
7 Correct 485 ms 59684 KB Output is correct
8 Correct 490 ms 59548 KB Output is correct
9 Correct 399 ms 59444 KB Output is correct
10 Correct 390 ms 59516 KB Output is correct
11 Correct 398 ms 59456 KB Output is correct
12 Correct 388 ms 59372 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3932 KB Output is correct
2 Correct 103 ms 25532 KB Output is correct
3 Correct 122 ms 25588 KB Output is correct
4 Correct 245 ms 14172 KB Output is correct
5 Correct 504 ms 56660 KB Output is correct
6 Correct 451 ms 56660 KB Output is correct
7 Correct 456 ms 57004 KB Output is correct
8 Correct 506 ms 58060 KB Output is correct
9 Correct 357 ms 57932 KB Output is correct
10 Correct 355 ms 58000 KB Output is correct
11 Correct 418 ms 57952 KB Output is correct
12 Correct 364 ms 57996 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 29412 KB Output is correct
2 Correct 297 ms 29816 KB Output is correct
3 Correct 192 ms 25748 KB Output is correct
4 Correct 278 ms 18712 KB Output is correct
5 Correct 502 ms 56904 KB Output is correct
6 Correct 457 ms 56984 KB Output is correct
7 Correct 473 ms 57052 KB Output is correct
8 Correct 475 ms 56884 KB Output is correct
9 Correct 393 ms 56892 KB Output is correct
10 Correct 380 ms 56964 KB Output is correct
11 Correct 376 ms 56912 KB Output is correct
12 Correct 373 ms 56928 KB Output is correct