제출 #1289957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289957		phuchung	Sterilizing Spray (JOI15_sterilizing)	C++20	80 / 100	5092 ms	4512 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
const int max_n = (int)1e5;
int n, q, k, a[max_n + 5];
long long sum[(max_n << 2) + 5];
void inp(void)
{
    cin >> n >> q >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
}
struct seg
{
    void init(void)
    {
      for (int i = 0; i < (max_n << 2) + 5; ++i) sum[i] = 0;
    }
    void build(const int &l, const int &r, const int &pos)
    {
        if (l == r) sum[pos] = a[l];
            else
            {
                const int mid = (l + r) >> 1;
                build(l, mid, pos << 1);
                build(mid + 1, r, (pos << 1) | 1);
                sum[pos] = sum[pos << 1] + sum[(pos << 1) | 1];
            }
    }
    void update(const int &base_l, const int &base_r, const int &k, const int &val, const int &pos)
    {
        if (base_r < k || base_l > k) return;
        if (base_l == base_r)
        {
            sum[pos] = val;
            return;
        }
        const int mid = (base_l + base_r) >> 1;
        update(base_l, mid, k, val, pos << 1);
        update(mid + 1, base_r, k, val, (pos << 1) | 1);
        sum[pos] = sum[pos << 1] + sum[(pos << 1) | 1];
    }
    void update_range(const int &base_l, const int &base_r, const int &l, const int &r, const int &pos)
    {
        if (base_l > r || base_r < l || !sum[pos]) return;
        if (base_l == base_r)
        {
            sum[pos]/=k;
            return;
        }
        const int mid = (base_l + base_r) >> 1;
        update_range(base_l, mid, l, r, pos << 1);
        update_range(mid + 1, base_r, l, r, (pos << 1) | 1);
        sum[pos] = sum[pos << 1] + sum[(pos << 1) | 1];
    }
    long long get_val(const int &base_l, const int &base_r, const int &l, const int &r, const int &pos)
    {
        if (base_r < l || base_l > r) return 0;
        if (base_l >= l && base_r <= r) return sum[pos];
        const int mid = (base_l + base_r) >> 1;
        return get_val(base_l, mid, l, r, pos << 1) + get_val(mid + 1, base_r, l, r, (pos << 1) | 1);
    }
}t;
void process(void)
{
    t.init();
    t.build(1, n, 1);
    int type, l, r;
    while (q--)
    {
        cin >> type >> l >> r;
        if (type == 1)
        {
            t.update(1, n, l, r, 1);
        }
            else if (type == 2)
            {
                t.update_range(1, n, l, r, 1);
            }
                else
                {
                    cout << t.get_val(1, n, l, r, 1) << '\n';
                }
    }
}
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    inp();
    process();
}

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