oj.uz

Submission #124817

# Submission time Handle Problem Language Result Execution time Memory
124817 2019-07-04T03:02:55 Z nhimnam120 Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 157 ms 2176 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,k;
int inp[N];
int node[N*4];
void build_tree(int id,int l ,int 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(int id, int l, int r ,int pos, int val){
	if(r<pos||l>pos){
		return;
	}
	if(l==r){
		node[id]=val;
		return;
	}
	int 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(int id, int l ,int r, int u, int v){
	if(node[id]==0||k==1){
		return;
	}
	if(r<u||l>v){
		return;
	}
	if(l==r){
		node[id] = node[id]/k;
		return;
	}
	int 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];
}
int get(int id, int l, int r, int u, int v){
	if(l>v||r<u){
		return 0;
	}
	if(l>=u&&r<=v){
		return node[id];
	}
	int mid = (l+r)/2;
	int 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 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 143 ms 1528 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 58 ms 632 KB Output is correct
2 Correct 28 ms 1176 KB Output is correct
3 Correct 42 ms 1272 KB Output is correct
4 Correct 139 ms 1080 KB Output is correct
5 Correct 156 ms 1960 KB Output is correct
6 Correct 155 ms 2040 KB Output is correct
7 Correct 149 ms 2176 KB Output is correct
8 Correct 157 ms 2068 KB Output is correct
9 Correct 150 ms 2040 KB Output is correct
10 Correct 150 ms 1956 KB Output is correct
11 Correct 156 ms 2084 KB Output is correct
12 Correct 150 ms 2168 KB Output is correct

Subtask #4
0 / 75.0

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