oj.uz

Submission #388641

# Submission time Handle Problem Language Result Execution time Memory
388641 2021-04-12T11:03:43 Z MasterTaster Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 432 ms 9560 KB 
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
#define MAXN 100010

using namespace std;

int n, q, k;
ll a[MAXN], bit[MAXN];
set<int> koji;

void upd(int x, ll v)
{
    while (x<MAXN)
    {
        bit[x]+=v;
        x+=x&(-x);
    }
}
ll sum(int x)
{
    ll ret=0;
    while (x)
    {
        ret+=bit[x];
        x-=x&(-x);
    }
    return ret;
}

int main()
{
    cin>>n>>q>>k;

    for (int i=1; i<=n; i++) { cin>>a[i]; upd(i, a[i]); if (a[i]) koji.insert(i); }

    while (q--)
    {
        int t; cin>>t;
        if (t==1)
        {
            ll x, v; cin>>x>>v;
            upd(x, v-a[x]);
            if (v) koji.insert(x);
            a[x]=v;
        }
        else if (t==2)
        {
            int l, r; cin>>l>>r;
            if (k==1) continue;
            for (auto it=koji.lower_bound(l); it!=koji.end() && (*it)<=r; it++)
            {
                int x=*it;
                //cout<<x<<" ala "<<a[x]<<endl;
                if (a[x]==0) continue;

                upd(x, a[x]/k-a[x]);
                a[x]/=k;
            }
            for (auto it=koji.lower_bound(l); it!=koji.end() && (*it)<=r; it++)
            {
                int x=*it;
                if (a[x]==0) koji.erase(it);
            }
        }
        else
        {
            int l, r; cin>>l>>r;
            cout<<sum(r)-sum(l-1)<<endl;
        }

        /*for (int i=1; i<=n; i++) cout<<a[i]<<" ";
        cout<<endl;
        for (auto it:koji) cout<<(it)<<" ";
        cout<<endl;*/
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 332 KB Output is correct
2 Correct 3 ms 316 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 8 ms 460 KB Output is correct
5 Correct 11 ms 588 KB Output is correct
6 Correct 8 ms 588 KB Output is correct
7 Correct 9 ms 588 KB Output is correct
8 Correct 9 ms 576 KB Output is correct
9 Correct 10 ms 572 KB Output is correct
10 Correct 9 ms 588 KB Output is correct
11 Correct 9 ms 588 KB Output is correct
12 Correct 9 ms 588 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 5696 KB Output is correct
2 Correct 163 ms 4420 KB Output is correct
3 Correct 148 ms 7060 KB Output is correct
4 Correct 189 ms 8900 KB Output is correct
5 Correct 235 ms 9456 KB Output is correct
6 Correct 236 ms 9412 KB Output is correct
7 Correct 223 ms 9372 KB Output is correct
8 Correct 241 ms 9560 KB Output is correct
9 Correct 222 ms 9336 KB Output is correct
10 Correct 216 ms 9328 KB Output is correct
11 Correct 223 ms 9512 KB Output is correct
12 Correct 245 ms 9316 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 956 KB Output is correct
2 Correct 35 ms 2328 KB Output is correct
3 Correct 53 ms 2488 KB Output is correct
4 Correct 137 ms 2416 KB Output is correct
5 Correct 213 ms 5592 KB Output is correct
6 Correct 172 ms 5632 KB Output is correct
7 Correct 177 ms 6108 KB Output is correct
8 Correct 169 ms 5572 KB Output is correct
9 Correct 181 ms 5464 KB Output is correct
10 Correct 173 ms 5576 KB Output is correct
11 Correct 161 ms 5468 KB Output is correct
12 Correct 163 ms 5444 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 5140 KB Output is correct
2 Correct 188 ms 5464 KB Output is correct
3 Correct 177 ms 4392 KB Output is correct
4 Correct 205 ms 4164 KB Output is correct
5 Correct 279 ms 9364 KB Output is correct
6 Correct 285 ms 9284 KB Output is correct
7 Correct 272 ms 9344 KB Output is correct
8 Correct 432 ms 9208 KB Output is correct
9 Correct 288 ms 9160 KB Output is correct
10 Correct 349 ms 9172 KB Output is correct
11 Correct 275 ms 9060 KB Output is correct
12 Correct 399 ms 9168 KB Output is correct