oj.uz

Submission #820168

# Submission time Handle Problem Language Result Execution time Memory
820168 2023-08-10T22:28:44 Z PenguinsAreCute Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 261 ms 16540 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A[500005];
struct node{
    ll s, e, v, mid;
    node *l, *r;
    node(ll _s, ll _e) {
        s = _s; e = _e; mid = (s + e) / 2;
        if(s != e) {
            l = new node(s, mid);
            r = new node(mid + 1, e);
            value();
        } else {
            v = A[s];
        }
    }
    ll value() {
        return v = l->v + r->v;
    }
    ll query(ll x, ll y) {
        if(s == x && e == y) {return v;}
        if(y <= mid) return l->query(x, y);
        if(x > mid) return r->query(x, y);
        return l->query(x,mid) + r->query(mid + 1,y);
    }
    void update(ll x, ll u) {
        if(s == e) {
            v = u; return;
        }
        if(x <= mid) l->update(x, u);
        else r->update(x, u);
        value();
    }
    void update2(ll x, ll y, ll div) {
        if(v == 0) return;
        if(s == e) {v /= div; return;}
        if(y <= mid) l->update2(x, y, div);
        else if(x > mid) r->update2(x, y, div);
        else {
            l->update2(x, mid, div);
            r->update2(mid + 1, y, div);
        }
        value();
    }
}*root;
int main() {
    ll N, Q, K, a, b, c; cin >> N >> Q >> K;
    for(ll i = 1; i <= N; i++) cin >> A[i];
    root = new node(1, N);
    while(Q--) {
        cin >> a;
        if(a == 2) {
            cin >> a >> b;
            if(K != 1) root->update2(a, b, K);
        } else if(a == 1) {
            cin >> a >> b;
            root->update(a, b);
        } else {
            cin >> a >> b;
            cout << root->query(a, b) << "\n";
        }
    }
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:48:23: warning: unused variable 'c' [-Wunused-variable]
   48 |     ll N, Q, K, a, b, c; cin >> N >> Q >> K;
      |                       ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 328 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 6 ms 700 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 5 ms 708 KB Output is correct
9 Correct 6 ms 708 KB Output is correct
10 Correct 5 ms 724 KB Output is correct
11 Correct 7 ms 724 KB Output is correct
12 Correct 6 ms 708 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 9068 KB Output is correct
2 Correct 115 ms 6700 KB Output is correct
3 Correct 102 ms 12452 KB Output is correct
4 Correct 132 ms 15864 KB Output is correct
5 Correct 156 ms 16540 KB Output is correct
6 Correct 161 ms 16444 KB Output is correct
7 Correct 152 ms 16404 KB Output is correct
8 Correct 148 ms 16460 KB Output is correct
9 Correct 139 ms 16316 KB Output is correct
10 Correct 139 ms 16396 KB Output is correct
11 Correct 144 ms 16400 KB Output is correct
12 Correct 176 ms 16348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1532 KB Output is correct
2 Correct 28 ms 6636 KB Output is correct
3 Correct 39 ms 6612 KB Output is correct
4 Correct 104 ms 4828 KB Output is correct
5 Correct 137 ms 15000 KB Output is correct
6 Correct 141 ms 15008 KB Output is correct
7 Correct 134 ms 15308 KB Output is correct
8 Correct 139 ms 15092 KB Output is correct
9 Correct 137 ms 14880 KB Output is correct
10 Correct 121 ms 14880 KB Output is correct
11 Correct 143 ms 14876 KB Output is correct
12 Correct 123 ms 14884 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 8816 KB Output is correct
2 Correct 137 ms 9140 KB Output is correct
3 Correct 117 ms 7692 KB Output is correct
4 Correct 173 ms 6476 KB Output is correct
5 Correct 225 ms 16332 KB Output is correct
6 Correct 237 ms 16348 KB Output is correct
7 Correct 190 ms 16244 KB Output is correct
8 Correct 233 ms 16316 KB Output is correct
9 Correct 213 ms 16184 KB Output is correct
10 Correct 218 ms 16204 KB Output is correct
11 Correct 197 ms 16196 KB Output is correct
12 Correct 261 ms 16280 KB Output is correct