oj.uz

Submission #1050994

# Submission time Handle Problem Language Result Execution time Memory
1050994 2024-08-09T17:48:07 Z manhlinh1501 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 3868 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 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) 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 344 KB Output is correct
2 Correct 1 ms 348 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 348 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 348 KB Output is correct
11 Correct 2 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 2691 ms 3512 KB Output is correct
2 Correct 1652 ms 3244 KB Output is correct
3 Correct 2698 ms 3340 KB Output is correct
4 Correct 4580 ms 3760 KB Output is correct
5 Execution timed out 5059 ms 3868 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 604 KB Output is correct
2 Correct 10 ms 2908 KB Output is correct
3 Correct 10 ms 3044 KB Output is correct
4 Correct 27 ms 2928 KB Output is correct
5 Correct 30 ms 3512 KB Output is correct
6 Correct 29 ms 3424 KB Output is correct
7 Execution timed out 5043 ms 3444 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3196 KB Output is correct
2 Correct 45 ms 3160 KB Output is correct
3 Correct 63 ms 3156 KB Output is correct
4 Correct 57 ms 3152 KB Output is correct
5 Correct 65 ms 3664 KB Output is correct
6 Correct 73 ms 3664 KB Output is correct
7 Correct 62 ms 3556 KB Output is correct
8 Correct 87 ms 3668 KB Output is correct
9 Correct 75 ms 3556 KB Output is correct
10 Correct 86 ms 3664 KB Output is correct
11 Correct 73 ms 3728 KB Output is correct
12 Correct 114 ms 3664 KB Output is correct