oj.uz

Submission #752308

# Submission time Handle Problem Language Result Execution time Memory
752308 2023-06-02T17:18:03 Z GrindMachine Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1280 ms 9732 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        ll mx, ind, sum;
    };

    data neutral = {-inf2, -1, 0};

    data merge(data &left, data &right) {
        data curr;

        curr.mx = max(left.mx, right.mx);

        if(left.mx >= right.mx){
            curr.ind = left.ind;
        }
        else{
            curr.ind = right.ind;
        }

        curr.sum = left.sum + right.sum;

        return curr;
    }

    void create(int i, T v) {
        tr[i] = {v,i-n,v};
    }

    void modify(int i, T v) {
        tr[i] = {v,i-n,v};
    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    data query(int l, int r) {
        data resl = neutral, resr = neutral;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tr[l++]);
            if (!(r & 1)) resr = merge(tr[r--], resr);
        }

        return merge(resl, resr);
    }
};

void solve(int test_case)
{
    ll n,q,k; cin >> n >> q >> k;
    vector<ll> a(n+5);
    rep1(i,n) cin >> a[i];

    segtree<ll> st(n+5);
    st.build(a,n+1);

    while(q--){
        ll t; cin >> t;
        if(t == 1){
            ll i,v; cin >> i >> v;
            st.pupd(i,v);
        }
        else if(t == 2){
            ll l,r; cin >> l >> r;
            if(k == 1) conts;

            vector<pll> upd;
            
            while(true){
                auto [mx, ind, sum] = st.query(l,r);
                if(mx == 0) break;

                upd.pb({ind, mx/k});
                st.pupd(ind, 0);
            }

            for(auto [i,v] : upd){
                st.pupd(i,v);
            }
        }
        else{
            ll l,r; cin >> l >> r;
            ll ans = st.query(l,r).sum;
            cout << ans << endl;
        }
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 12 ms 468 KB Output is correct
5 Correct 12 ms 680 KB Output is correct
6 Correct 9 ms 596 KB Output is correct
7 Correct 11 ms 676 KB Output is correct
8 Correct 11 ms 592 KB Output is correct
9 Correct 15 ms 596 KB Output is correct
10 Correct 11 ms 596 KB Output is correct
11 Correct 11 ms 676 KB Output is correct
12 Correct 12 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4428 KB Output is correct
2 Correct 34 ms 4188 KB Output is correct
3 Correct 32 ms 6480 KB Output is correct
4 Correct 44 ms 8140 KB Output is correct
5 Correct 48 ms 8696 KB Output is correct
6 Correct 45 ms 8620 KB Output is correct
7 Correct 46 ms 8652 KB Output is correct
8 Correct 47 ms 8644 KB Output is correct
9 Correct 46 ms 8692 KB Output is correct
10 Correct 47 ms 8524 KB Output is correct
11 Correct 48 ms 8524 KB Output is correct
12 Correct 45 ms 8556 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 724 KB Output is correct
2 Correct 15 ms 2924 KB Output is correct
3 Correct 17 ms 2928 KB Output is correct
4 Correct 39 ms 1876 KB Output is correct
5 Correct 55 ms 6260 KB Output is correct
6 Correct 55 ms 6168 KB Output is correct
7 Correct 35 ms 5976 KB Output is correct
8 Correct 63 ms 7596 KB Output is correct
9 Correct 54 ms 7252 KB Output is correct
10 Correct 54 ms 7344 KB Output is correct
11 Correct 54 ms 7248 KB Output is correct
12 Correct 61 ms 7252 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 4284 KB Output is correct
2 Correct 214 ms 4100 KB Output is correct
3 Correct 437 ms 4416 KB Output is correct
4 Correct 267 ms 2900 KB Output is correct
5 Correct 387 ms 7840 KB Output is correct
6 Correct 491 ms 7832 KB Output is correct
7 Correct 363 ms 8944 KB Output is correct
8 Correct 713 ms 9216 KB Output is correct
9 Correct 646 ms 9560 KB Output is correct
10 Correct 800 ms 9732 KB Output is correct
11 Correct 485 ms 9412 KB Output is correct
12 Correct 1280 ms 9636 KB Output is correct