oj.uz

Submission #1050990

# Submission time Handle Problem Language Result Execution time Memory
1050990 2024-08-09T17:46:38 Z manhlinh1501 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 6184 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;
        updatep(id * 2, l, m, p, x);
        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:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 548 KB Output is correct
7 Correct 2 ms 628 KB Output is correct
8 Correct 2 ms 624 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 480 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2652 ms 3408 KB Output is correct
2 Correct 1639 ms 3276 KB Output is correct
3 Correct 2672 ms 3360 KB Output is correct
4 Correct 4377 ms 3760 KB Output is correct
5 Execution timed out 5054 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 9 ms 604 KB Output is correct
2 Correct 6 ms 3164 KB Output is correct
3 Correct 8 ms 3248 KB Output is correct
4 Correct 25 ms 4036 KB Output is correct
5 Correct 31 ms 4692 KB Output is correct
6 Correct 32 ms 4892 KB Output is correct
7 Execution timed out 5068 ms 4692 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 3112 KB Output is correct
2 Correct 47 ms 4956 KB Output is correct
3 Correct 59 ms 4180 KB Output is correct
4 Correct 59 ms 4688 KB Output is correct
5 Correct 67 ms 6064 KB Output is correct
6 Correct 74 ms 6184 KB Output is correct
7 Correct 63 ms 6132 KB Output is correct
8 Correct 91 ms 5972 KB Output is correct
9 Correct 77 ms 5976 KB Output is correct
10 Correct 86 ms 5968 KB Output is correct
11 Correct 71 ms 5972 KB Output is correct
12 Correct 115 ms 5968 KB Output is correct