oj.uz

Submission #952401

# Submission time Handle Problem Language Result Execution time Memory
952401 2024-03-23T18:02:00 Z SulA Sterilizing Spray (JOI15_sterilizing) C++17
5 / 100
 5000 ms 12084 KB 
#include <bits/stdc++.h>
#define push push_back
using namespace std;

long long oper(long long a, long long b) { return a + b; }

struct SEG {
    vector<long long> tree, lazy;
    int offset = 1;
    void init(int n) {
        while (offset < n) offset <<= 2;
        tree.resize(2*offset);
        lazy.resize(2*offset);
    }

    void pointupdate(int i, long long x) {
        i += offset;
        tree[i] = x;
        while (i /= 2) tree[i] = oper(tree[2*i], tree[2*i+1]);
    }

    long long _query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        if (r < ql || qr < l) return 0;
        int mid = (l+r)/2;
        return oper(_query(2*v, l, mid, ql, qr),
                    _query(2*v+1, mid+1, r, ql, qr));
    }

    long long query(int ql, int qr) {
        return _query(1, 0, offset-1, ql, qr);
    }

    void lazyupdate(int v, int l, int r, int ul, int ur, int k) {
        if (r < ul || ur < l) return;
        if (l == r) {
            tree[v] /= k;
            return;
        }
        int mid = (l+r)/2;
        lazyupdate(2*v, l, mid, ul, ur, k);
        lazyupdate(2*v+1, mid+1, r, ul, ur, k);
        tree[v] = oper(tree[2*v], tree[2*v+1]);
    }
};


int main () {
    int n,q,k; cin >> n >> q >> k;
    SEG s; s.init(n);
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        s.pointupdate(i, x);
    }
    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int i; long long x; cin >> i >> x;
            s.pointupdate(--i, x);
        }
        else if (type == 2) {
            int l,r; cin >> l >> r;
            s.lazyupdate(1, 0, s.offset-1, --l, --r, k);
        }
        else {
            int l,r; cin >> l >> r;
            cout << s.query(--l, --r) << "\n";
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 604 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 9 ms 600 KB Output is correct
8 Correct 8 ms 600 KB Output is correct
9 Correct 11 ms 636 KB Output is correct
10 Correct 11 ms 624 KB Output is correct
11 Correct 8 ms 640 KB Output is correct
12 Correct 9 ms 604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3590 ms 4660 KB Output is correct
2 Correct 2242 ms 5000 KB Output is correct
3 Correct 3558 ms 10952 KB Output is correct
4 Execution timed out 5059 ms 11092 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 1360 KB Output is correct
2 Correct 305 ms 2896 KB Output is correct
3 Correct 486 ms 2876 KB Output is correct
4 Correct 1080 ms 3768 KB Output is correct
5 Correct 4882 ms 10232 KB Output is correct
6 Correct 4875 ms 10444 KB Output is correct
7 Correct 4992 ms 10484 KB Output is correct
8 Execution timed out 5025 ms 10212 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1587 ms 4048 KB Output is correct
2 Correct 1843 ms 4176 KB Output is correct
3 Correct 985 ms 3792 KB Output is correct
4 Correct 1329 ms 4588 KB Output is correct
5 Correct 4942 ms 12084 KB Output is correct
6 Correct 4948 ms 11844 KB Output is correct
7 Correct 4944 ms 11444 KB Output is correct
8 Correct 4869 ms 11348 KB Output is correct
9 Execution timed out 5016 ms 10276 KB Time limit exceeded
10 Halted 0 ms 0 KB -