oj.uz

Submission #1050999

# Submission time Handle Problem Language Result Execution time Memory
1050999 2024-08-09T17:54:55 Z manhlinh1501 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 3444 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) {
                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 344 KB Output is correct
2 Correct 1 ms 344 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 344 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 476 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 2706 ms 3132 KB Output is correct
2 Correct 1622 ms 3152 KB Output is correct
3 Correct 2663 ms 3268 KB Output is correct
4 Correct 4369 ms 3336 KB Output is correct
5 Execution timed out 5025 ms 3444 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 600 KB Output is correct
2 Correct 5 ms 2652 KB Output is correct
3 Correct 7 ms 2860 KB Output is correct
4 Correct 20 ms 2648 KB Output is correct
5 Correct 24 ms 2908 KB Output is correct
6 Correct 26 ms 2904 KB Output is correct
7 Execution timed out 5010 ms 3168 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2908 KB Output is correct
2 Correct 45 ms 3040 KB Output is correct
3 Correct 50 ms 2900 KB Output is correct
4 Correct 74 ms 2908 KB Output is correct
5 Correct 61 ms 3152 KB Output is correct
6 Correct 70 ms 3132 KB Output is correct
7 Correct 59 ms 3152 KB Output is correct
8 Correct 84 ms 3156 KB Output is correct
9 Correct 72 ms 3388 KB Output is correct
10 Correct 104 ms 3156 KB Output is correct
11 Correct 62 ms 3164 KB Output is correct
12 Correct 113 ms 3180 KB Output is correct