oj.uz

Submission #124850

# Submission time Handle Problem Language Result Execution time Memory
124850 2019-07-04T04:27:03 Z TienDungz Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 92 ms 3448 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,k,q,u,v,x,st[405000],gt[100005];
void build(int index,int l,int r)
{
	if(l>r) return;
	if(l==r) 
	{
		st[index]=gt[l];
		return;
	}
	int mid=(l+r)/2;
	build(index*2,l,mid);
	build(index*2+1,mid+1,r);
	st[index]=st[index*2]+st[index*2+1];
}
void update1(int index,int l,int r,int pos,int val)
{
	if(r<pos||l>pos) return;
	if(l==r&&l==pos)
	{
		st[index]=val;
		return;
	}
	int mid=(l+r)/2;
	update1(index*2,l,mid,pos,val);
	update1(index*2+1,mid+1,r,pos,val);
	st[index]=st[index*2]+st[index*2+1];
}	
void update2(int index,int l,int r,int u,int v)
{
	if(r<u||l>v||st[index]==0||k==1) return;
	if(l==r)
	{
		st[index]=st[index]/k;
		return;
	}
	int mid=(l+r)/2;
	update2(index*2,l,mid,u,v);
	update2(index*2+1,mid+1,r,u,v);
	st[index]=st[index*2]+st[index*2+1];
}
int get(int index,int l,int r,int u,int v)
{
	if(r<u||l>v) return 0;
	if(u<=l&&r<=v) return st[index];
	int mid=(l+r)/2;
	return get(index*2,l,mid,u,v)+get(index*2+1,mid+1,r,u,v);
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>q>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>gt[i];
	}
	build(1,1,n);
	while(q--)
	{
		int type;
		cin>>type;
		if(type==1)
		{
			int a,b;
			cin>>a>>b;
			update1(1,1,n,a,b);
		}
		else if(type==2)
		{
			int l,r;
			cin>>l>>r;
			update2(1,1,n,l,r);
		}
		else if(type==3)
		{
			int l,r;
			cin>>l>>r;
			cout<<get(1,1,n,l,r)<<"\n";
		}
	}
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 3320 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 23 ms 888 KB Output is correct
2 Correct 16 ms 1272 KB Output is correct
3 Correct 21 ms 1456 KB Output is correct
4 Correct 59 ms 1952 KB Output is correct
5 Correct 72 ms 3192 KB Output is correct
6 Correct 77 ms 3192 KB Output is correct
7 Correct 69 ms 3448 KB Output is correct
8 Correct 78 ms 3192 KB Output is correct
9 Correct 69 ms 3064 KB Output is correct
10 Correct 69 ms 3064 KB Output is correct
11 Correct 67 ms 3192 KB Output is correct
12 Correct 71 ms 3084 KB Output is correct

Subtask #4
0 / 75.0

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