Submission #380543

#	Time	Username	Problem	Language	Result	Execution time	Memory
380543		Aryan_Raina	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	1373 ms	198136 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define ar array

const int INF = 1e17;
const int MOD = 1e9;

struct SegTree {
    vector<deque<int>> values;
    vector<int> operations;
    int size, k;
    void init(int n, int _k) {
        size = 1; k = _k;
        while (size < n) size <<= 1;
        operations.resize(2*size);
        values.resize(2*size);
    }
    void propogate(int x, int lx, int rx) {
        if (rx - lx != 1) {
            operations[2*x+1] += operations[x];
            operations[2*x+2] += operations[x];
        } 
        for ( ; operations[x] && values[x].size() > 1; operations[x]--) values[x].pop_front();
        operations[x] = 0;
    }
    void update(int x, int lx, int rx) {
        if (rx - lx == 1) return;
        int m = (lx + rx) >> 1;
        while (values[x].size() > 0) values[x].pop_front();
        propogate(2*x+1, lx, m);
        propogate(2*x+2, m, rx);
        int i, j;
        for (i = 0, j = 0; i < values[2*x+1].size() && j < values[2*x+2].size(); ++i, ++j) {  
            values[x].push_back(values[2*x+1][i] + values[2*x+2][j]);
        }
        for (; i < values[2*x+1].size(); ++i) values[x].push_back(values[2*x+1][i]);
            for (; j < values[2*x+2].size(); ++j) values[x].push_back(values[2*x+2][j]);
    }
    void set(int i, int v, int x, int lx, int rx) {
        propogate(x, lx, rx);
        if (rx - lx == 1) {
            while (values[x].size() > 0) values[x].pop_front();
            while (v && k > 1) {
                values[x].push_back(v); v /= k;
            }
            values[x].push_back(v);
            return;
        }
        int m = (lx + rx) >> 1;
        if (i < m) set(i, v, 2*x+1, lx, m);
        else set(i, v, 2*x+2, m, rx);
        update(x, lx, rx);
    }
    void set(int i, int v) {
        set(i, v, 0, 0, size);
    }
    void modify(int l, int r, int x, int lx, int rx) {
        propogate(x, lx, rx);
        if (lx >= r || l >= rx) return;
        if (l <= lx && rx <= r) return void(operations[x]++);
        int m = (lx + rx) >> 1;
        modify(l, r, 2*x+1, lx, m);
        modify(l, r, 2*x+2, m, rx);
        update(x, lx, rx);
    }
    void modify(int l, int r) {
        modify(l, r, 0, 0, size);
    }
    int calc(int l, int r, int x, int lx, int rx) {
        propogate(x, lx, rx);
        if (lx >= r || l >= rx) return 0;
        if (l <= lx && rx <= r) {
            return values[x].front();
        }
        int m = (lx + rx) >> 1;
        int s1 = calc(l, r, 2*x+1, lx, m);
        int s2 = calc(l, r, 2*x+2, m, rx);
        return s1 + s2;
    }
    int calc(int l, int r) {
        return calc(l, r, 0, 0, size);
    }
};

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k; cin>>n>>m>>k;
    SegTree st; st.init(n, k);
    for (int i = 0; i < n; i++) {
        int x; cin>>x;
        st.set(i, x);
    }
    while (m--) {
        int t, a, b; cin>>t>>a>>b;
        if (t == 1) {
            st.set(a-1, b);
        } else if (t == 2 && k > 1) {
            st.modify(a-1, b);
        } else if (t == 3) {
            cout<<st.calc(a-1, b)<<"\n";
        }
    }
}

Compilation message (stderr)

sterilizing.cpp: In member function 'void SegTree::update(long long int, long long int, long long int)':
sterilizing.cpp:36:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (i = 0, j = 0; i < values[2*x+1].size() && j < values[2*x+2].size(); ++i, ++j) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:36:58: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (i = 0, j = 0; i < values[2*x+1].size() && j < values[2*x+2].size(); ++i, ++j) {
      |                                                        ~~^~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:39:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (; i < values[2*x+1].size(); ++i) values[x].push_back(values[2*x+1][i]);
      |                ~~^~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:40:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             for (; j < values[2*x+2].size(); ++j) values[x].push_back(values[2*x+2][j]);
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75