Submission #48566

#	Time	Username	Problem	Language	Result	Execution time	Memory
48566		Pajaraja	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	1278 ms	117092 KiB

sterilizing

#include <bits/stdc++.h>
#define MAXN 100007
#define MAXL 32
using namespace std;
long long seg[MAXL][4*MAXN];
int cl[4*MAXN],k;
void relax(int ind)
{
	cl[2*ind]+=cl[ind];
	cl[2*ind+1]+=cl[ind];
	cl[ind]=0;
	for(int i=0;i<MAXL;i++) seg[i][ind]=((i+cl[2*ind]<MAXL)?seg[i+cl[2*ind]][2*ind]:0)+((i+cl[2*ind+1]<MAXL)?seg[i+cl[2*ind+1]][2*ind+1]:0);
}
void pos(int a,int v,int l,int r,int ind)
{
	if(l==r) {for(int i=0;i<MAXL;i++) {seg[i][ind]=a; a/=k;} cl[ind]=0; return;}
	int s=(l+r)/2;
	relax(ind);
	if(v<=s) pos(a,v,l,s,2*ind);
	else pos(a,v,s+1,r,2*ind+1);
	for(int i=0;i<MAXL;i++) seg[i][ind]=((i+cl[2*ind]<MAXL)?seg[i+cl[2*ind]][2*ind]:0)+((i+cl[2*ind+1]<MAXL)?seg[i+cl[2*ind+1]][2*ind+1]:0);
}
void upd(int lt,int rt,int l,int r,int ind)
{
	if(l>=lt && r<=rt) {cl[ind]++; return;}
	if(r<lt || l>rt) return;
	relax(ind);
	int s=(l+r)/2;
	upd(lt,rt,l,s,2*ind);
	upd(lt,rt,s+1,r,2*ind+1);
	for(int i=0;i<MAXL;i++) seg[i][ind]=((i+cl[2*ind]<MAXL)?seg[i+cl[2*ind]][2*ind]:0)+((i+cl[2*ind+1]<MAXL)?seg[i+cl[2*ind+1]][2*ind+1]:0);
}
long long sum(int lt,int rt,int l,int r,int ind)
{
	long long rez=0;
	if(l>=lt && r<=rt)  return cl[ind]<MAXL?seg[cl[ind]][ind]:0;
	if(r<lt || l>rt) return 0;
	relax(ind);
	int s=(l+r)/2;
	rez+=sum(lt,rt,l,s,2*ind);
	rez+=sum(lt,rt,s+1,r,2*ind+1);
	return rez;
}
int main()
{
	int n,q,t;
	scanf("%d%d%d",&n,&q,&k);
	fill(cl,cl+MAXN,0);
	for(int i=1;i<=n;i++) {scanf("%d",&t); pos(t,i,1,n,1);}
	while(q--)
	{
		int a,b;
		scanf("%d%d%d",&t,&a,&b);
		if(t==1) pos(b,a,1,n,1);
		if(t==2) if(k!=1) upd(a,b,1,n,1);
		if(t==3) printf("%lld\n",sum(a,b,1,n,1));
	}
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&q,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~
sterilizing.cpp:49:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) {scanf("%d",&t); pos(t,i,1,n,1);}
                         ~~~~~^~~~~~~~~
sterilizing.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&t,&a,&b);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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