oj.uz

Submission #482968

# Submission time Handle Problem Language Result Execution time Memory
482968 2021-10-27T06:01:10 Z K4YAN Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 1127 ms 102332 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;
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) continue;
            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 3
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
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 202 ms 54708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16716 KB Output is correct
2 Correct 97 ms 33412 KB Output is correct
3 Correct 106 ms 33676 KB Output is correct
4 Correct 127 ms 24208 KB Output is correct
5 Correct 285 ms 59148 KB Output is correct
6 Correct 292 ms 59328 KB Output is correct
7 Incorrect 284 ms 63236 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 340 ms 57028 KB Output is correct
2 Correct 365 ms 57816 KB Output is correct
3 Correct 449 ms 51896 KB Output is correct
4 Correct 353 ms 39596 KB Output is correct
5 Correct 731 ms 102096 KB Output is correct
6 Correct 762 ms 102212 KB Output is correct
7 Correct 645 ms 102332 KB Output is correct
8 Correct 869 ms 102140 KB Output is correct
9 Correct 768 ms 102212 KB Output is correct
10 Correct 902 ms 102212 KB Output is correct
11 Correct 705 ms 102212 KB Output is correct
12 Correct 1127 ms 102204 KB Output is correct