Submission #1192215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192215		baldwin_huang	Sterilizing Spray (JOI15_sterilizing)	C++20	10 / 100	722 ms	293680 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

int N, Q, K;
vector<int> C(131072 + 1);

template<typename val>
struct PetriDish {
    val c;
    int i;
    vector<val> ith_division = vector<val>(65);

    void build (val _c) {
        c = _c;
        i = 0;
        ith_division[0] = c / K;
        for (int j = 1; j < 65; j++) {
            ith_division[j] = ith_division[j - 1] / K;
        }
    }

    val divide(int count) {
        if (K == 1) {
            return c;
        }
        i = count;
        i--;
        if (64 < i) {
            return 0;
        }
        c = ith_division[i];
        return ith_division[i];
    }
};

PetriDish<int64_t> join(PetriDish<int64_t> i, PetriDish<int64_t> j) {
    int64_t c = i.c + j.c;
    vector<int64_t> ith_division(65);
    for (int x = i.i, y = j.i, k = 0; k < 65; k++) {
        ith_division[k] = i.divide(x + 1 + k) + j.divide(y + 1 + k);
    }
    PetriDish<int64_t> ans;
    ans.c = c;
    ans.i = 0;
    ans.ith_division = ith_division;
    return ans;
}

PetriDish<int64_t> ST[4 * (1 << 17) + 1];
bool lazy_flag[4 * (1 << 17) + 1];
int lazy_count[4 * (1 << 17) + 1];

void execute_lazy (int tree_index, int l, int r);
void set_lazy (int tree_index, int l, int r);

void build(int tree_index, int l, int r) {
    if (l == r) {
        ST[tree_index].build(C[l]);
        return;
    }
    int mid = (l + r) / 2;
    build(2 * tree_index, l, mid);
    build(2 * tree_index + 1, mid + 1, r);
    ST[tree_index] = join(ST[2 * tree_index], ST[2 * tree_index + 1]);
}

void execute_lazy (int tree_index, int l, int r) {
    if (lazy_flag[tree_index] == false) {
        return;
    }
    if (l == r) {
        return;
    }
    // cout << l << ' ' << r << '\n';
    int mid = (l + r) / 2;
    lazy_count[2 * tree_index] += lazy_count[tree_index];
    lazy_count[2 * tree_index + 1] += lazy_count[tree_index];
    lazy_count[tree_index] = 0;
    set_lazy(2 * tree_index, l, mid);
    set_lazy(2 * tree_index + 1, mid + 1, r);
    
    lazy_flag[tree_index] = false;
}

void set_lazy (int tree_index, int l, int r) {
    // cout << "Info: " << lazy_count[tree_index] << '\n';
    ST[tree_index].divide(lazy_count[tree_index]);
    if (l == r) {
        return;
    }
    lazy_flag[tree_index] = true;
}

void spray(int tree_index, int l, int r, int l_target, int r_target) {
    if (r < l_target || r_target < l) {
        return;
    }
    if (l_target <= l && r <= r_target) {
        lazy_count[tree_index]++;
        set_lazy(tree_index, l, r);
        // cout << "Lazy_count: " << ST[tree_index].c << ' ' << l << ' ' << r << '\n';
        return;
    }
    execute_lazy(tree_index, l, r);
    int mid = (l + r) / 2;
    spray(2 * tree_index, l, mid, l_target, r_target);
    spray(2 * tree_index + 1, mid + 1, r, l_target, r_target);
    ST[tree_index] = join(ST[2 * tree_index], ST[2 * tree_index + 1]);
}

void edit(int tree_index, int l, int r, int target, int payload) {
    if (l == target && r == target) {
        ST[tree_index].build(payload);
        lazy_count[tree_index] = 0;
        return;
    }
    if (r < target || target < l) {
        return;
    }
    execute_lazy(tree_index, l, r);
    int mid = (l + r) / 2;
    edit(2 * tree_index, l, mid, target, payload);
    edit(2 * tree_index + 1, mid + 1, r, target, payload);
    ST[tree_index] = ST[tree_index] = join(ST[2 * tree_index], ST[2 * tree_index + 1]);
}

int64_t query(int tree_index, int l, int r, int l_target, int r_target) {
    if (r < l_target || r_target < l) {
        return 0;
    }
    if (l_target <= l && r <= r_target) {
        // cout << "Range " << l << ' ' << r << ": " << ST[tree_index].c << '\n';
        return ST[tree_index].c;
    }
    execute_lazy(tree_index, l, r);
    int mid = (l + r) / 2;
    int64_t a = query(2 * tree_index, l, mid, l_target, r_target);
    int64_t b = query(2 * tree_index + 1, mid + 1, r, l_target, r_target);
    // cout << "Range " << l << ' ' << r << ": " << (a + b) << '\n';
    return a + b;
}



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> Q >> K;

    for (int i = 1; i <= N; i++) {
        cin >> C[i];
    }

    build(1, 1, 1<<17);

    while (Q--) {
        int S, T, U;
        cin >> S >> T >> U;
        // cout << S << ' ' << T << ' ' << U << '\n';
        if (S == 1) {
            edit(1, 1, 1<<17, T, U);
        }
        else if (S == 2) {
            spray(1, 1, 1<<17, T, U);
        }
        else if (S == 3) {
            // cout << '#' << 3 << '\n';
            cout << query(1, 1, 1<<17, T, U) << '\n';
        }
        // cout << "Operation " << S << ": ";
        // for (int i = 1; i <= N; i++) {
        //     cout << query(1, 1, 1<<17, i, i) << ' ';
        // }
        // cout << '\n';
    }

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75