Submission #1289953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289953		phuchung	Sterilizing Spray (JOI15_sterilizing)	C++17	5 / 100	5094 ms	4576 KiB

sterilizing

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

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