oj.uz

Submission #752306

# Submission time Handle Problem Language Result Execution time Memory
752306 2023-06-02T17:15:43 Z GrindMachine Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 1280 ms 10644 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){
            if(k == 1) conts;

            ll l,r; cin >> l >> r;
            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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 6708 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1104 KB Output is correct
2 Correct 14 ms 3176 KB Output is correct
3 Correct 17 ms 3332 KB Output is correct
4 Correct 44 ms 2960 KB Output is correct
5 Correct 57 ms 7468 KB Output is correct
6 Correct 56 ms 7328 KB Output is correct
7 Incorrect 32 ms 7380 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 5768 KB Output is correct
2 Correct 213 ms 5536 KB Output is correct
3 Correct 469 ms 4988 KB Output is correct
4 Correct 285 ms 4564 KB Output is correct
5 Correct 430 ms 9464 KB Output is correct
6 Correct 509 ms 9428 KB Output is correct
7 Correct 370 ms 10504 KB Output is correct
8 Correct 772 ms 10408 KB Output is correct
9 Correct 669 ms 10644 KB Output is correct
10 Correct 827 ms 10600 KB Output is correct
11 Correct 515 ms 10532 KB Output is correct
12 Correct 1280 ms 10616 KB Output is correct