oj.uz

Submission #124819

# Submission time Handle Problem Language Result Execution time Memory
124819 2019-07-04T03:03:52 Z nhimnam120 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 356 ms 4016 KB 
#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+5;
long long n,q,k;
long long inp[N];
long long node[N*4];
void build_tree(long long id,long long l ,long long r){
	if(l>r){
		return;
	}
	if(l==r){
		node[id] = inp[l];
		return;
	}
	int mid=(l+r)/2;
	build_tree(id*2,l,mid);
	build_tree(id*2+1,mid+1,r);
	node[id] = node[id*2] + node[id*2+1];
}
void upd(long long id, long long l, long long r ,long long pos, long long val){
	if(r<pos||l>pos){
		return;
	}
	if(l==r){
		node[id]=val;
		return;
	}
	long long mid=(l+r)/2;
	if(pos<=mid){
		upd(id*2,l,mid,pos,val);
	}
	else{
		upd(id*2+1,mid+1,r,pos,val);
	}
	node[id] = node[id*2] + node[id*2+1];
}
void upd2(long long id, long long l ,long long r, long long u, long long v){
	if(node[id]==0||k==1){
		return;
	}
	if(r<u||l>v){
		return;
	}
	if(l==r){
		node[id] = node[id]/k;
		return;
	}
	long long mid=(l+r)/2;
	if(u<=mid){
		upd2(id*2,l,mid,u,v);
	}
	if(v>mid){
		upd2(id*2+1,mid+1,r,u,v);
	}
	node[id] = node[id*2] + node[id*2+1];
}
long long get(long long id, long long l, long long r, long long u, long long v){
	if(l>v||r<u){
		return 0;
	}
	if(l>=u&&r<=v){
		return node[id];
	}
	long long mid = (l+r)/2;
	long long ans=0;
	if(u<=mid){
		ans = ans + get(id*2,l,mid,u,v);
	}
	if(v>mid){
		ans = ans + get(id*2+1,mid+1,r,u,v);
	}
	return ans;
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q >> k;
	for(int i=1;i<=n;i++){
		cin >> inp[i];
	}
	build_tree(1,1,n);
	int s,t,u;
	while(q--){
		cin >> s >> t >> u;
		if(s==1){
			upd(1,1,n,t,u);
		}
		if(s==2){
			upd2(1,1,n,t,u);
		}
		if(s==3){
			cout << get(1,1,n,t,u)<<endl;
		}
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 2324 KB Output is correct
2 Correct 131 ms 2296 KB Output is correct
3 Correct 106 ms 3644 KB Output is correct
4 Correct 130 ms 3832 KB Output is correct
5 Correct 161 ms 3804 KB Output is correct
6 Correct 162 ms 3860 KB Output is correct
7 Correct 163 ms 3960 KB Output is correct
8 Correct 161 ms 3912 KB Output is correct
9 Correct 161 ms 3880 KB Output is correct
10 Correct 160 ms 3844 KB Output is correct
11 Correct 164 ms 4016 KB Output is correct
12 Correct 156 ms 3796 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 504 KB Output is correct
2 Correct 28 ms 1656 KB Output is correct
3 Correct 43 ms 1784 KB Output is correct
4 Correct 139 ms 1144 KB Output is correct
5 Correct 158 ms 3320 KB Output is correct
6 Correct 160 ms 3284 KB Output is correct
7 Correct 152 ms 3320 KB Output is correct
8 Correct 159 ms 3320 KB Output is correct
9 Correct 152 ms 3284 KB Output is correct
10 Correct 151 ms 3244 KB Output is correct
11 Correct 153 ms 3320 KB Output is correct
12 Correct 152 ms 3320 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 1912 KB Output is correct
2 Correct 172 ms 2124 KB Output is correct
3 Correct 165 ms 2076 KB Output is correct
4 Correct 214 ms 1712 KB Output is correct
5 Correct 245 ms 3816 KB Output is correct
6 Correct 258 ms 3704 KB Output is correct
7 Correct 232 ms 3704 KB Output is correct
8 Correct 296 ms 3740 KB Output is correct
9 Correct 264 ms 3768 KB Output is correct
10 Correct 288 ms 3704 KB Output is correct
11 Correct 238 ms 3740 KB Output is correct
12 Correct 356 ms 3804 KB Output is correct