Submission #489414

#	Time	Username	Problem	Language	Result	Execution time	Memory
489414		Alexandruabcde	Sterilizing Spray (JOI15_sterilizing)	C++14	80 / 100	5091 ms	12816 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 1e5 + 5;
typedef long long LL;

int N, Q, K;
int A[NMAX];

struct Node {
    LL sum = 0;
    int Max = 0;

    Node* st;
    Node* dr;
    Node (int val) {
        sum = Max = val;
        st = dr = nullptr;
    }
};
Node* arb = nullptr;

void Update_Poz (Node* &Tree, int a, int b, int poz, int val) {
    if (Tree == nullptr) {
        Tree = new Node(0);
    }

    if (a == b) {
        Tree->sum = val;
        Tree->Max = val;
        return;
    }

    int mij = (a + b) / 2;

    if (poz <= mij) Update_Poz(Tree->st, a, mij, poz, val);
    else Update_Poz(Tree->dr, mij+1, b, poz, val);

    if (Tree->st != nullptr) {
        Tree->sum = Tree->st->sum;
        Tree->Max = Tree->st->Max;
    }

    if (Tree->dr != nullptr) {
        Tree->sum += Tree->dr->sum;
        Tree->Max = max(Tree->Max, Tree->dr->Max);
    }
}

void UpdateInterval (Node* &Tree, int st, int dr, int ust, int udr) {
    if (st > dr || st > udr || dr < ust || Tree->Max == 0) return;

    if (st == dr) {
        LL new_val = Tree->sum / K;
        Tree->sum = new_val;
        Tree->Max = new_val;
        return;
    }

    int mij = (st + dr) / 2;

    UpdateInterval(Tree->st, st, mij, ust, udr);
    UpdateInterval(Tree->dr, mij+1, dr, ust, udr);
    Tree->sum = Tree->st->sum + Tree->dr->sum;
    Tree->Max = max(Tree->st->Max, Tree->dr->Max);
}

LL Query (Node* &Tree, int st, int dr, int Qa, int Qb) {
    if (Qa <= st && dr <= Qb) return Tree->sum;

    int mij = (st + dr) / 2;
    LL ans_st = 0, ans_dr = 0;
    if (Qa <= mij) ans_st = Query(Tree->st, st, mij, Qa, Qb);
    if (mij < Qb) ans_dr = Query(Tree->dr, mij+1, dr, Qa, Qb);

    return ans_st + ans_dr;
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> Q >> K;

    for (int i = 1; i <= N; ++ i ) {
        cin >> A[i];
        Update_Poz(arb, 1, N, i, A[i]);
    }
}

void Solve () {
    for (; Q; -- Q ) {
        int S, T, U;
        cin >> S >> T >> U;

        if (S == 1)
            Update_Poz(arb, 1, N, T, U);
        else if (S == 2) {
            UpdateInterval(arb, 1, N, T, U);
        }
        else {
            cout << Query(arb, 1, N, T, U) << '\n';
        }
    }
}

int main () {
    Read();
    Solve();

    return 0;
}

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