oj.uz

Submission #482969

# Submission time Handle Problem Language Result Execution time Memory
482969 2021-10-27T06:02:30 Z K4YAN Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1112 ms 102356 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;
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) {
                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 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14412 KB Output is correct
2 Correct 9 ms 14796 KB Output is correct
3 Correct 13 ms 15436 KB Output is correct
4 Correct 17 ms 15208 KB Output is correct
5 Correct 22 ms 16348 KB Output is correct
6 Correct 20 ms 16332 KB Output is correct
7 Correct 23 ms 16332 KB Output is correct
8 Correct 22 ms 16348 KB Output is correct
9 Correct 24 ms 16352 KB Output is correct
10 Correct 21 ms 16344 KB Output is correct
11 Correct 22 ms 16228 KB Output is correct
12 Correct 24 ms 16348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 54828 KB Output is correct
2 Correct 188 ms 42564 KB Output is correct
3 Correct 326 ms 82312 KB Output is correct
4 Correct 433 ms 100596 KB Output is correct
5 Correct 472 ms 101820 KB Output is correct
6 Correct 472 ms 101836 KB Output is correct
7 Correct 467 ms 101828 KB Output is correct
8 Correct 461 ms 101876 KB Output is correct
9 Correct 442 ms 101816 KB Output is correct
10 Correct 475 ms 101832 KB Output is correct
11 Correct 463 ms 101828 KB Output is correct
12 Correct 449 ms 101856 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16684 KB Output is correct
2 Correct 99 ms 33444 KB Output is correct
3 Correct 104 ms 33608 KB Output is correct
4 Correct 121 ms 24172 KB Output is correct
5 Correct 284 ms 59184 KB Output is correct
6 Correct 299 ms 59388 KB Output is correct
7 Correct 340 ms 65636 KB Output is correct
8 Correct 307 ms 59212 KB Output is correct
9 Correct 266 ms 59552 KB Output is correct
10 Correct 271 ms 59448 KB Output is correct
11 Correct 267 ms 59456 KB Output is correct
12 Correct 263 ms 59476 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 57032 KB Output is correct
2 Correct 357 ms 57636 KB Output is correct
3 Correct 443 ms 51968 KB Output is correct
4 Correct 327 ms 39620 KB Output is correct
5 Correct 709 ms 102236 KB Output is correct
6 Correct 768 ms 102356 KB Output is correct
7 Correct 645 ms 102112 KB Output is correct
8 Correct 879 ms 102284 KB Output is correct
9 Correct 753 ms 102208 KB Output is correct
10 Correct 828 ms 102176 KB Output is correct
11 Correct 691 ms 102208 KB Output is correct
12 Correct 1112 ms 102156 KB Output is correct