Submission #239928

#	Time	Username	Problem	Language	Result	Execution time	Memory
239928		MvC	Sterilizing Spray (JOI15_sterilizing)	C++11	100 / 100	721 ms	71800 KiB

sterilizing

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
using namespace std;
int n,q,l,r,a[nmax],k,lzy[4*nmax],tp,i;
ll st[4*nmax],vl[4*nmax][32],fw[nmax];
void push(int nod,int l,int r)
{
    if(!lzy[nod])return;
    lzy[nod]=min(lzy[nod],30);
    int i;
    for(i=0;i+lzy[nod]<=30;i++)vl[nod][i]=vl[nod][i+lzy[nod]];
    for(;i<=30;i++)vl[nod][i]=0;
    ll pw=1;
    st[nod]=0;
    for(i=0;i<=30;i++)
    {
		st[nod]+=pw*vl[nod][i];
		if(pw*1LL*k>=inf)break;
		pw*=k;
	}
    if(l!=r)
    {
    	lzy[nod*2]+=lzy[nod];
		lzy[nod*2+1]+=lzy[nod];
	}
    lzy[nod]=0;
}
void upd(int nod,int l,int r,int tl,int tr)
{
    push(nod,l,r);
    if(tl<=l && r<=tr)
	{
        lzy[nod]++;
        push(nod,l,r);
        return;
    }
    int mid=(l+r)/2;
    if(tl<=mid)upd(nod*2,l,mid,tl,tr);
    if(mid<tr)upd(nod*2+1,mid+1,r,tl,tr);
    push(nod*2,l,mid);
	push(nod*2+1,mid+1,r);
	for(int i=0;i<=30;i++)vl[nod][i]=vl[nod*2][i]+vl[nod*2+1][i];
    st[nod]=st[nod*2]+st[nod*2+1];
}
void chg(int nod,int l,int r,int p,int v)
{
    push(nod,l,r);
    if(l==r)
	{
		st[nod]=v;
		int i=0;
        while(v)
        {
			vl[nod][i++]=v%k;
			v/=k;
		}
		for(;i<=30;i++)vl[nod][i]=0;
        return;
    }
    int mid=(l+r)/2;
    if(p<=mid)chg(nod*2,l,mid,p,v);
    else chg(nod*2+1,mid+1,r,p,v);
    push(nod*2,l,mid);
	push(nod*2+1,mid+1,r);
	for(int i=0;i<=30;i++)vl[nod][i]=vl[nod*2][i]+vl[nod*2+1][i];
    st[nod]=st[nod*2]+st[nod*2+1];
}
ll qry(int nod,int l,int r,int tl,int tr)
{
    push(nod,l,r);
    if(l>tr || r<tl)return 0;
    if(tl<=l && r<=tr)return st[nod];
    int mid=(l+r)/2;
    return qry(nod*2,l,mid,tl,tr)+qry(nod*2+1,mid+1,r,tl,tr);
}
void ufw(int i,ll v)
{
	for(;i<=n;i+=i&(-i))fw[i]+=v;
}
ll qfw(int i)
{
	ll ans=0;
	for(;i>=1;i-=i&(-i))ans+=fw[i];
	return ans;
}
ll query(int l,int r)
{
	ll ans=qfw(r);
	if(l>1)ans-=qfw(l-1);
	return ans;
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>q>>k;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		if(k!=1)chg(1,1,n,i,a[i]);
		else ufw(i,a[i]);
	}
	while(q--)
	{
		cin>>tp>>l>>r;
		if(tp==1)
		{
			if(k!=1)
			{
				a[l]=r;
				chg(1,1,n,l,a[l]);
			}
			else
			{
				ufw(l,-a[l]);
				a[l]=r;
				ufw(l,a[l]);
			}
		}
		else if(tp==2 && k!=1)upd(1,1,n,l,r);
		else if(tp==3)
		{
			if(k==1)cout<<query(l,r)<<'\n';
			else cout<<qry(1,1,n,l,r)<<'\n';
		}
	}
	return 0;
}
/*
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