oj.uz

Submission #48562

# Submission time Handle Problem Language Result Execution time Memory
48562 2018-05-16T12:56:31 Z Pajaraja Sterilizing Spray (JOI15_sterilizing) C++17
0 / 100
 618 ms 70636 KB 
#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)
{
	int rez=0;
	if(l>=lt && r<=rt)  return seg[cl[ind]][ind];
	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);
	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

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:48: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:52: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 618 ms 36932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 36932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 221 ms 70636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -