oj.uz

Submission #708537

# Submission time Handle Problem Language Result Execution time Memory
708537 2023-03-12T03:07:53 Z joelgun14 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 728 ms 72032 KB 
// header file
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// pragma
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// macros
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int lim = 1 << 17;
int k;
struct segment_tree {
    ll occur_drop[2 * lim][32], a[2 * lim];
    int occur_prop[2 * lim];

    segment_tree() {
        memset(a, 0, sizeof(a));
        memset(occur_drop, 0, sizeof(occur_drop));
        memset(occur_prop, 0, sizeof(occur_prop));
    }
    void propagate(int nd, int cl, int cr) {
        if(cl != cr) {
            occur_prop[2 * nd] += occur_prop[nd];
            occur_prop[2 * nd + 1] += occur_prop[nd];
        }
        //cout << occur_prop[nd] << " " << a[nd] << endl;
        if(occur_prop[nd]) {
            for(int i = 0; i < min(32, occur_prop[nd]); ++i) {
                //cout << occur_drop[nd][i];
                a[nd] -= occur_drop[nd][i];
                occur_drop[nd][i] = 0;
            }
            //cout << cl << " " << cr << " " << a[nd] << endl;
            for(int i = occur_prop[nd]; i < 32; ++i) {
                occur_drop[nd][i - occur_prop[nd]] = occur_drop[nd][i], occur_drop[nd][i] = 0;
            }
            occur_prop[nd] = 0;
        }
    }
    void upd(int nd, int cl, int cr, int idx, int val) {
        propagate(nd, cl, cr);
        // tambahkan occur_drop
        int tmp = val, cur = 0;
        a[nd] += val;
        while(tmp && k != 1) {
            int tmp2 = tmp / k;
            occur_drop[nd][cur++] += tmp - tmp2;
            tmp = tmp2;
        }
        //cout << cl << " " << cr << " " << a[nd] << endl;
        if(cl != cr) {
            int mid = (cl + cr) >> 1;
            if(idx <= mid)
                upd(2 * nd, cl, mid, idx, val);
            else
                upd(2 * nd + 1, mid + 1, cr, idx, val);
        }
    }
    void erase(int nd, int cl, int cr, int idx, int val) {
        propagate(nd, cl, cr);
        // tambahkan occur_drop
        int tmp = val, cur = 0;
        a[nd] -= val;
        while(tmp && k != 1) {
            int tmp2 = tmp / k;
            occur_drop[nd][cur++] -= tmp - tmp2;
            tmp = tmp2;
        }
        //cout << cl << " " << cr << " " << a[nd] << endl;
        if(cl != cr) {
            int mid = (cl + cr) >> 1;
            if(idx <= mid)
                erase(2 * nd, cl, mid, idx, val);
            else
                erase(2 * nd + 1, mid + 1, cr, idx, val);
        }
    }
    ll query(int nd, int cl, int cr, int l, int r) {
        propagate(nd, cl, cr);
        //cout << cl << " " << cr << " " << a[nd] << endl;
        if(cl >= l && cr <= r) {
            return a[nd];
        }
        else if(cl > r || cr < l)
            return 0;
        else {
            int mid = (cl + cr) >> 1;
            return query(2 * nd, cl, mid, l, r) + query(2 * nd + 1, mid + 1, cr, l, r);
        }
    }
    void spray(int nd, int cl, int cr, int l, int r) {
        propagate(nd, cl, cr);
        if(cl >= l && cr <= r) {
            ++occur_prop[nd];
            propagate(nd, cl, cr);
        }
        else if(cl > r || cr < l)
            return;
        else {
            int mid = (cl + cr) >> 1;
            spray(2 * nd, cl, mid, l, r);
            spray(2 * nd + 1, mid + 1, cr, l, r);
            for(int i = 0; i < 32; ++i)
                occur_drop[nd][i] = occur_drop[2 * nd][i] + occur_drop[2 * nd + 1][i];
            a[nd] = a[2 * nd] + a[2 * nd + 1];
        }
    }
};
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    // each node maintains array of occur
    // at most 30/31
    int n, q;
    cin >> n >> q >> k;
    segment_tree seg;
    for(int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        seg.upd(1, 0, lim - 1, i, x);
    }
    for(;q--;) {
        int s, t, u;
        cin >> s >> t >> u;
        if(s == 1) {
            seg.erase(1, 0, lim - 1, t, seg.query(1, 0, lim - 1, t, t));
            seg.upd(1, 0, lim - 1, t, u);
        }
        else if(s == 2) {
            //cout << "SPRAY" << endl;
            seg.spray(1, 0, lim - 1, t, u);
            //cout << "SPRAYEND" << endl;
        }
        else {
            cout << seg.query(1, 0, lim - 1, t, u) << endl;
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 69076 KB Output is correct
2 Correct 37 ms 68964 KB Output is correct
3 Correct 39 ms 69052 KB Output is correct
4 Correct 51 ms 69096 KB Output is correct
5 Correct 49 ms 69116 KB Output is correct
6 Correct 44 ms 69036 KB Output is correct
7 Correct 47 ms 69048 KB Output is correct
8 Correct 45 ms 69072 KB Output is correct
9 Correct 48 ms 69072 KB Output is correct
10 Correct 46 ms 69068 KB Output is correct
11 Correct 49 ms 69104 KB Output is correct
12 Correct 44 ms 69088 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 71376 KB Output is correct
2 Correct 284 ms 71060 KB Output is correct
3 Correct 266 ms 70908 KB Output is correct
4 Correct 315 ms 71560 KB Output is correct
5 Correct 382 ms 71876 KB Output is correct
6 Correct 390 ms 71976 KB Output is correct
7 Correct 383 ms 72024 KB Output is correct
8 Correct 401 ms 72032 KB Output is correct
9 Correct 257 ms 71820 KB Output is correct
10 Correct 255 ms 71840 KB Output is correct
11 Correct 274 ms 71756 KB Output is correct
12 Correct 263 ms 71736 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 69536 KB Output is correct
2 Correct 92 ms 69308 KB Output is correct
3 Correct 118 ms 69416 KB Output is correct
4 Correct 284 ms 70208 KB Output is correct
5 Correct 427 ms 70436 KB Output is correct
6 Correct 379 ms 70456 KB Output is correct
7 Correct 377 ms 70692 KB Output is correct
8 Correct 390 ms 70592 KB Output is correct
9 Correct 248 ms 70356 KB Output is correct
10 Correct 293 ms 70436 KB Output is correct
11 Correct 300 ms 70544 KB Output is correct
12 Correct 256 ms 70384 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 70840 KB Output is correct
2 Correct 335 ms 70940 KB Output is correct
3 Correct 404 ms 70312 KB Output is correct
4 Correct 405 ms 71080 KB Output is correct
5 Correct 527 ms 71840 KB Output is correct
6 Correct 565 ms 71712 KB Output is correct
7 Correct 528 ms 71760 KB Output is correct
8 Correct 674 ms 71908 KB Output is correct
9 Correct 514 ms 71664 KB Output is correct
10 Correct 546 ms 71712 KB Output is correct
11 Correct 432 ms 71644 KB Output is correct
12 Correct 728 ms 71628 KB Output is correct