oj.uz

Submission #521766

# Submission time Handle Problem Language Result Execution time Memory
521766 2022-02-03T02:45:28 Z tengiz05 Sterilizing Spray (JOI15_sterilizing) C++17
0 / 100
 5000 ms 5376 KB 
#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 100005;
int n, k;
struct Info {
    int mx;
    int 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
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3816 KB Output is correct
2 Correct 16 ms 3780 KB Output is correct
3 Correct 22 ms 3908 KB Output is correct
4 Correct 48 ms 4676 KB Output is correct
5 Correct 68 ms 5316 KB Output is correct
6 Correct 61 ms 5232 KB Output is correct
7 Execution timed out 5089 ms 4856 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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