oj.uz

Submission #482965

# Submission time Handle Problem Language Result Execution time Memory
482965 2021-10-27T05:52:59 Z K4YAN Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1189 ms 115536 KB 
//Be Name Khoda

#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("avx2")

using namespace std;

#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define piii pair<pii, int>
#define piiii pair<pii, pii>
#define piiiii pair<pii, piii>
#define pll pair<ll, ll>
#define plll pair<pll, ll>

const ll mxn = 1e5 + 16;
ll n, k, m, q, w;
ll fw[mxn];
vector<int> res, g;
unordered_set<int> s[3 * mxn];

struct segtree {

    int sz = 1;
    vector<ll> v;
    void init(ll n) {
        while(sz < n) sz <<= 1;
        v.assign(2 * sz, 0);
    }
    void add(int i, ll k, int x, int lx, int rx) {
        if(k > 0) {
            s[x].insert(i);
        }
        if(rx - lx == 1) {
            v[x] = k;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) add(i, k, 2 * x + 1, lx, m);
        else add(i, k, 2 * x + 2, m, rx);
        v[x] = v[2 * x + 1] + v[2 * x + 2];
    }
    void add(int i, ll k) {
        add(i, k, 0, 0, sz);
    }
    void edit(int i, ll k, int x, int lx, int rx) {
        if(rx - lx == 1) {
            v[x] /= k;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) edit(i, k, 2 * x + 1, lx, m);
        else edit(i, k, 2 * x + 2, m, rx);
        v[x] = v[2 * x + 1] + v[2 * x + 2];
    }
    void edit(int i, ll k) {
        edit(i, k, 0, 0, sz);
    }
    void rem(int i, int x, int lx, int rx) {
        s[x].erase(i);
        if(rx - lx == 1) {
            v[x] = 0;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) rem(i, 2 * x + 1, lx, m);
        else rem(i, 2 * x + 2, m, rx);
        v[x] = v[2 * x + 1] + v[2 * x + 2];
    }
    void rem(int i) {
        rem(i, 0, 0, sz);
    }
    void cal(int l, int r, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return;
        if(l <= lx && rx <= r) {
            for(auto it : s[x]) {
                res.push_back(it);
            }
            return;
        }
        int m = (lx + rx) >> 1;
        cal(l, r, 2 * x + 1, lx, m);
        cal(l, r, 2 * x + 2, m, rx);
    }
    void cal(int l, int r) {
        cal(l, r, 0, 0, sz);
    }
    ll ask(int l, int r, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return 0;
        if(l <= lx && rx <= r) {
            return v[x];
        }
        int m = (lx + rx) >> 1;
        ll a1 = ask(l, r, 2 * x + 1, lx, m);
        ll a2 = ask(l, r, 2 * x + 2, m, rx);
        return a1 + a2;
    }
    ll ask(int l, int r) {
        return ask(l, r, 0, 0, sz);
    } 

};
segtree st;

void input() {

    cin >> n >> q >> m;
    for(int i = 0; i < n; i++) {
        cin >> w;
        g.push_back(w);
    }

}

void solve() {

    st.init(n);
    for(int i = 0; i < n; i++) {
        st.add(i, g[i]);
    }
    if(m == 1) {
        for(int i = 0; i < q; i++) {
            int si;
            cin >> si;
            if(si == 2) {
                cin >> si >> si;
            }
            if(si == 1) {
                ll a, b;
                cin >> a >> b;
                a--; g[a] = b;
                st.add(a, b);
            }
            if(si == 3) {
                int l, r;
                cin >> l >> r;
                l--;
                cout << st.ask(l, r) << "\n";
            }
        }
        return;
    }
    for(int i = 0; i < q; i++) {
        int si;
        cin >> si;
        if(si == 1) {
            ll a, b;
            cin >> a >> b;
            a--; g[a] = b;
            st.rem(a);
            st.add(a, b);
        }
        if(si == 2) {
            int l, r;
            cin >> l >> r;
            l--; res.clear();
            st.cal(l, r);
            for(auto it : res) {
                if(g[it] >= m) {
                    g[it] /= m;
                    st.edit(it, m);
                }
                else {
                    g[it] = 0;
                    st.rem(it);
                }
            }
        }
        if(si == 3) {
            int l, r;
            cin >> l >> r;
            l--;
            cout << st.ask(l, r) << "\n";
        }
    }

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;

}
/*
5 10 1
1
2
8
1
3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16844 KB Output is correct
2 Correct 11 ms 17288 KB Output is correct
3 Correct 14 ms 17996 KB Output is correct
4 Correct 19 ms 17740 KB Output is correct
5 Correct 23 ms 19104 KB Output is correct
6 Correct 21 ms 19092 KB Output is correct
7 Correct 25 ms 19104 KB Output is correct
8 Correct 25 ms 19100 KB Output is correct
9 Correct 29 ms 19076 KB Output is correct
10 Correct 22 ms 19020 KB Output is correct
11 Correct 22 ms 19100 KB Output is correct
12 Correct 24 ms 19220 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 63384 KB Output is correct
2 Correct 234 ms 49352 KB Output is correct
3 Correct 495 ms 92392 KB Output is correct
4 Correct 648 ms 113204 KB Output is correct
5 Correct 672 ms 114772 KB Output is correct
6 Correct 664 ms 114764 KB Output is correct
7 Correct 666 ms 114804 KB Output is correct
8 Correct 674 ms 114804 KB Output is correct
9 Correct 672 ms 114704 KB Output is correct
10 Correct 668 ms 114576 KB Output is correct
11 Correct 661 ms 114612 KB Output is correct
12 Correct 662 ms 114708 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 20092 KB Output is correct
2 Correct 137 ms 39680 KB Output is correct
3 Correct 143 ms 39956 KB Output is correct
4 Correct 142 ms 29764 KB Output is correct
5 Correct 400 ms 70356 KB Output is correct
6 Correct 386 ms 70400 KB Output is correct
7 Correct 465 ms 77688 KB Output is correct
8 Correct 394 ms 70388 KB Output is correct
9 Correct 406 ms 70520 KB Output is correct
10 Correct 407 ms 70388 KB Output is correct
11 Correct 418 ms 70456 KB Output is correct
12 Correct 400 ms 70484 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 65404 KB Output is correct
2 Correct 385 ms 66268 KB Output is correct
3 Correct 469 ms 59572 KB Output is correct
4 Correct 322 ms 46532 KB Output is correct
5 Correct 739 ms 115220 KB Output is correct
6 Correct 803 ms 115052 KB Output is correct
7 Correct 706 ms 115372 KB Output is correct
8 Correct 973 ms 115536 KB Output is correct
9 Correct 845 ms 115472 KB Output is correct
10 Correct 957 ms 115464 KB Output is correct
11 Correct 762 ms 115348 KB Output is correct
12 Correct 1189 ms 115348 KB Output is correct