oj.uz

답안 #825601

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

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 S = int_baseK;
struct F { int c; };
S op(S x, S y) {
    // int carry = 0;
    S 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;
}
S e() { return int_baseK{}; }
S mapping(F f, S x) { 
    S res{};
    for (int i = 0; i + f.c < BASE_LENGTH; i++)
        res[i] = x[i + f.c];
    return res;
}
F composition(F f, F g) { return F{f.c + g.c}; }
F id() { return F{0}; }

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q; cin >> n >> q >> K;
    vector<S> c(n);
    for (auto &it : c) {
        int64_t x; cin >> x;
        it = to_baseK(x);
    }
    // for (int i = 0; i < n; i++) cout << to_ll(c[i]) << ' ';
    // cout << '\n';
    lazy_segtree<S, op, e, F, mapping, composition, id> segtree(c);
    while (q--) {
        int s, t, u; cin >> s >> t >> u; --t;
        if (s == 1) {
            segtree.set(t, to_baseK(u));
        } else if (s == 2) {
            segtree.apply(t, u, F{1});
        } else {
            // cout << to_ll(segtree.prod(3, 4)) << '\n';
            cout << to_ll(segtree.prod(t, u)) << '\n';
        }
        // for (int i = 0; i < n; i++) cout << to_ll(segtree.get(i)) << ' ';
        // cout << '\n';
    }
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 340 KB Output is correct
2 Runtime error 1 ms 852 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 23636 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 6160 KB Output is correct
2 Correct 78 ms 42236 KB Output is correct
3 Correct 107 ms 42292 KB Output is correct
4 Correct 294 ms 22756 KB Output is correct
5 Correct 459 ms 87300 KB Output is correct
6 Correct 452 ms 87372 KB Output is correct
7 Runtime error 27 ms 48084 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 45108 KB Output is correct
2 Correct 321 ms 45468 KB Output is correct
3 Correct 198 ms 43196 KB Output is correct
4 Correct 327 ms 25332 KB Output is correct
5 Correct 443 ms 88508 KB Output is correct
6 Correct 446 ms 88552 KB Output is correct
7 Correct 443 ms 88512 KB Output is correct
8 Correct 457 ms 88752 KB Output is correct
9 Correct 407 ms 88480 KB Output is correct
10 Correct 412 ms 88512 KB Output is correct
11 Correct 416 ms 88432 KB Output is correct
12 Correct 415 ms 88512 KB Output is correct