oj.uz

Submission #489415

# Submission time Handle Problem Language Result Execution time Memory
489415 2021-11-22T22:32:11 Z Alexandruabcde Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 287 ms 13024 KB 
#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) {
            if (K == 1) continue;
            UpdateInterval(arb, 1, N, T, U);
        }
        else {
            cout << Query(arb, 1, N, T, U) << '\n';
        }
    }
}

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

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 4 ms 588 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 4 ms 588 KB Output is correct
12 Correct 4 ms 588 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 5444 KB Output is correct
2 Correct 53 ms 5544 KB Output is correct
3 Correct 77 ms 9752 KB Output is correct
4 Correct 72 ms 12396 KB Output is correct
5 Correct 81 ms 12968 KB Output is correct
6 Correct 82 ms 13020 KB Output is correct
7 Correct 92 ms 13024 KB Output is correct
8 Correct 91 ms 13016 KB Output is correct
9 Correct 75 ms 12852 KB Output is correct
10 Correct 76 ms 12824 KB Output is correct
11 Correct 75 ms 12872 KB Output is correct
12 Correct 79 ms 12812 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 964 KB Output is correct
2 Correct 19 ms 4592 KB Output is correct
3 Correct 23 ms 4684 KB Output is correct
4 Correct 51 ms 2756 KB Output is correct
5 Correct 87 ms 10108 KB Output is correct
6 Correct 80 ms 10068 KB Output is correct
7 Correct 80 ms 10780 KB Output is correct
8 Correct 101 ms 11608 KB Output is correct
9 Correct 74 ms 11392 KB Output is correct
10 Correct 74 ms 11336 KB Output is correct
11 Correct 89 ms 11392 KB Output is correct
12 Correct 77 ms 11368 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 5420 KB Output is correct
2 Correct 106 ms 5676 KB Output is correct
3 Correct 121 ms 4832 KB Output is correct
4 Correct 129 ms 3652 KB Output is correct
5 Correct 172 ms 10316 KB Output is correct
6 Correct 189 ms 10344 KB Output is correct
7 Correct 177 ms 10268 KB Output is correct
8 Correct 262 ms 10292 KB Output is correct
9 Correct 198 ms 10608 KB Output is correct
10 Correct 218 ms 10396 KB Output is correct
11 Correct 169 ms 10360 KB Output is correct
12 Correct 287 ms 10336 KB Output is correct