Submission #493950

#	Time	Username	Problem	Language	Result	Execution time	Memory
493950		alextodoran	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	1277 ms	7696 KiB

sterilizing

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int Q_MAX = 100000;

int N, Q, K;

int C[N_MAX + 2];

struct SGTNode {
    int first;
    ll sum;
};

SGTNode operator + (const SGTNode &u, const SGTNode &v) {
    return SGTNode{(u.first != -1 ? u.first : v.first), u.sum + v.sum};
}

SGTNode SGT[N_MAX * 4 + 2];

void build (int node, int l, int r) {
    if (l == r) {
        SGT[node].first = (C[l] > 0 ? l : -1);
        SGT[node].sum = C[l];
        return;
    }

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    build(lSon, l, mid);
    build(rSon, mid + 1, r);

    SGT[node] = SGT[lSon] + SGT[rSon];
}
void build () {
    build(1, 1, N);
}

void update (int node, int l, int r, int upos) {
    if (l == r) {
        SGT[node].first = (C[l] > 0 ? l : -1);
        SGT[node].sum = C[l];
        return;
    }

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (upos <= mid) {
        update(lSon, l, mid, upos);
    } else {
        update(rSon, mid + 1, r, upos);
    }

    SGT[node] = SGT[lSon] + SGT[rSon];
}
void update (int upos) {
    update(1, 1, N, upos);
}

SGTNode query (int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return SGT[node];
    }

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (ql <= mid && mid + 1 <= qr) {
        return query(lSon, l, mid, ql, qr) + query(rSon, mid + 1, r, ql, qr);
    } else if (ql <= mid) {
        return query(lSon, l, mid, ql, qr);
    } else {
        return query(rSon, mid + 1, r, ql, qr);
    }
}
SGTNode query (int ql, int qr) {
    return query(1, 1, N, ql, qr);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> Q >> K;
    for (int i = 1; i <= N; i++) {
        cin >> C[i];
    }
    build();
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int upos, uval;
            cin >> upos >> uval;
            C[upos] = uval;
            update(upos);
        } else if (type == 2) {
            int l, r;
            cin >> l >> r;
            if (K == 1) {
                continue;
            }
            while (l <= r) {
                int upos = query(l, r).first;
                if (upos != -1) {
                    C[upos] /= K;
                    update(upos);
                    l = upos + 1;
                } else {
                    break;
                }
            }
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(l, r).sum << "\n";
        }
    }

    return 0;
}

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