oj.uz

Submission #523868

# Submission time Handle Problem Language Result Execution time Memory
523868 2022-02-08T10:15:20 Z IMystic Sterilizing Spray (JOI15_sterilizing) C++17
5 / 100
 5000 ms 3276 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<int> &a) : n(int(a.size())) {
        fen.resize(n);
        for(int i=0; i<n; i++)this->inc(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 set(int p, T v){
        v = v - get(p, p);
        inc(p, v);
    }

    void inc(int p, T v){
        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<int> 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;
        --l, --r;
        if(t == 1){
            d.set(l, r + 1);
            b.insert(l);
        }
        else if(t == 2){
            while(true){
                auto it = lower_bound(b.begin(), b.end(), l);
                if(*it > r || it == b.end())break;
                ll nw = d.get(*it, *it)/k;
                d.set(*it, nw);
                l = *it + 1;
                if(nw == 0)b.erase(*it);
            }
        }else{
            cout << d.get(l, r) << '\n';
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 332 KB Output is correct
2 Correct 415 ms 372 KB Output is correct
3 Correct 263 ms 424 KB Output is correct
4 Correct 426 ms 452 KB Output is correct
5 Correct 998 ms 540 KB Output is correct
6 Correct 535 ms 536 KB Output is correct
7 Correct 735 ms 536 KB Output is correct
8 Correct 801 ms 540 KB Output is correct
9 Correct 1146 ms 532 KB Output is correct
10 Correct 751 ms 544 KB Output is correct
11 Correct 746 ms 532 KB Output is correct
12 Correct 830 ms 536 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 588 KB Output is correct
2 Execution timed out 5046 ms 2892 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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