oj.uz

Submission #953171

# Submission time Handle Problem Language Result Execution time Memory
953171 2024-03-25T15:17:52 Z FaresSTH Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 5000 ms 3920 KB 
#pragma GCC optimize("O3,Ofast,unroll-loops")
#include "bits/stdc++.h"
const int MOD = 1e9 + 7;
using namespace std;
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define ll long long
#define S second
#define F first
vector<ll> tree;
ll N;
 
void init(ll n) {
    N = 1 << (ll)ceil(log2(n));
    tree.resize(N * 2, 0);
}
 
void upd(ll id, ll val) {
    id += N;
    tree[id] = val;
    while (id /= 2) {
        tree[id] = tree[id * 2] + tree[id * 2 + 1];
    }
}
 
ll query(ll id, ll l, ll r, ll s, ll e) {
    if (s <= l && r <= e) return tree[id];
    if (l > e || r < s) return 0;
    ll m = (l + r) / 2;
    return query(id * 2, l, m, s, e) + query(id * 2 + 1, m + 1, r, s, e);
}
 
void solve() {
    ll n, q, k;
    cin >> n >> q >> k;
    vector<ll> c(n); init(n);
    for (ll i = 0; i < n; i++) {
        cin >> c[i];
        upd(i, c[i]);
    }
 
    while (q--) {
        ll s, t, u;
        cin >> s >> t >> u;
        if (s == 1) {
            c[t - 1] = u;
            upd(t - 1, u);
        }
        if (s == 2) {
            if (k != 1) {
                for (ll i = t - 1; i < u; i++) {
                    c[i] /= k;
                    upd(i, c[i]);
                }
            }
        }
        if (s == 3) cout << query(1, 0, N - 1, t - 1, u - 1) << endl;
    }
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 2164 KB Output is correct
2 Correct 70 ms 1896 KB Output is correct
3 Correct 51 ms 3160 KB Output is correct
4 Correct 81 ms 3544 KB Output is correct
5 Correct 78 ms 3560 KB Output is correct
6 Correct 79 ms 3664 KB Output is correct
7 Correct 80 ms 3604 KB Output is correct
8 Correct 83 ms 3920 KB Output is correct
9 Correct 83 ms 3668 KB Output is correct
10 Correct 76 ms 3656 KB Output is correct
11 Correct 77 ms 3764 KB Output is correct
12 Correct 74 ms 3712 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 644 KB Output is correct
2 Correct 1601 ms 2132 KB Output is correct
3 Correct 2529 ms 2488 KB Output is correct
4 Execution timed out 5045 ms 3316 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5013 ms 2472 KB Time limit exceeded
2 Halted 0 ms 0 KB -