Submission #44706

#	Time	Username	Problem	Language	Result	Execution time	Memory
44706		choikiwon	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	1861 ms	307276 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int N, Q, K;
int C[100010];
ll psum[100010];

struct node {
    ll sum;
    deque<int> dq;
};

node mrg(node &a, node &b) {
    node ret;
    ret.sum = a.sum + b.sum;

    for(int i = 0; i < min(a.dq.size(), b.dq.size()); i++) {
        ret.dq.push_back(a.dq[i] + b.dq[i]);
    }
    for(int i = min(a.dq.size(), b.dq.size()); i < a.dq.size(); i++) {
        ret.dq.push_back(a.dq[i]);
    }
    for(int i = min(a.dq.size(), b.dq.size()); i < b.dq.size(); i++) {
        ret.dq.push_back(b.dq[i]);
    }
    return ret;
}

struct BIT {
    vector<node> tree;
    vector<int> lazy;
    void init() {
        tree = vector<node>(4 * N);
        lazy = vector<int>(4 * N, 0);
        build(0, N - 1, 1);
    }
    void build(int l, int r, int n) {
        if(l == r) {
            tree[n].sum = C[l];
            if(K == 1) tree[n].dq.push_back(C[l]);
            else while(C[l]) tree[n].dq.push_back(C[l] % K), C[l] /= K;
            return;
        }
        int m = (l + r)>>1;
        build(l, m, 2*n);
        build(m + 1, r, 2*n + 1);
        tree[n] = mrg(tree[2*n], tree[2*n + 1]);
    }
    void prop(int l, int r, int n) {
        if(l != r) {
            lazy[2*n] += lazy[n];
            lazy[2*n + 1] += lazy[n];
            while(lazy[n]) {
                if(!tree[2*n].dq.size() && !tree[2*n + 1].dq.size()) break;
                if(tree[2*n].dq.size()) {
                    tree[2*n].sum -= tree[2*n].dq.front(); tree[2*n].dq.pop_front();
                    tree[2*n].sum /= K;
                }
                if(tree[2*n + 1].dq.size()) {
                    tree[2*n + 1].sum -= tree[2*n + 1].dq.front(); tree[2*n + 1].dq.pop_front();
                    tree[2*n + 1].sum /= K;
                }
                lazy[n]--;
            }
            lazy[n] = 0;
        }
    }
    void upd1(int idx, int val, int l, int r, int n) {
        if(idx < l || r < idx) return;
        if(l == r) {
            tree[n].sum = val;
            while(!tree[n].dq.empty()) tree[n].dq.pop_back();
            if(K == 1) tree[n].dq.push_back(val);
            else while(val) tree[n].dq.push_back(val % K), val /= K;
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd1(idx, val, l, m, 2*n);
        upd1(idx, val, m + 1, r, 2*n + 1);
        tree[n] = mrg(tree[2*n], tree[2*n + 1]);
    }
    void upd2(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return;
        if(a <= l && r <= b) {
            if(!tree[n].dq.empty()) {
                tree[n].sum -= tree[n].dq.front(); tree[n].dq.pop_front();
                tree[n].sum /= K;
            }
            lazy[n]++;
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd2(a, b, l, m, 2*n);
        upd2(a, b, m + 1, r, 2*n + 1);
        tree[n] = mrg(tree[2*n], tree[2*n + 1]);
    }
    ll quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return 0;
        if(a <= l && r <= b) return tree[n].sum;
        prop(l, r, n);
        int m = (l + r)>>1;
        ll L = quer(a, b, l, m, 2*n);
        ll R = quer(a, b, m + 1, r, 2*n + 1);
        return L + R;
    }
} bit;

int main() {
    scanf("%d %d %d", &N, &Q, &K);

    for(int i = 0; i < N; i++) {
        scanf("%d", &C[i]);
    }

    bit.init();

    for(int i = 0; i < Q; i++) {
        int t, a, b; scanf("%d %d %d", &t, &a, &b);
        if(t == 1) {
            a--;
            bit.upd1(a, b, 0, N - 1, 1);
        }
        if(t == 2) {
            if(K == 1) continue;
            a--; b--;
            bit.upd2(a, b, 0, N - 1, 1);
        }
        if(t == 3) {
            a--; b--;
            printf("%lld\n", bit.quer(a, b, 0, N - 1, 1));
        }
    }
}

Compilation message (stderr)

sterilizing.cpp: In function 'node mrg(node&, node&)':
sterilizing.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < min(a.dq.size(), b.dq.size()); i++) {
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:22:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = min(a.dq.size(), b.dq.size()); i < a.dq.size(); i++) {
                                                ~~^~~~~~~~~~~~~
sterilizing.cpp:25:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = min(a.dq.size(), b.dq.size()); i < b.dq.size(); i++) {
                                                ~~^~~~~~~~~~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &Q, &K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &C[i]);
         ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:122:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int t, a, b; scanf("%d %d %d", &t, &a, &b);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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