oj.uz

Submission #124815

# Submission time Handle Problem Language Result Execution time Memory
124815 2019-07-04T02:57:40 Z nhimnam120 Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 5000 ms 1960 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(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 4996 ms 1668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 484 KB Output is correct
2 Correct 724 ms 1144 KB Output is correct
3 Correct 1141 ms 1212 KB Output is correct
4 Correct 2551 ms 1136 KB Output is correct
5 Execution timed out 5090 ms 1960 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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