oj.uz

Submission #523861

# Submission time Handle Problem Language Result Execution time Memory
523861 2022-02-08T10:05:46 Z IMystic Sterilizing Spray (JOI15_sterilizing) C++17
0 / 100
 2 ms 332 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);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    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;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:71:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:72:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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