Submission #87199

#	Time	Username	Problem	Language	Result	Execution time	Memory
87199		tieunhi	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	310 ms	69684 KiB

sterilizing

#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define ll long long
#define mid (r + l)/2
#define N 100005

using namespace std;

int n, numQuery, k;
struct IntervalTree
{
    ll t[N << 2];
    int mx[N << 2];
    void update(int l, int r, int id, int x, int val)
    {
        if (l == r)
        {
            t[id] = mx[id] = val;
            return;
        }
        if (x <= mid) update(l, mid, id*2, x, val);
        else update(mid+1, r, id*2+1, x, val);
        t[id] = t[id*2] + t[id*2+1];
        mx[id] = max(mx[id*2], mx[id*2+1]);
    }
    void divide(int l, int r, int id, int x, int y)
    {
        if (l > y || r < x) return;
        if (l >= x && r <= y)
        {
            if (mx[id] == 0) return;
            if (l == r)
            {
                t[id] = mx[id] = t[id]/k;
                return;
            }
        }
        divide(l, mid, id*2, x, y);
        divide(mid+1, r, id*2+1, x, y);
        t[id] = t[id*2] + t[id*2+1];
        mx[id] = max(mx[id*2], mx[id*2+1]);
    }
    ll get(int l, int r, int id, int x, int y)
    {
        if (l > y || r < x) return 0;
        if (l >= x && r <= y) return t[id];
        ll a = get(l, mid, id*2, x, y);
        ll b = get(mid+1, r, id*2+1, x, y);
        return a + b;
    }
}t;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> numQuery >> k;
    FOR(i, 1, n)
    {
        int x; cin >> x;
        t.update(1, n, 1, i, x);
    }
    while (numQuery--)
    {
        int type, x, y; cin >> type >> x >> y;
        if (type == 1)
            t.update(1, n, 1, x, y);
        else if (type == 2 && k > 1)
            t.divide(1, n, 1, x, y);
        else if (type == 3)
            cout <<t.get(1, n, 1, x, y)<<'\n';
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75