답안 #825606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825606	2023-08-15T06:16:58 Z	Koyote	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	492 ms	86192 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);
        }
    }

    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++]);
                }
                return l - size;
            }
            sm = op(sm, d[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);
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  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

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	340 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	1620 KB	Output is correct
5	Correct	9 ms	2900 KB	Output is correct
6	Correct	9 ms	2988 KB	Output is correct
7	Correct	9 ms	2980 KB	Output is correct
8	Correct	9 ms	2984 KB	Output is correct
9	Correct	9 ms	2900 KB	Output is correct
10	Correct	9 ms	2992 KB	Output is correct
11	Correct	9 ms	2980 KB	Output is correct
12	Correct	9 ms	2900 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	2160 KB	Output is correct
2	Correct	26 ms	1936 KB	Output is correct
3	Correct	23 ms	3264 KB	Output is correct
4	Correct	28 ms	3540 KB	Output is correct
5	Correct	32 ms	3636 KB	Output is correct
6	Correct	33 ms	3544 KB	Output is correct
7	Correct	34 ms	3620 KB	Output is correct
8	Correct	33 ms	3552 KB	Output is correct
9	Correct	31 ms	3624 KB	Output is correct
10	Correct	32 ms	3644 KB	Output is correct
11	Correct	32 ms	3672 KB	Output is correct
12	Correct	31 ms	3564 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	106 ms	5732 KB	Output is correct
2	Correct	75 ms	41868 KB	Output is correct
3	Correct	105 ms	41812 KB	Output is correct
4	Correct	320 ms	21668 KB	Output is correct
5	Correct	447 ms	85892 KB	Output is correct
6	Correct	437 ms	85936 KB	Output is correct
7	Correct	28 ms	3248 KB	Output is correct
8	Correct	471 ms	85944 KB	Output is correct
9	Correct	417 ms	85896 KB	Output is correct
10	Correct	409 ms	85872 KB	Output is correct
11	Correct	418 ms	86052 KB	Output is correct
12	Correct	424 ms	86020 KB	Output is correct

Subtask #4

75.0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	272 ms	43576 KB	Output is correct
2	Correct	325 ms	43888 KB	Output is correct
3	Correct	219 ms	42040 KB	Output is correct
4	Correct	313 ms	23632 KB	Output is correct
5	Correct	474 ms	86132 KB	Output is correct
6	Correct	456 ms	86168 KB	Output is correct
7	Correct	476 ms	86148 KB	Output is correct
8	Correct	492 ms	86136 KB	Output is correct
9	Correct	422 ms	86192 KB	Output is correct
10	Correct	426 ms	86092 KB	Output is correct
11	Correct	478 ms	86080 KB	Output is correct
12	Correct	461 ms	86152 KB	Output is correct