답안 #825606

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