oj.uz

Submission #523882

# Submission time Handle Problem Language Result Execution time Memory
523882 2022-02-08T11:07:54 Z IMystic Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 7516 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){ 
            vector<int> tem ;
            for(auto it = lower_bound(b.begin(), b.end(), l - 1); it != b.end() && (*it) < r; it++){
                int x = *it;
                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 5 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 9 ms 444 KB Output is correct
5 Correct 8 ms 580 KB Output is correct
6 Correct 6 ms 572 KB Output is correct
7 Correct 7 ms 572 KB Output is correct
8 Correct 7 ms 452 KB Output is correct
9 Correct 9 ms 460 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 576 KB Output is correct
12 Correct 7 ms 440 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 836 KB Output is correct
2 Correct 26 ms 3252 KB Output is correct
3 Correct 31 ms 3492 KB Output is correct
4 Correct 42 ms 2252 KB Output is correct
5 Correct 88 ms 7128 KB Output is correct
6 Correct 84 ms 6928 KB Output is correct
7 Execution timed out 5082 ms 7044 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 3908 KB Output is correct
2 Correct 161 ms 4208 KB Output is correct
3 Correct 254 ms 3672 KB Output is correct
4 Correct 196 ms 2884 KB Output is correct
5 Correct 271 ms 7348 KB Output is correct
6 Correct 316 ms 7236 KB Output is correct
7 Correct 249 ms 7200 KB Output is correct
8 Correct 471 ms 7240 KB Output is correct
9 Correct 134 ms 7516 KB Output is correct
10 Correct 210 ms 7348 KB Output is correct
11 Correct 148 ms 7340 KB Output is correct
12 Correct 201 ms 7420 KB Output is correct