oj.uz

Submission #521767

# Submission time Handle Problem Language Result Execution time Memory
521767 2022-02-03T02:46:21 Z tengiz05 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 9636 KB 
#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 100005;
int n, k;
struct Info {
    int mx;
    i64 sum;
    Info(int x = 0) : mx(x), sum(x) {}
};
Info operator+(const Info &a, const Info &b) {
    Info res;
    res.mx = std::max(a.mx, b.mx);
    res.sum = a.sum + b.sum;
    return res;
}
Info t[4 * N];
void modify(int p, int l, int r, int x, int y) {
    if (l == r - 1) {
        t[p] = Info(y);
        return;
    }
    int m = (l + r) / 2;
    if (x < m) {
        modify(2 * p, l, m, x, y);
    } else {
        modify(2 * p + 1, m, r, x, y);
    }
    t[p] = t[2 * p] + t[2 * p + 1];
}
void apply(int p, int l, int r, int x, int y) {
    if (r <= x || y <= l || t[p].mx == 0) {
        return;
    }
    if (l == r - 1) {
        t[p] = Info(t[p].mx / k);
        return;
    }
    int m = (l + r) / 2;
    apply(2 * p, l, m, x, y);
    apply(2 * p + 1, m, r, x, y);
    t[p] = t[2 * p] + t[2 * p + 1];
}
Info query(int p, int l, int r, int x, int y) {
    if (r <= x || y <= l) {
        return Info();
    }
    if (x <= l && r <= y) {
        return t[p];
    }
    int m = (l + r) / 2;
    return query(2 * p, l, m, x, y) + query(2 * p + 1, m, r, x, y);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int q;
    std::cin >> n >> q >> k;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        modify(1, 0, n, i, a[i]);
    }
    
    while (q--) {
        int op, x, y;
        std::cin >> op >> x >> y;
        
        x--;
        
        if (op == 1) {
            modify(1, 0, n, x, y);
        } else if (op == 2) {
            apply(1, 0, n, x, y);
        } else {
            std::cout << query(1, 0, n, x, y).sum << "\n";
        }
    }
    
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 5 ms 6592 KB Output is correct
3 Correct 4 ms 6604 KB Output is correct
4 Correct 6 ms 6636 KB Output is correct
5 Correct 6 ms 6588 KB Output is correct
6 Correct 6 ms 6588 KB Output is correct
7 Correct 6 ms 6604 KB Output is correct
8 Correct 6 ms 6588 KB Output is correct
9 Correct 6 ms 6604 KB Output is correct
10 Correct 6 ms 6648 KB Output is correct
11 Correct 6 ms 6604 KB Output is correct
12 Correct 7 ms 6544 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4583 ms 7300 KB Output is correct
2 Correct 2852 ms 8652 KB Output is correct
3 Correct 4743 ms 8612 KB Output is correct
4 Execution timed out 5053 ms 8804 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6604 KB Output is correct
2 Correct 17 ms 6732 KB Output is correct
3 Correct 25 ms 6776 KB Output is correct
4 Correct 49 ms 6676 KB Output is correct
5 Correct 65 ms 6972 KB Output is correct
6 Correct 64 ms 6908 KB Output is correct
7 Execution timed out 5081 ms 7112 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 6912 KB Output is correct
2 Correct 92 ms 8680 KB Output is correct
3 Correct 96 ms 7936 KB Output is correct
4 Correct 105 ms 8628 KB Output is correct
5 Correct 127 ms 9636 KB Output is correct
6 Correct 142 ms 8880 KB Output is correct
7 Correct 125 ms 8560 KB Output is correct
8 Correct 168 ms 8632 KB Output is correct
9 Correct 163 ms 8816 KB Output is correct
10 Correct 178 ms 8636 KB Output is correct
11 Correct 136 ms 8648 KB Output is correct
12 Correct 230 ms 8640 KB Output is correct