oj.uz

답안 #825610

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

  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 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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