oj.uz

Submission #825603

# Submission time Handle Problem Language Result Execution time Memory
825603 2023-08-15T06:11:25 Z Koyote Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 483 ms 87372 KB 
#include <bits/stdc++.h>
using namespace std;

int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

template <class S, S (*op)(S, S), S (*e)(),
          class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()>
struct lazy_segtree {
  public:
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

using S1 = int64_t;
struct F1 {};
S1 op1(S1 x, S1 y) { return x + y; }
S1 e1() { return 0LL; }
S1 mapping1(F1 f, S1 x) { (void)f; return x; }
F1 composition1(F1 f, F1 g) { (void)g; return f; }
F1 id1() { return F1{}; }

const int BASE_LENGTH = 60;
typedef array<int, BASE_LENGTH> int_baseK;
int K;

int64_t to_ll(const int_baseK &x) {
    int64_t res = 0;
    for (int i = BASE_LENGTH - 1; i >= 0; i--)
        res = res * K + x[i];
    return res;
}

int_baseK to_baseK(int64_t x) {
    int i = 0;
    int_baseK res{};
    while (x) res[i++] = x % K, x /= K;
    return res;
}

using S2 = int_baseK;
struct F2 { int c; };
S2 op2(S2 x, S2 y) {
    // int carry = 0;
    S2 res{};
    for (int i = 0; i < BASE_LENGTH; i++) {
        // int add = x[i] + y[i] + carry;
        // res[i] = add % K;
        // carry = add / K;
        res[i] = x[i] + y[i];
    }
    return res;
}
S2 e2() { return int_baseK{}; }
S2 mapping2(F2 f, S2 x) { 
    S2 res{};
    for (int i = 0; i + f.c < BASE_LENGTH; i++)
        res[i] = x[i + f.c];
    return res;
}
F2 composition2(F2 f, F2 g) { return F2{f.c + g.c}; }
F2 id2() { return F2{0}; }

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q; cin >> n >> q >> K;
    if (K == 1) {
        vector<S1> c(n); for (auto &i : c) cin >> i;
        lazy_segtree<S1, op1, e1, F1, mapping1, composition1, id1> segtree(c);
        while (q--) {
            int s, t, u; cin >> s >> t >> u; --t;
            if (s == 1) segtree.set(t, u);
            if (s == 3) cout << segtree.prod(t, u) << '\n';
        }
        return 0;
    }
    vector<S2> c(n);
    for (auto &it : c) {
        int64_t x; cin >> x;
        it = to_baseK(x);
    }
    lazy_segtree<S2, op2, e2, F2, mapping2, composition2, id2> segtree(c);
    while (q--) {
        int s, t, u; cin >> s >> t >> u; --t;
        if (s == 1) segtree.set(t, to_baseK(u));
        if (s == 2) segtree.apply(t, u, F2{1});
        if (s == 3) cout << to_ll(segtree.prod(t, u)) << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 1748 KB Output is correct
4 Correct 8 ms 1684 KB Output is correct
5 Correct 9 ms 3048 KB Output is correct
6 Correct 9 ms 3028 KB Output is correct
7 Correct 9 ms 3028 KB Output is correct
8 Correct 10 ms 3016 KB Output is correct
9 Correct 10 ms 3028 KB Output is correct
10 Correct 9 ms 3044 KB Output is correct
11 Correct 9 ms 3052 KB Output is correct
12 Correct 11 ms 3024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4016 KB Output is correct
2 Correct 26 ms 3648 KB Output is correct
3 Correct 22 ms 4880 KB Output is correct
4 Correct 29 ms 5588 KB Output is correct
5 Correct 34 ms 5992 KB Output is correct
6 Correct 35 ms 6092 KB Output is correct
7 Correct 36 ms 6088 KB Output is correct
8 Correct 36 ms 6084 KB Output is correct
9 Correct 31 ms 5960 KB Output is correct
10 Correct 32 ms 5864 KB Output is correct
11 Correct 39 ms 5968 KB Output is correct
12 Correct 33 ms 5848 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 5716 KB Output is correct
2 Correct 72 ms 41868 KB Output is correct
3 Correct 127 ms 41900 KB Output is correct
4 Correct 322 ms 21668 KB Output is correct
5 Correct 452 ms 86048 KB Output is correct
6 Correct 463 ms 85936 KB Output is correct
7 Correct 28 ms 4684 KB Output is correct
8 Correct 442 ms 87372 KB Output is correct
9 Correct 464 ms 87188 KB Output is correct
10 Correct 438 ms 87200 KB Output is correct
11 Correct 410 ms 87224 KB Output is correct
12 Correct 405 ms 87204 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 43672 KB Output is correct
2 Correct 303 ms 43768 KB Output is correct
3 Correct 206 ms 42036 KB Output is correct
4 Correct 326 ms 23588 KB Output is correct
5 Correct 454 ms 86140 KB Output is correct
6 Correct 483 ms 86160 KB Output is correct
7 Correct 470 ms 86348 KB Output is correct
8 Correct 459 ms 86180 KB Output is correct
9 Correct 414 ms 86264 KB Output is correct
10 Correct 446 ms 86120 KB Output is correct
11 Correct 431 ms 86220 KB Output is correct
12 Correct 433 ms 86168 KB Output is correct