oj.uz

Submission #405157

# Submission time Handle Problem Language Result Execution time Memory
405157 2021-05-15T19:29:53 Z timmyfeng Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 88 ms 8484 KB 
#include <bits/stdc++.h>
using namespace std;

struct segtree {
    segtree *left, *right;
    int sum;

    segtree(int l, int r, int *c) {
        if (l == r) {
            sum = c[l];
        } else {
            int m = (l + r) / 2;
            left = new segtree(l, m, c);
            right = new segtree(m + 1, r, c);
            sum = left->sum + right->sum;
        }
    }

    void set(int a, int x, int l, int r) {
        if (l == r) {
            sum = x;
        } else {
            int m = (l + r) / 2;
            if (a <= m) {
                left->set(a, x, l, m);
            } else {
                right->set(a, x, m + 1, r);
            }
            sum = left->sum + right->sum;
        }
    }

    void update(int a, int b, int k, int l, int r) {
        if (b < l || r < a || k == 1 || sum == 0) {
            return;
        } else if (l == r) {
            sum /= k;
        } else {
            int m = (l + r) / 2;
            left->update(a, b, k, l, m);
            right->update(a, b, k, m + 1, r);
            sum = left->sum + right->sum;
        }
    }

    int query(int a, int b, int l, int r) {
        if (b < l || r < a) {
            return 0;
        } else if (a <= l && r <= b) {
            return sum;
        } else {
            int m = (l + r) / 2;
            return left->query(a, b, l, m) + right->query(a, b, m + 1, r);
        }
    }
};

const int N = 100001;

int c[N];

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

    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
    }

    segtree *sum = new segtree(1, n, c);
    while (m--) {
        int t, x, y;
        cin >> t >> x >> y;

        if (t == 1) {
            sum->set(x, y, 1, n);
        } else if (t == 2) {
            sum->update(x, y, k, 1, n);
        } else {
            cout << sum->query(x, y, 1, n) << "\n";
        }
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 5828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1212 KB Output is correct
2 Correct 17 ms 3532 KB Output is correct
3 Correct 22 ms 3700 KB Output is correct
4 Correct 56 ms 3092 KB Output is correct
5 Correct 78 ms 8352 KB Output is correct
6 Correct 78 ms 8416 KB Output is correct
7 Correct 70 ms 8484 KB Output is correct
8 Correct 78 ms 8340 KB Output is correct
9 Correct 69 ms 8236 KB Output is correct
10 Correct 69 ms 8260 KB Output is correct
11 Correct 69 ms 8260 KB Output is correct
12 Correct 69 ms 8260 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 5316 KB Output isn't correct
2 Halted 0 ms 0 KB -