oj.uz

Submission #523887

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

template <class S, S (*op)(S, S), S I() > 
class segment {
 public : 
    explicit segment(vector<int> &a) : n(int(a.size())) {
        log = 1;
        while((1<<log) < n)++log;
        size = 1<<log;
        d.resize(2*size, I());
        for(int i=0; i<n; i++)d[i + size] = a[i];
        for(int i=size - 1; i > 0; i--)update(i);
    }

    void set(int k, S v){
        assert(0 <= k && k < n);
        k += size;
        d[k] = v;
        for(int i = 1; i <= log; i++)update(k>>i);
    }

    S get(int k){
        assert(0 <= k && k < n);
        k += size;
        return d[k];
    }

    S get(int l, int r){
        assert(0 <= l && l <= r && r <= n);
        if(l == r) return I();
        l += size;
        r += size;

        
        S sml = I(), smr = I();
        while(l < r){
            if(l&1)sml = op(sml, d[l++]);
            if(r&1)smr = op(d[--r], smr);

            l >>= 1;
            r >>= 1;
        }
        
        return op(sml, smr);
    }
 private :
    int n, log, size;
    vector<S> d;

    void update(int p){
        d[p] = op(d[2*p], d[2*p + 1]);
    }
};


ll op(ll a, ll b){
    return (a + b);
}

ll I(){
    return 0;
}

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

    int n, q, k;
    cin >> n >> q >> k;

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

    segment<ll, op, I> 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;
        --l;
        if(t == 1){
            d.set(l, r);
            if(r > 0)b.insert(l);
        }else if(t == 2){
            if(k == 1)continue;
            vector<int> tem ;
            for(auto it = lower_bound(b.begin(), b.end(), l); it != b.end() && (*it) < r; it++){
                int x = *it;
                d.set(x, d.get(x)/k);
                if(d.get(x) == 0)tem.push_back(x);
            }
            for(int &c : tem)b.erase(c);
        }else {
            cout << d.get(l, r) << '\n';
        }
        // for(int i = 0; i < n; i++)cout << d.get(i) << ' ';
        // cout << '\n';
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 332 KB Output is correct
5 Correct 8 ms 460 KB Output is correct
6 Correct 6 ms 528 KB Output is correct
7 Correct 7 ms 460 KB Output is correct
8 Correct 10 ms 520 KB Output is correct
9 Correct 10 ms 536 KB Output is correct
10 Correct 9 ms 460 KB Output is correct
11 Correct 7 ms 460 KB Output is correct
12 Correct 10 ms 460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 4212 KB Output is correct
2 Correct 39 ms 3420 KB Output is correct
3 Correct 46 ms 6508 KB Output is correct
4 Correct 69 ms 7756 KB Output is correct
5 Correct 87 ms 7920 KB Output is correct
6 Correct 74 ms 7900 KB Output is correct
7 Correct 68 ms 7840 KB Output is correct
8 Correct 70 ms 7880 KB Output is correct
9 Correct 69 ms 7836 KB Output is correct
10 Correct 101 ms 7852 KB Output is correct
11 Correct 67 ms 7832 KB Output is correct
12 Correct 65 ms 7912 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 27 ms 3688 KB Output is correct
3 Correct 30 ms 3756 KB Output is correct
4 Correct 55 ms 2188 KB Output is correct
5 Correct 110 ms 7584 KB Output is correct
6 Correct 91 ms 7596 KB Output is correct
7 Correct 70 ms 7596 KB Output is correct
8 Correct 87 ms 7572 KB Output is correct
9 Correct 67 ms 8000 KB Output is correct
10 Correct 68 ms 8028 KB Output is correct
11 Correct 73 ms 7976 KB Output is correct
12 Correct 66 ms 8092 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 4124 KB Output is correct
2 Correct 153 ms 4124 KB Output is correct
3 Correct 317 ms 3740 KB Output is correct
4 Correct 200 ms 2732 KB Output is correct
5 Correct 305 ms 7772 KB Output is correct
6 Correct 339 ms 7756 KB Output is correct
7 Correct 255 ms 7704 KB Output is correct
8 Correct 477 ms 7760 KB Output is correct
9 Correct 173 ms 8052 KB Output is correct
10 Correct 214 ms 7884 KB Output is correct
11 Correct 153 ms 8120 KB Output is correct
12 Correct 397 ms 7860 KB Output is correct