oj.uz

Submission #48565

# Submission time Handle Problem Language Result Execution time Memory
48565 2018-05-16T13:04:22 Z Pajaraja Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 1190 ms 68912 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 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

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
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 35436 KB Output is correct
2 Correct 255 ms 35436 KB Output is correct
3 Correct 312 ms 35436 KB Output is correct
4 Correct 656 ms 35436 KB Output is correct
5 Correct 1190 ms 68708 KB Output is correct
6 Correct 1183 ms 68708 KB Output is correct
7 Correct 908 ms 68836 KB Output is correct
8 Correct 1184 ms 68836 KB Output is correct
9 Correct 971 ms 68836 KB Output is correct
10 Correct 956 ms 68836 KB Output is correct
11 Correct 942 ms 68892 KB Output is correct
12 Correct 942 ms 68912 KB Output is correct

Subtask #4
0 / 75.0

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