oj.uz

Submission #124812

# Submission time Handle Problem Language Result Execution time Memory
124812 2019-07-04T02:48:26 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(){
	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 376 KB Output is correct
5 Correct 21 ms 504 KB Output is correct
6 Correct 22 ms 504 KB Output is correct
7 Correct 21 ms 504 KB Output is correct
8 Correct 21 ms 504 KB Output is correct
9 Correct 22 ms 504 KB Output is correct
10 Correct 22 ms 504 KB Output is correct
11 Correct 21 ms 504 KB Output is correct
12 Correct 22 ms 376 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 632 KB Output is correct
2 Correct 1153 ms 1932 KB Output is correct
3 Correct 1836 ms 1920 KB Output is correct
4 Correct 4097 ms 1380 KB Output is correct
5 Execution timed out 5013 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 5099 ms 2228 KB Time limit exceeded
2 Halted 0 ms 0 KB -