oj.uz

Submission #523863

# Submission time Handle Problem Language Result Execution time Memory
523863 2022-02-08T10:06:47 Z IMystic Sterilizing Spray (JOI15_sterilizing) C++17
0 / 100
 5000 ms 7868 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]);
    }
};
 
 
int op(int a, int b){
    return (a + b);
}
 
int 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<int, 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);
            b.insert(l);
        }else if(t == 2){
            while(true){
                auto it = b.lower_bound(l);
                if(it == b.end() || *it >= r)break;
                int tem = d.get(*it)/k;
                d.set(*it, tem);
                l = *it + 1;
                if(tem == 0)b.erase(it);
            }
        }else {
            cout << d.get(l, r) << '\n';
        }
    }
 
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5019 ms 4328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1084 KB Output is correct
2 Correct 20 ms 3388 KB Output is correct
3 Correct 23 ms 3468 KB Output is correct
4 Correct 42 ms 3008 KB Output is correct
5 Correct 68 ms 7868 KB Output is correct
6 Correct 69 ms 7860 KB Output is correct
7 Execution timed out 5064 ms 7196 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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