제출 #559941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
559941		maeola	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	716 ms	62108 KiB

sterilizing

// trans rights

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int N, Q, K;
constexpr int H = 33;

struct Package
{
    ll P[H];
    void roll(int g)
    {
        if (K == 1)
            return;
        g = min(g, H);
        for (int i = 0; i < H - g; i++)
            P[i] = P[i + g];
        for (int i = H - g; i < H; i++)
            P[i] = 0;
    }
};

Package combine(const Package& a, const Package& b)
{
    Package c;
    for (int i = 0; i < H; i++)
        c.P[i] = a.P[i] + b.P[i];
    return c;
}

struct Node 
{
    int l, r;
    Node *lc, *rc;
    int rolln = 0;
    Package pk;
    Node(int l, int r) : l(l), r(r), lc(0), rc(0)
    {
        if (l != r)
        {
            int m = l + (r - l) / 2;
            lc = new Node(l, m);
            rc = new Node(m + 1, r);
        }
    }
    void clean()
    {
        pk.roll(rolln);
        if (l != r)
        {
            lc->rolln += rolln;
            rc->rolln += rolln;
        }
        rolln = 0;
    }
    void update(int p, int x)
    {
        clean();
        if (p < l or p > r)
            return;
        if (l == r)
        {
            pk.P[0] = x;
            for (int i = 1; i < H; i++)
                pk.P[i] = pk.P[i - 1] / K;
            return;
        }
        lc->update(p, x);
        rc->update(p, x);
        pk = combine(lc->pk, rc->pk);
    }
    void spray(int ql, int qr)
    {
        clean();
        if (qr < l or ql > r)
            return;
        if (ql <= l and qr >= r)
        {
            rolln++;
            clean();
            return;
        }
        lc->spray(ql, qr);
        rc->spray(ql, qr);
        pk = combine(lc->pk, rc->pk);
    }
    ll query(int ql, int qr)
    {
        clean();
        if (qr < l or ql > r)
            return 0;
        if (ql <= l and qr >= r)
            return pk.P[0];
        return lc->query(ql, qr) + rc->query(ql, qr);
    }
};

int main(int argc, const char *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> Q >> K;
    Node *root = new Node(1, N);
    for (int i = 1; i <= N; i++)
    {
        int a;
        cin >> a;
        root->update(i, a);
    }
    for (int k = 0; k < Q; k++)
    {
        int s, t, u;
        cin >> s >> t >> u;
        if (s == 1)
        {
            root->update(t, u);
        }else if (s == 2)
        {
            root->spray(t, u);
        }else if(s == 3)
        {
            cout << root->query(t, u) << '\n';
        }
    }
    return 0;
}

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