oj.uz

Submission #523886

# Submission time Handle Problem Language Result Execution time Memory
523886 2022-02-08T11:16:03 Z IMystic Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 441 ms 9444 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;



template <typename T>
class fenwick {
public : 
    int n;
    vector<T> fen;
    explicit fenwick(vector<T> &a) : n(int(a.size())) {
        fen.resize(n);
        for(int i=0; i<n; i++)modify(i, a[i]);
    }

    T get(int p){
        T v = 0;
        while(p >= 0){
            v += fen[p];
            p = (p & ( p + 1)) - 1;
        }
        return v;
    }

    T get(int l, int r){
        return (get(r) - get(l - 1));
    }

    void modify(int p, T v){
        assert(0 <= p && p < n);
        while(p < n){
            fen[p] += v;
            p |= (p + 1);
        }
    }
};


int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q, k;
    cin >> n >> q >> k;
    vector<ll> a(n);
    for(int i=0; i<n; i++)cin >> a[i];

    fenwick<ll> d(a);
    set<int> b;
    for(int i=0; i<n; i++)b.insert(i);

    for(int i=0; i<q; i++){
        int t, l, r;
        cin >> t >>  l >> r;
        if(t == 1){
            d.modify(l - 1, r - a[l - 1]);
            a[l - 1] = r;
            if(r > 0)b.insert(l - 1);
        }
        else if(t == 2){ 
            if(k == 1)continue;
            vector<int> tem ;
            for(auto it = lower_bound(b.begin(), b.end(), l - 1); it != b.end() && (*it) < r; it++){
                int x = *it;
                if(a[x] == 0){
                    tem.push_back(x);
                    continue;
                }
                
                d.modify(x, (a[x]/k) - a[x]);
                a[x] = a[x]/k;
                if(a[x] == 0)tem.push_back(x);
            }
            for(int &c : tem)b.erase(c);
        }else{
            cout << d.get(l - 1, r - 1) << '\n';
        }

        // for(int i=0; i<n; i++)cout << d.get(i, i) << ' ';
        // cout << '\n';
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 396 KB Output is correct
5 Correct 8 ms 460 KB Output is correct
6 Correct 6 ms 500 KB Output is correct
7 Correct 7 ms 460 KB Output is correct
8 Correct 9 ms 460 KB Output is correct
9 Correct 11 ms 588 KB Output is correct
10 Correct 6 ms 588 KB Output is correct
11 Correct 7 ms 460 KB Output is correct
12 Correct 7 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4684 KB Output is correct
2 Correct 37 ms 4344 KB Output is correct
3 Correct 54 ms 7052 KB Output is correct
4 Correct 61 ms 8888 KB Output is correct
5 Correct 77 ms 9392 KB Output is correct
6 Correct 67 ms 9412 KB Output is correct
7 Correct 85 ms 9444 KB Output is correct
8 Correct 71 ms 9412 KB Output is correct
9 Correct 77 ms 9348 KB Output is correct
10 Correct 69 ms 9284 KB Output is correct
11 Correct 71 ms 9312 KB Output is correct
12 Correct 72 ms 9392 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 716 KB Output is correct
2 Correct 29 ms 3144 KB Output is correct
3 Correct 32 ms 3248 KB Output is correct
4 Correct 56 ms 1960 KB Output is correct
5 Correct 86 ms 6732 KB Output is correct
6 Correct 82 ms 6684 KB Output is correct
7 Correct 59 ms 7548 KB Output is correct
8 Correct 88 ms 8132 KB Output is correct
9 Correct 64 ms 8016 KB Output is correct
10 Correct 62 ms 7980 KB Output is correct
11 Correct 60 ms 7980 KB Output is correct
12 Correct 64 ms 8104 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 3636 KB Output is correct
2 Correct 139 ms 3712 KB Output is correct
3 Correct 299 ms 3264 KB Output is correct
4 Correct 168 ms 2484 KB Output is correct
5 Correct 260 ms 6860 KB Output is correct
6 Correct 336 ms 6852 KB Output is correct
7 Correct 220 ms 6828 KB Output is correct
8 Correct 441 ms 7020 KB Output is correct
9 Correct 168 ms 7156 KB Output is correct
10 Correct 150 ms 7028 KB Output is correct
11 Correct 118 ms 7164 KB Output is correct
12 Correct 231 ms 6948 KB Output is correct