Submission #820168

#	Time	Username	Problem	Language	Result	Execution time	Memory
820168		PenguinsAreCute	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	261 ms	16540 KiB

sterilizing

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75