Submission #292940

#	Time	Username	Problem	Language	Result	Execution time	Memory
292940		davooddkareshki	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	320 ms	8188 KiB

sterilizing

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

typedef long long ll;

const int maxn = 1e5+10;
const int mod = 1e9+7;
const ll inf = 1e9+10;

int n, m, k, q;
int a[maxn];
int sum[maxn<<2], mx[maxn<<2];

void build(int v = 1, int tl = 1, int tr = n)
{
    if(tl == tr)
    {
        mx[v] = sum[v] = a[tl];
        return;
    }

    int tm = (tl + tr) >> 1;
    build(v<<1, tl, tm);
    build(v<<1|1, tm+1, tr);
    mx[v] = max(mx[v<<1], mx[v<<1|1]);
    sum[v] = sum[v<<1] + sum[v<<1|1];
}

void DO(int l, int r, int v = 1, int tl = 1, int tr = n)
{
    if(mx[v] == 0 || l > r || k == 1) return;
    if(tl == tr)
    {
        mx[v] /= k;
        sum[v] /= k;
        return;
    }

    int tm = (tl + tr) >> 1;
    DO(l, min(tm,r), v<<1, tl, tm);
    DO(max(tm+1,l), r, v<<1|1, tm+1, tr);
    mx[v] = max(mx[v<<1], mx[v<<1|1]);
    sum[v] = sum[v<<1] + sum[v<<1|1];
}

void _set(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
    if(tl == tr)
    {
        mx[v] = sum[v] = val;
        return;
    }

    int tm = (tl + tr) >> 1;
    if(pos <= tm) _set(pos, val, v<<1, tl, tm);
    else          _set(pos, val, v<<1|1, tm+1, tr);
    mx[v] = max(mx[v<<1], mx[v<<1|1]);
    sum[v] = sum[v<<1] + sum[v<<1|1];
}

int sum_qu(int l, int r, int v = 1, int tl = 1, int tr = n)
{
    if(l > r) return 0;
    if(tl == l && tr == r) return sum[v];

    int tm = (tl + tr) >> 1;
    return sum_qu(l, min(tm,r), v<<1, tl, tm) +
            sum_qu(max(tm+1,l), r, v<<1|1, tm+1, tr);
}

signed main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

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

    while(q--)
    {
        int tp; cin>> tp;
        if(tp == 1)
        {
            int pos, val; cin>> pos >> val;
            _set(pos,val);
        }
        if(tp == 2)
        {
            int l, r; cin>> l >> r;
            DO(l,r);
        }
        if(tp == 3)
        {
            int l, r; cin>> l >> r;
            cout<< sum_qu(l,r) <<"\n";
        }
    }
}
/*
5 10 3
1 2 8 1 3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5
*/

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