oj.uz

Submission #1050997

# Submission time Handle Problem Language Result Execution time Memory
1050997 2024-08-09T17:52:41 Z manhlinh1501 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 3732 KB 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 1e5 + 5;

int N, Q, K;
i64 a[MAXN];

struct segment_tree {
    int N;
    i64 tree[MAXN * 4];

    void build(int id, int l, int r) {
        if(l == r) {
            tree[id] = a[r];
            return;
        }
        int m = (l + r) / 2;
        build(id * 2, l, m);
        build(id * 2 + 1, m + 1, r);
        tree[id] = tree[id * 2] + tree[id * 2 + 1];
    }

    void init(int _N) {
        N = _N;
        build(1, 1, N);
    }

    void update(int id, int l, int r, int u, int v) {
        if(r < u or l > v or tree[id] == 0) return;
        if(u <= l and r <= v) {
            if(l == r)
                tree[id] /= K;
            else if(tree[id] > 0) {
                int m = (l + r) / 2;
                update(id * 2, l, m, u, v);
                update(id * 2 + 1, m + 1, r, u, v);
                tree[id] = tree[id * 2] + tree[id * 2 + 1];
            }
            return;
        }
        int m = (l + r) / 2;
        update(id * 2, l, m, u, v);
        update(id * 2 + 1, m + 1, r, u, v);
        tree[id] = tree[id * 2] + tree[id * 2 + 1];
    }

    void updatep(int id, int l, int r, int p, int x) {
        if(r < p or l > p) return;
        if(l == r) {
            tree[id] = x;
            return;
        }
        int m = (l + r) / 2;
        if(p <= m)
            updatep(id * 2, l, m, p, x);
        else
            updatep(id * 2 + 1, m + 1, r, p, x);
        tree[id] = tree[id * 2] + tree[id * 2 + 1];
    }

    void updatep(int p, int x) {
        return updatep(1, 1, N, p, x);
    }

    void update(int l, int r) {
        return update(1, 1, N, l, r);
    }

    i64 get(int id, int l, int r, int u, int v) {
        if(r < u or l > v) return 0;
        if(u <= l and r <= v) return tree[id];
        int m = (l + r) / 2;
        return get(id * 2, l, m, u, v) + get(id * 2 + 1, m + 1, r, u, v);
    }

    i64 get(int l, int r) {
        return get(1, 1, N, l, r);
    }
} ST;

signed main() {
#define TASK "code"

    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> Q >> K;

    for(int i = 1; i <= N; i++) cin >> a[i];

    ST.init(N);

    while(Q--) {
        int type;
        cin >> type;
        if(type == 1) {
            int p, x;
            cin >> p >> x;
            ST.updatep(p, x);
        } else if(type == 2) {
            int l, r;
            cin >> l >> r;
            ST.update(l, r);
        } else if(type == 3) {
            int l, r;
            cin >> l >> r;
            cout << ST.get(l, r) << "\n";
        }
    }

    return (0 ^ 0);
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 500 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 564 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2736 ms 3412 KB Output is correct
2 Correct 1766 ms 3456 KB Output is correct
3 Correct 2680 ms 3440 KB Output is correct
4 Correct 4408 ms 3696 KB Output is correct
5 Execution timed out 5013 ms 3704 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 600 KB Output is correct
2 Correct 6 ms 2908 KB Output is correct
3 Correct 8 ms 2908 KB Output is correct
4 Correct 24 ms 2884 KB Output is correct
5 Correct 30 ms 3420 KB Output is correct
6 Correct 36 ms 3676 KB Output is correct
7 Execution timed out 5066 ms 3568 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3164 KB Output is correct
2 Correct 45 ms 3160 KB Output is correct
3 Correct 53 ms 3052 KB Output is correct
4 Correct 58 ms 3120 KB Output is correct
5 Correct 65 ms 3668 KB Output is correct
6 Correct 74 ms 3664 KB Output is correct
7 Correct 64 ms 3664 KB Output is correct
8 Correct 89 ms 3716 KB Output is correct
9 Correct 75 ms 3692 KB Output is correct
10 Correct 88 ms 3732 KB Output is correct
11 Correct 75 ms 3528 KB Output is correct
12 Correct 115 ms 3668 KB Output is correct