oj.uz

Submission #124811

# Submission time Handle Problem Language Result Execution time Memory
124811 2019-07-04T02:47:25 Z nhimnam120 Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 5000 ms 3320 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;
	upd(id*2,l,mid,pos,val);
	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(r<u||l>v){
		return;
	}
	if(l==r){
		node[id] = node[id]/k;
		return;
	}
	long long mid=(l+r)/2;
	upd2(id*2,l,mid,u,v);
	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;
	return get(id*2,l,mid,u,v) + get(id*2+1,mid+1,r,u,v);
}
signed main(){
	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 8 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 16 ms 376 KB Output is correct
5 Correct 26 ms 376 KB Output is correct
6 Correct 27 ms 376 KB Output is correct
7 Correct 26 ms 376 KB Output is correct
8 Correct 26 ms 504 KB Output is correct
9 Correct 27 ms 376 KB Output is correct
10 Correct 27 ms 492 KB Output is correct
11 Correct 26 ms 376 KB Output is correct
12 Correct 27 ms 376 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5018 ms 2168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 696 KB Output is correct
2 Correct 1191 ms 1912 KB Output is correct
3 Correct 1882 ms 2040 KB Output is correct
4 Correct 4229 ms 1400 KB Output is correct
5 Execution timed out 5010 ms 3320 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5016 ms 2200 KB Time limit exceeded
2 Halted 0 ms 0 KB -