Submission #825610

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
825610	2023-08-15T06:19:24 Z	Koyote	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	485 ms	86200 KB

sterilizing

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

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 = lazy_segtree<S, op, e, F, mapping, composition, id>::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);
        }
    }

  private:
    static int ceil_pow2(int n) {
        int x = 0;
        while ((1U << x) < (unsigned int)(n)) x++;
        return x;
    }
    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) {
    S2 res{};
    for (int i = 0; i < BASE_LENGTH; i++) 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	5 ms	404 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	1620 KB	Output is correct
4	Correct	8 ms	1628 KB	Output is correct
5	Correct	11 ms	2900 KB	Output is correct
6	Correct	14 ms	2900 KB	Output is correct
7	Correct	9 ms	2980 KB	Output is correct
8	Correct	9 ms	2988 KB	Output is correct
9	Correct	9 ms	2900 KB	Output is correct
10	Correct	9 ms	2900 KB	Output is correct
11	Correct	9 ms	2992 KB	Output is correct
12	Correct	9 ms	2984 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	2128 KB	Output is correct
2	Correct	24 ms	1924 KB	Output is correct
3	Correct	21 ms	3224 KB	Output is correct
4	Correct	27 ms	3524 KB	Output is correct
5	Correct	39 ms	3548 KB	Output is correct
6	Correct	33 ms	3548 KB	Output is correct
7	Correct	32 ms	3588 KB	Output is correct
8	Correct	45 ms	3556 KB	Output is correct
9	Correct	32 ms	3536 KB	Output is correct
10	Correct	33 ms	3536 KB	Output is correct
11	Correct	33 ms	3544 KB	Output is correct
12	Correct	33 ms	3544 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	118 ms	5720 KB	Output is correct
2	Correct	105 ms	41864 KB	Output is correct
3	Correct	117 ms	41904 KB	Output is correct
4	Correct	423 ms	21792 KB	Output is correct
5	Correct	441 ms	85932 KB	Output is correct
6	Correct	441 ms	85976 KB	Output is correct
7	Correct	28 ms	3348 KB	Output is correct
8	Correct	436 ms	85940 KB	Output is correct
9	Correct	437 ms	85924 KB	Output is correct
10	Correct	408 ms	86056 KB	Output is correct
11	Correct	402 ms	85916 KB	Output is correct
12	Correct	417 ms	85940 KB	Output is correct

Subtask #4

75.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	270 ms	43596 KB	Output is correct
2	Correct	320 ms	43808 KB	Output is correct
3	Correct	212 ms	41996 KB	Output is correct
4	Correct	326 ms	23628 KB	Output is correct
5	Correct	468 ms	86200 KB	Output is correct
6	Correct	453 ms	86124 KB	Output is correct
7	Correct	451 ms	86144 KB	Output is correct
8	Correct	485 ms	86184 KB	Output is correct
9	Correct	418 ms	86148 KB	Output is correct
10	Correct	431 ms	86144 KB	Output is correct
11	Correct	419 ms	86180 KB	Output is correct
12	Correct	449 ms	86136 KB	Output is correct