oj.uz

Submission #523865

# Submission time Handle Problem Language Result Execution time Memory
523865 2022-02-08T10:11:42 Z IMystic Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 10176 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);
            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';
        }
        // 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 1 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 5 ms 596 KB Output is correct
9 Correct 6 ms 580 KB Output is correct
10 Correct 8 ms 564 KB Output is correct
11 Correct 4 ms 580 KB Output is correct
12 Correct 6 ms 716 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1152 KB Output is correct
2 Correct 21 ms 3856 KB Output is correct
3 Correct 25 ms 4044 KB Output is correct
4 Correct 38 ms 3252 KB Output is correct
5 Correct 77 ms 8844 KB Output is correct
6 Correct 79 ms 8940 KB Output is correct
7 Execution timed out 5030 ms 8200 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 5604 KB Output is correct
2 Correct 86 ms 5836 KB Output is correct
3 Correct 180 ms 4884 KB Output is correct
4 Correct 91 ms 4312 KB Output is correct
5 Correct 168 ms 10164 KB Output is correct
6 Correct 215 ms 10132 KB Output is correct
7 Correct 155 ms 10096 KB Output is correct
8 Correct 255 ms 10176 KB Output is correct
9 Correct 259 ms 10052 KB Output is correct
10 Correct 277 ms 10088 KB Output is correct
11 Correct 204 ms 10064 KB Output is correct
12 Correct 381 ms 10028 KB Output is correct