Submission #50853

#	Time	Username	Problem	Language	Result	Execution time	Memory
50853		faustaadp	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	2021 ms	106664 KiB

sterilizing

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,q,k,i,a[101010],ta,tb,ST[404040],j,v[404040],te;
set<ll> sT[404040];
set<ll>::iterator it;
void upd(ll aa,ll bb,ll cc,ll ee,ll ff)
{
	if(a[cc]==0)
	{
		if(sT[ee].count(cc))
			sT[ee].erase(cc);
	}
	else
	if(ff==1)
		sT[ee].insert(cc);
	if(aa==bb)
		ST[ee]=a[cc];
	else
	{
		ll ce=(aa+bb)/2;
		if(cc<=ce)
			upd(aa,ce,cc,ee*2,ff);
		else
			upd(ce+1,bb,cc,ee*2+1,ff);
		ST[ee]=ST[ee*2]+ST[ee*2+1];
	}
}
void cari(ll aa,ll bb,ll cc,ll dd,ll ee)
{
	if(bb<cc||dd<aa)
		return ;
	else
	if(cc<=aa&&bb<=dd)
	{
		te++;
		v[te]=ee;
	}
	else
	{
		ll ce=(aa+bb)/2;
		cari(aa,ce,cc,dd,ee*2);
		cari(ce+1,bb,cc,dd,ee*2+1);
	}
}
ll jum(ll aa,ll bb,ll cc,ll dd,ll ee)
{
	if(bb<cc||dd<aa)
		return 0;
	else
	if(cc<=aa&&bb<=dd)
		return ST[ee];
	else
	{
		ll ce=(aa+bb)/2;
		return jum(aa,ce,cc,dd,ee*2)+jum(ce+1,bb,cc,dd,ee*2+1);
	}
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q>>k;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		upd(1,n,i,1,1);
	}
	while(q--)
	{
		cin>>ta;
		if(ta==1)
		{
			cin>>ta>>tb;
			a[ta]=tb;
			upd(1,n,ta,1,1);
		}
		else
		if(ta==2)
		{
			cin>>ta>>tb;
			if(k==1)
				continue;
			te=0;
			cari(1,n,ta,tb,1);
			for(i=1;i<=te;i++)
			{
				vector<ll> tem;
				for(it=sT[v[i]].begin();it!=sT[v[i]].end();it++)
				{
					tem.pb(*it);
					a[*it]=a[*it]/k;
				}	
				for(j=0;j<tem.size();j++)
					upd(1,n,tem[j],1,0);				
			}
		}
		else
		{
			cin>>ta>>tb;
			cout<<jum(1,n,ta,tb,1)<<"\n";
		}
	}
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:97:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<tem.size();j++)
             ~^~~~~~~~~~~

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