Submission #1260158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260158		tvgk	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	120 ms	3668 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7;

ll tree[mxN * 4];
int n, a[mxN], dmg, q;

void Build(int j = 1, int l = 1, int r = n)
{
    if (l == r)
    {
        tree[j] = a[l];
        return;
    }

    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
    tree[j] = tree[j * 2] + tree[j * 2 + 1];
}

void Upd(int vt, int val, int j = 1, int l = 1, int r = n)
{
    if (vt > r || l > vt)
        return;

    if (l == r)
    {
        tree[j] = val;
        return;
    }

    int mid = (l + r) / 2;
    Upd(vt, val, j * 2, l, mid);
    Upd(vt, val, j * 2 + 1, mid + 1, r);
    tree[j] = tree[j * 2] + tree[j * 2 + 1];
}

void Divi(int u, int v, int j = 1, int l = 1, int r = n)
{
    if (u > r || l > v || !tree[j])
        return;

    if (l == r)
    {
        tree[j] /= dmg;
        return;
    }

    int mid = (l + r) / 2;
    Divi(u, v, j * 2, l, mid);
    Divi(u, v, j * 2 + 1, mid + 1, r);
    tree[j] = tree[j * 2] + tree[j * 2 + 1];
}

ll Get(int u, int v, int j = 1, int l = 1, int r = n)
{
    if (u > r || l > v)
        return 0;

    if (u <= l && r <= v)
        return tree[j];

    int mid = (l + r) / 2;
    return Get(u, v, j * 2, l, mid) + Get(u, v, j * 2 + 1, mid + 1, r);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> q >> dmg;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    Build();

    for (int i = 1; i <= q; i++)
    {
        int tt, l, r;
        cin >> tt >> l >> r;

        if (tt == 1)
            Upd(l, r);
        if (tt == 2 && dmg > 1)
            Divi(l, r);
        if (tt == 3)
            cout << Get(l, r) << '\n';
    }
}

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