oj.uz

Submission #739765

# Submission time Handle Problem Language Result Execution time Memory
739765 2023-05-11T09:01:36 Z bgnbvnbv Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 243 ms 8140 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll st[4*maxN],mx[4*maxN],n;
void update(ll pos,ll val,ll id=1,ll l=1,ll r=n)
{
    if(l==r)
    {
        st[id]=val;
        mx[id]=val;
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid) update(pos,val,id*2,l,mid);
    else update(pos,val,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
    mx[id]=max(mx[id*2],mx[id*2+1]);
}
ll k;
void upd(ll i,ll j,ll id=1,ll l=1,ll r=n)
{
    if(j<l||r<i) return;
    if(mx[id]==0) return;
    if(l==r)
    {
        st[id]=st[id]/k;
        mx[id]=mx[id]/k;
        return;
    }
    ll mid=l+r>>1;
    upd(i,j,id*2,l,mid);
    upd(i,j,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
    mx[id]=max(mx[id*2],mx[id*2+1]);
}
ll get(ll i,ll j,ll id=1,ll l=1,ll r=n)
{
    if(j<l||r<i) return 0;
    if(i<=l&&r<=j) return st[id];
    ll mid=l+r>>1;
    return get(i,j,id*2,l,mid)+get(i,j,id*2+1,mid+1,r);
}
ll q,a[maxN];
void solve()
{
    cin >> n >> q >> k;
    for(int i=1;i<=n;i++) cin >> a[i],update(i,a[i]);
    for(int i=1;i<=q;i++)
    {
        ll t;
        cin >> t;
        if(t==1)
        {
            ll pos,val;
            cin >> pos >> val;
            update(pos,val);
        }
        else if(t==2)
        {
            ll l,r;
            cin >> l >> r;
            if(k!=1)
            {
                upd(l,r);
            }
        }
        else
        {
            ll l,r;
            cin >> l >> r;
            cout << get(l,r)<<'\n';
        }
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

sterilizing.cpp: In function 'void update(ll, ll, ll, ll, ll)':
sterilizing.cpp:22:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     ll mid=l+r>>1;
      |            ~^~
sterilizing.cpp: In function 'void upd(ll, ll, ll, ll, ll)':
sterilizing.cpp:39:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     ll mid=l+r>>1;
      |            ~^~
sterilizing.cpp: In function 'll get(ll, ll, ll, ll, ll)':
sterilizing.cpp:49:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     ll mid=l+r>>1;
      |            ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 7 ms 572 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5112 KB Output is correct
2 Correct 40 ms 4612 KB Output is correct
3 Correct 46 ms 6988 KB Output is correct
4 Correct 52 ms 7656 KB Output is correct
5 Correct 61 ms 8068 KB Output is correct
6 Correct 62 ms 8100 KB Output is correct
7 Correct 61 ms 8140 KB Output is correct
8 Correct 64 ms 8124 KB Output is correct
9 Correct 56 ms 7992 KB Output is correct
10 Correct 60 ms 7996 KB Output is correct
11 Correct 60 ms 7932 KB Output is correct
12 Correct 63 ms 7984 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1032 KB Output is correct
2 Correct 15 ms 3036 KB Output is correct
3 Correct 21 ms 3144 KB Output is correct
4 Correct 43 ms 2736 KB Output is correct
5 Correct 60 ms 6636 KB Output is correct
6 Correct 64 ms 6648 KB Output is correct
7 Correct 55 ms 6708 KB Output is correct
8 Correct 62 ms 6672 KB Output is correct
9 Correct 56 ms 6504 KB Output is correct
10 Correct 60 ms 6548 KB Output is correct
11 Correct 59 ms 6500 KB Output is correct
12 Correct 63 ms 6476 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 4468 KB Output is correct
2 Correct 87 ms 4684 KB Output is correct
3 Correct 105 ms 4044 KB Output is correct
4 Correct 111 ms 3540 KB Output is correct
5 Correct 126 ms 7900 KB Output is correct
6 Correct 146 ms 7856 KB Output is correct
7 Correct 132 ms 7860 KB Output is correct
8 Correct 183 ms 7920 KB Output is correct
9 Correct 169 ms 7756 KB Output is correct
10 Correct 186 ms 7800 KB Output is correct
11 Correct 136 ms 7888 KB Output is correct
12 Correct 243 ms 7760 KB Output is correct