Submission #102393

#	Time	Username	Problem	Language	Result	Execution time	Memory
102393		Alexa2001	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	317 ms	5848 KiB

sterilizing

#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)


using namespace std;

/// 17:27

const int Nmax = 1e5 + 5;
typedef long long ll;


int C[Nmax], n, K;


class ST
{
    ll a[Nmax<<2];

public:
    void update(int node, int st, int dr, int pos, int val)
    {
        if(st == dr)
        {
            a[node] = val;
            return;
        }
        if(pos <= mid) update(left_son, st, mid, pos, val);
            else update(right_son, mid+1, dr, pos, val);

        a[node] = a[left_son] + a[right_son];
    }

    void init(int node, int st, int dr)
    {
        if(st == dr)
        {
            a[node] = C[st];
            return;
        }

        init(left_son, st, mid);
        init(right_son, mid+1, dr);

        a[node] = a[left_son] + a[right_son];
    }

    void spray(int node, int st, int dr, int L, int R)
    {
        if(!a[node]) return;
        if(R < st || dr < L) return;

        if(st == dr)
        {
            a[node] /= K;
            return;
        }

        spray(left_son, st, mid, L, R);
        spray(right_son, mid+1, dr, L, R);

        a[node] = a[left_son] + a[right_son];
    }

    ll query(int node, int st, int dr, int L, int R)
    {
        if(L <= st && dr <= R) return a[node];

        ll x = 0, y = 0;
        if(L <= mid) x = query(left_son, st, mid, L, R);
        if(mid < R) y = query(right_son, mid+1, dr, L, R);

        return x + y;
    }

} aint;

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i, x, y, tip, q;

    cin >> n >> q >> K;
    for(i=1; i<=n; ++i) cin >> C[i];

    aint.init(1, 1, n);

    while(q--)
    {
        cin >> tip >> x >> y;
        if(tip == 1) aint.update(1, 1, n, x, y);
            else if(tip == 2 && K > 1) aint.spray(1, 1, n, x, y);
                else if(tip == 3) cout << aint.query(1, 1, n, x, y) << '\n';
    }

    return 0;
}

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