oj.uz

Submission #124813

# Submission time Handle Problem Language Result Execution time Memory
124813 2019-07-04T02:53:48 Z nhimnam120 Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 5000 ms 3484 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(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;
	return get(id*2,l,mid,u,v) + get(id*2+1,mid+1,r,u,v);
}
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 5 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 13 ms 380 KB Output is correct
5 Correct 22 ms 376 KB Output is correct
6 Correct 23 ms 504 KB Output is correct
7 Correct 22 ms 504 KB Output is correct
8 Correct 22 ms 504 KB Output is correct
9 Correct 23 ms 504 KB Output is correct
10 Correct 23 ms 504 KB Output is correct
11 Correct 22 ms 504 KB Output is correct
12 Correct 25 ms 376 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 776 KB Output is correct
2 Correct 1239 ms 1912 KB Output is correct
3 Correct 1962 ms 1932 KB Output is correct
4 Correct 4379 ms 1528 KB Output is correct
5 Execution timed out 5009 ms 3484 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 5011 ms 2200 KB Time limit exceeded
2 Halted 0 ms 0 KB -