oj.uz

Submission #48566

# Submission time Handle Problem Language Result Execution time Memory
48566 2018-05-16T13:13:25 Z Pajaraja Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1278 ms 117092 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)
{
	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

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

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1016 KB Output is correct
2 Correct 6 ms 1640 KB Output is correct
3 Correct 8 ms 2264 KB Output is correct
4 Correct 14 ms 2284 KB Output is correct
5 Correct 21 ms 3488 KB Output is correct
6 Correct 21 ms 3608 KB Output is correct
7 Correct 20 ms 3608 KB Output is correct
8 Correct 20 ms 3796 KB Output is correct
9 Correct 20 ms 3844 KB Output is correct
10 Correct 20 ms 4040 KB Output is correct
11 Correct 21 ms 4104 KB Output is correct
12 Correct 20 ms 4300 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 35676 KB Output is correct
2 Correct 480 ms 37220 KB Output is correct
3 Correct 722 ms 72308 KB Output is correct
4 Correct 843 ms 74492 KB Output is correct
5 Correct 1012 ms 77124 KB Output is correct
6 Correct 987 ms 79476 KB Output is correct
7 Correct 952 ms 81900 KB Output is correct
8 Correct 967 ms 84336 KB Output is correct
9 Correct 801 ms 86520 KB Output is correct
10 Correct 764 ms 88988 KB Output is correct
11 Correct 781 ms 91304 KB Output is correct
12 Correct 800 ms 93652 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 93652 KB Output is correct
2 Correct 253 ms 93652 KB Output is correct
3 Correct 329 ms 93652 KB Output is correct
4 Correct 624 ms 93652 KB Output is correct
5 Correct 1268 ms 93652 KB Output is correct
6 Correct 1244 ms 93652 KB Output is correct
7 Correct 962 ms 93652 KB Output is correct
8 Correct 1255 ms 93652 KB Output is correct
9 Correct 944 ms 93652 KB Output is correct
10 Correct 946 ms 93652 KB Output is correct
11 Correct 956 ms 93652 KB Output is correct
12 Correct 974 ms 93652 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 93652 KB Output is correct
2 Correct 774 ms 93652 KB Output is correct
3 Correct 536 ms 93652 KB Output is correct
4 Correct 662 ms 93652 KB Output is correct
5 Correct 1268 ms 100368 KB Output is correct
6 Correct 1199 ms 103016 KB Output is correct
7 Correct 1278 ms 105252 KB Output is correct
8 Correct 1208 ms 107828 KB Output is correct
9 Correct 918 ms 110028 KB Output is correct
10 Correct 947 ms 112484 KB Output is correct
11 Correct 958 ms 114912 KB Output is correct
12 Correct 936 ms 117092 KB Output is correct