oj.uz

답안 #683654

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683654 2023-01-19T04:59:47 Z vjudge1 Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 434 ms 71916 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;
        for(int i = 0; i < min(32, occur_prop[nd]); ++i) {
            a[nd] -= occur_drop[nd][i];
        }
        //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_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) {
            seg.spray(1, 0, lim - 1, t, u);
        }
        else {
            cout << seg.query(1, 0, lim - 1, t, u) << endl;
        }
    }
    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 68936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 353 ms 71352 KB Output is correct
2 Correct 312 ms 71012 KB Output is correct
3 Correct 265 ms 71000 KB Output is correct
4 Correct 322 ms 71464 KB Output is correct
5 Correct 415 ms 71884 KB Output is correct
6 Correct 393 ms 71916 KB Output is correct
7 Correct 434 ms 71872 KB Output is correct
8 Correct 426 ms 71884 KB Output is correct
9 Correct 375 ms 71880 KB Output is correct
10 Correct 315 ms 71916 KB Output is correct
11 Correct 335 ms 71836 KB Output is correct
12 Correct 361 ms 71836 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 122 ms 69052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 355 ms 69508 KB Output isn't correct
2 Halted 0 ms 0 KB -