oj.uz

Submission #48564

# Submission time Handle Problem Language Result Execution time Memory
48564 2018-05-16T13:02:39 Z Pajaraja Sterilizing Spray (JOI15_sterilizing) C++17
10 / 100
 1182 ms 68004 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;
	int s=(l+r)/2;
	upd(lt,rt,l,s,2*ind);
	upd(lt,rt,s+1,r,2*ind+1);
	relax(ind);
	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);
	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 Incorrect 7 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 619 ms 34408 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 181 ms 34408 KB Output is correct
2 Correct 269 ms 34408 KB Output is correct
3 Correct 315 ms 34408 KB Output is correct
4 Correct 613 ms 34408 KB Output is correct
5 Correct 1175 ms 67732 KB Output is correct
6 Correct 1182 ms 67732 KB Output is correct
7 Correct 863 ms 68004 KB Output is correct
8 Correct 1123 ms 68004 KB Output is correct
9 Correct 877 ms 68004 KB Output is correct
10 Correct 919 ms 68004 KB Output is correct
11 Correct 880 ms 68004 KB Output is correct
12 Correct 911 ms 68004 KB Output is correct

Subtask #4
0 / 75.0

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