Submission #1181287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181287		vnedu	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	310 ms	7752 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 1e5 + 15;
const int Q = 1e5 + 15;

struct Query
{
    int s,t,u;
    Query() {}
    void input()
    {
        cin>>s>>t>>u;
    }
} query[Q];

int n,q,a[N],k;
namespace sub1
{
    bool check()
    {
        return max(n,q)<=3000;
    }
    void solve()
    {
//        cout<<k;
//        return;
        for (int i=1; i<=q; ++i)
        {
            if (query[i].s==1) a[query[i].t]=query[i].u;
            else if (query[i].s==2)
            {
//                cout<<query[i].t<<' '<<query[i].u<<'\n';
//                return;
                for (int j=query[i].t; j<=query[i].u; ++j)
                {
//                    cout<<1<<' ';
                    a[j]/=k;
                }
            }
            else
            {
                ll ans=0;
                for (int j=query[i].t; j<=query[i].u; ++j)
                {
//                    cout<<1<<' ';
                    ans+=a[j];
                }
                cout<<ans<<'\n';
            }
        }
    }
}
namespace subfull
{
    set<int> s;
    ll bit[N];
    void add(int x, ll val)
    {
        while (x<=n)
        {
            bit[x]+=val;
            x+=x&-x;
        }
    }
    ll get(int x)
    {
        ll ans=0;
        while (x>=1)
        {
            ans+=bit[x];
            x-=x&-x;
        }
        return ans;
    }
    void solve()
    {
        for (int i=1; i<=n; ++i)
        {
            if (a[i]!=0)
            {
                s.insert(i);
                add(i,a[i]);
            }
        }
        for (int tri=1; tri<=q; ++tri)
        {
            Query &cm=query[tri];
            if(cm.s==1)
            {
                ll newVal=cm.u;
                add(cm.t,newVal-a[cm.t]);
                a[cm.t]=newVal;
                if (newVal>0) s.insert(cm.t);
                else s.erase(cm.t);
            }
            else if(cm.s==2)
            {
                if (k==1) continue;
                int lst=cm.t;
                while(1)
                {
                    auto it=s.lower_bound(lst);
                    if (it==s.end() || (*it)>cm.u) break;
                    int pos=(*it);
                    ll newVal=a[pos]/k;
                    add(pos,newVal-a[pos]);
                    a[pos]=newVal;
                    if (newVal==0) s.erase(it);
                    lst=pos+1;
                }
            }
            else
            {
                cout<<get(cm.u)-get(cm.t-1)<<'\n';
            }
        }
    }
}
void solve()
{
    cin>>n>>q>>k;
    for (int i=1; i<=n; ++i) cin>>a[i];
    for (int i=1; i<=q; ++i) query[i].input();
    if (sub1::check()) return void(sub1::solve());
    return void(subfull::solve());
}

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

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

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