oj.uz

Submission #1051002

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

int N, Q, K;
int 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 and K > 1) {
                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 p, int x) {
        int l = 1, r = N, id = 1;
        while(l < r) {
            int m = (l + r) / 2;
            if(p <= m) {
                id = id * 2;
                r = m;
            } else {
                id = id * 2 + 1;
                l = m + 1;
            }
        }
        tree[id] = x;
        while(id >= 1) {
            id >>= 1;
            tree[id] = tree[id * 2] + tree[id * 2 + 1];
        }
    }

    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 or tree[id] == 0) 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: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 ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2108 KB Output is correct
2 Correct 28 ms 1848 KB Output is correct
3 Correct 24 ms 2960 KB Output is correct
4 Correct 31 ms 3408 KB Output is correct
5 Correct 37 ms 3412 KB Output is correct
6 Correct 36 ms 3436 KB Output is correct
7 Correct 35 ms 3444 KB Output is correct
8 Correct 38 ms 3160 KB Output is correct
9 Correct 33 ms 3308 KB Output is correct
10 Correct 32 ms 3384 KB Output is correct
11 Correct 33 ms 3480 KB Output is correct
12 Correct 33 ms 3408 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 604 KB Output is correct
2 Correct 5 ms 2652 KB Output is correct
3 Correct 8 ms 2648 KB Output is correct
4 Correct 35 ms 2788 KB Output is correct
5 Correct 43 ms 3104 KB Output is correct
6 Correct 25 ms 2908 KB Output is correct
7 Correct 40 ms 3160 KB Output is correct
8 Correct 25 ms 4444 KB Output is correct
9 Correct 23 ms 4188 KB Output is correct
10 Correct 23 ms 4188 KB Output is correct
11 Correct 23 ms 4212 KB Output is correct
12 Correct 23 ms 4340 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2900 KB Output is correct
2 Correct 52 ms 2908 KB Output is correct
3 Correct 57 ms 2904 KB Output is correct
4 Correct 58 ms 3060 KB Output is correct
5 Correct 63 ms 3160 KB Output is correct
6 Correct 73 ms 3344 KB Output is correct
7 Correct 60 ms 3320 KB Output is correct
8 Correct 90 ms 3152 KB Output is correct
9 Correct 75 ms 3160 KB Output is correct
10 Correct 97 ms 3176 KB Output is correct
11 Correct 64 ms 3320 KB Output is correct
12 Correct 121 ms 3392 KB Output is correct