oj.uz

Submission #124852

# Submission time Handle Problem Language Result Execution time Memory
124852 2019-07-04T04:29:05 Z TienDungz Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 265 ms 6008 KB 
#include<bits/stdc++.h>
#define int long long
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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 6 ms 504 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 6 ms 508 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 6 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2168 KB Output is correct
2 Correct 57 ms 3732 KB Output is correct
3 Correct 50 ms 4984 KB Output is correct
4 Correct 65 ms 5624 KB Output is correct
5 Correct 77 ms 5860 KB Output is correct
6 Correct 79 ms 5880 KB Output is correct
7 Correct 76 ms 5880 KB Output is correct
8 Correct 77 ms 5876 KB Output is correct
9 Correct 72 ms 5896 KB Output is correct
10 Correct 72 ms 5880 KB Output is correct
11 Correct 71 ms 6008 KB Output is correct
12 Correct 71 ms 5896 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 632 KB Output is correct
2 Correct 16 ms 1784 KB Output is correct
3 Correct 21 ms 1784 KB Output is correct
4 Correct 57 ms 1144 KB Output is correct
5 Correct 72 ms 3192 KB Output is correct
6 Correct 72 ms 3192 KB Output is correct
7 Correct 68 ms 3396 KB Output is correct
8 Correct 73 ms 3284 KB Output is correct
9 Correct 66 ms 3320 KB Output is correct
10 Correct 66 ms 3320 KB Output is correct
11 Correct 66 ms 3292 KB Output is correct
12 Correct 71 ms 3192 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 2024 KB Output is correct
2 Correct 102 ms 3704 KB Output is correct
3 Correct 118 ms 2968 KB Output is correct
4 Correct 127 ms 3064 KB Output is correct
5 Correct 150 ms 5692 KB Output is correct
6 Correct 170 ms 5568 KB Output is correct
7 Correct 147 ms 5640 KB Output is correct
8 Correct 207 ms 5800 KB Output is correct
9 Correct 190 ms 5728 KB Output is correct
10 Correct 198 ms 5624 KB Output is correct
11 Correct 152 ms 5784 KB Output is correct
12 Correct 265 ms 5724 KB Output is correct