oj.uz

Submission #124800

# Submission time Handle Problem Language Result Execution time Memory
124800 2019-07-04T02:14:51 Z gaoxam123 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 499 ms 3916 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 11 ms 376 KB Output is correct
5 Correct 13 ms 380 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 13 ms 376 KB Output is correct
8 Correct 13 ms 376 KB Output is correct
9 Correct 14 ms 376 KB Output is correct
10 Correct 13 ms 380 KB Output is correct
11 Correct 13 ms 376 KB Output is correct
12 Correct 13 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 2144 KB Output is correct
2 Correct 244 ms 2040 KB Output is correct
3 Correct 221 ms 3436 KB Output is correct
4 Correct 281 ms 3448 KB Output is correct
5 Correct 491 ms 3696 KB Output is correct
6 Correct 324 ms 3704 KB Output is correct
7 Correct 325 ms 3608 KB Output is correct
8 Correct 325 ms 3916 KB Output is correct
9 Correct 309 ms 3704 KB Output is correct
10 Correct 310 ms 3704 KB Output is correct
11 Correct 312 ms 3668 KB Output is correct
12 Correct 318 ms 3812 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 632 KB Output is correct
2 Correct 52 ms 1704 KB Output is correct
3 Correct 99 ms 1800 KB Output is correct
4 Correct 244 ms 1016 KB Output is correct
5 Correct 280 ms 3320 KB Output is correct
6 Correct 269 ms 3192 KB Output is correct
7 Correct 277 ms 3324 KB Output is correct
8 Correct 270 ms 3420 KB Output is correct
9 Correct 257 ms 3364 KB Output is correct
10 Correct 256 ms 3224 KB Output is correct
11 Correct 272 ms 3332 KB Output is correct
12 Correct 255 ms 3192 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 1912 KB Output is correct
2 Correct 290 ms 2064 KB Output is correct
3 Correct 238 ms 1912 KB Output is correct
4 Correct 324 ms 1528 KB Output is correct
5 Correct 403 ms 3448 KB Output is correct
6 Correct 418 ms 3452 KB Output is correct
7 Correct 394 ms 3616 KB Output is correct
8 Correct 453 ms 3576 KB Output is correct
9 Correct 420 ms 3576 KB Output is correct
10 Correct 436 ms 3576 KB Output is correct
11 Correct 390 ms 3500 KB Output is correct
12 Correct 499 ms 3576 KB Output is correct