oj.uz

Submission #124816

# Submission time Handle Problem Language Result Execution time Memory
124816 2019-07-04T02:58:38 Z nhimnam120 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 502 ms 3960 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,k;
int a[100005],node[400004];
void build(int i,int l,int r){
	if(l>r) return;
	if(l==r){
		node[i]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	node[i]=node[i*2]+node[i*2+1];
}
void update1(int i,int l,int r,int pos,int val){
	if(l>r||pos<l||pos>r) return;
	if(l==r){
		if(l==pos){
			a[l]=val;
			node[i]=val;
			return;
		}
		return;
	}
	int mid=(l+r)/2;
	if(pos<=mid) update1(i*2,l,mid,pos,val);
	else update1(i*2+1,mid+1,r,pos,val);
	node[i]=node[i*2]+node[i*2+1];
}
void update2(int i,int l,int r,int u,int v){
	if(node[i]==0||k==1) return;
	if(l==r){
		node[i]/=k;
		return;
	}
	int mid=(l+r)/2;
	if(u<=mid) update2(i*2,l,mid,u,v);
	if(mid<v) update2(i*2+1,mid+1,r,u,v);
	node[i]=node[i*2]+node[i*2+1];
}
int get(int i,int l,int r,int u,int v){
	if(l>r||u>r||v<l) return 0;
	if(u<=l&&v>=r) return node[i];
	int mid=(l+r)/2;
	int ans=0;
	if(u<=mid) ans+=get(i*2,l,mid,u,v);
	if(mid<v) ans+=get(i*2+1,mid+1,r,u,v);
	return ans;  
}
signed main(){
	cin>>n>>q>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(q--){
		int s;
		cin>>s;
		if(s==1){
			int u,v;
			cin>>u>>v;
			update1(1,1,n,u,v);
		}
		else if(s==2){
			int l,r;
			cin>>l>>r;
			update2(1,1,n,l,r);
		}
		else if(s==3){
			int l,r;
			cin>>l>>r;
			cout<<get(1,1,n,l,r)<<endl;
		}
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 2240 KB Output is correct
2 Correct 243 ms 2040 KB Output is correct
3 Correct 213 ms 3400 KB Output is correct
4 Correct 274 ms 3652 KB Output is correct
5 Correct 325 ms 3664 KB Output is correct
6 Correct 326 ms 3704 KB Output is correct
7 Correct 324 ms 3704 KB Output is correct
8 Correct 329 ms 3844 KB Output is correct
9 Correct 313 ms 3832 KB Output is correct
10 Correct 315 ms 3960 KB Output is correct
11 Correct 318 ms 3912 KB Output is correct
12 Correct 313 ms 3704 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 628 KB Output is correct
2 Correct 51 ms 1784 KB Output is correct
3 Correct 74 ms 1976 KB Output is correct
4 Correct 232 ms 1148 KB Output is correct
5 Correct 279 ms 3560 KB Output is correct
6 Correct 271 ms 3336 KB Output is correct
7 Correct 261 ms 3552 KB Output is correct
8 Correct 273 ms 3564 KB Output is correct
9 Correct 255 ms 3448 KB Output is correct
10 Correct 256 ms 3448 KB Output is correct
11 Correct 255 ms 3296 KB Output is correct
12 Correct 255 ms 3308 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 2168 KB Output is correct
2 Correct 289 ms 2296 KB Output is correct
3 Correct 240 ms 2180 KB Output is correct
4 Correct 327 ms 1656 KB Output is correct
5 Correct 402 ms 3564 KB Output is correct
6 Correct 415 ms 3548 KB Output is correct
7 Correct 401 ms 3636 KB Output is correct
8 Correct 458 ms 3576 KB Output is correct
9 Correct 419 ms 3652 KB Output is correct
10 Correct 439 ms 3732 KB Output is correct
11 Correct 394 ms 3828 KB Output is correct
12 Correct 502 ms 3700 KB Output is correct