oj.uz

Submission #683668

# Submission time Handle Problem Language Result Execution time Memory
683668 2023-01-19T05:14:32 Z vjudge1 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 781 ms 71764 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 35 ms 69068 KB Output is correct
3 Correct 38 ms 69044 KB Output is correct
4 Correct 47 ms 69092 KB Output is correct
5 Correct 46 ms 69088 KB Output is correct
6 Correct 49 ms 69100 KB Output is correct
7 Correct 47 ms 69116 KB Output is correct
8 Correct 46 ms 69108 KB Output is correct
9 Correct 48 ms 69056 KB Output is correct
10 Correct 45 ms 69076 KB Output is correct
11 Correct 44 ms 69040 KB Output is correct
12 Correct 45 ms 69040 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 69764 KB Output is correct
2 Correct 310 ms 69752 KB Output is correct
3 Correct 245 ms 69660 KB Output is correct
4 Correct 346 ms 69860 KB Output is correct
5 Correct 429 ms 69996 KB Output is correct
6 Correct 472 ms 69804 KB Output is correct
7 Correct 395 ms 69872 KB Output is correct
8 Correct 396 ms 69900 KB Output is correct
9 Correct 293 ms 69844 KB Output is correct
10 Correct 325 ms 69824 KB Output is correct
11 Correct 292 ms 69892 KB Output is correct
12 Correct 293 ms 69844 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 69272 KB Output is correct
2 Correct 98 ms 69324 KB Output is correct
3 Correct 144 ms 69476 KB Output is correct
4 Correct 288 ms 69744 KB Output is correct
5 Correct 379 ms 69748 KB Output is correct
6 Correct 416 ms 69808 KB Output is correct
7 Correct 433 ms 69904 KB Output is correct
8 Correct 410 ms 70052 KB Output is correct
9 Correct 274 ms 70228 KB Output is correct
10 Correct 303 ms 70420 KB Output is correct
11 Correct 269 ms 70348 KB Output is correct
12 Correct 272 ms 70276 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 70604 KB Output is correct
2 Correct 353 ms 70928 KB Output is correct
3 Correct 430 ms 70320 KB Output is correct
4 Correct 419 ms 71096 KB Output is correct
5 Correct 566 ms 71764 KB Output is correct
6 Correct 621 ms 71748 KB Output is correct
7 Correct 552 ms 71652 KB Output is correct
8 Correct 716 ms 71680 KB Output is correct
9 Correct 533 ms 71584 KB Output is correct
10 Correct 612 ms 71652 KB Output is correct
11 Correct 442 ms 71540 KB Output is correct
12 Correct 781 ms 71628 KB Output is correct