oj.uz

Submission #40639

# Submission time Handle Problem Language Result Execution time Memory
40639 2018-02-06T12:40:30 Z IvanC Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 39156 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
ll seg[4*MAXN],qtd[4*MAXN],vetor[MAXN],N,Q,K;
void build(int pos,int left,int right){
	if(left == right){
		seg[pos] = vetor[left];
		qtd[pos] = (seg[pos] == 0);
		return;
	}
	int mid = (left+right)/2;
	build(2*pos,left,mid);
	build(2*pos+1,mid+1,right);
	seg[pos] = seg[2*pos] + seg[2*pos+1];
	qtd[pos] = qtd[2*pos] + qtd[2*pos+1];
}
void update_division(int pos,int left,int right,int i,int j){
	if(qtd[pos] == right - left + 1) return;
	if(left == right){
		seg[pos] = seg[pos]/K;
		qtd[pos] = (seg[pos] == 0);
		return;
	}
	int mid = (left+right)/2;
	if(j <= mid){
		update_division(2*pos,left,mid,i,j);
	}
	else if(i >= mid+1){
		update_division(2*pos+1,mid+1,right,i,j);
	}
	else{
		update_division(2*pos,left,mid,i,mid);
		update_division(2*pos+1,mid+1,right,mid+1,j);
	}
	seg[pos] = seg[2*pos] + seg[2*pos+1];
	qtd[pos] = qtd[2*pos] + qtd[2*pos+1];
}
void update_value(int pos,int left,int right,int x,ll val){
	if(left == right){
		seg[pos] = val;
		qtd[pos] = (seg[pos] == 0);
		return;
	}
	int mid = (left+right)/2;
	if(x <= mid) update_value(2*pos,left,mid,x,val);
	else update_value(2*pos+1,mid+1,right,x,val);
	seg[pos] = seg[2*pos] + seg[2*pos+1];
	qtd[pos] = qtd[2*pos] + qtd[2*pos+1];
}
ll query(int pos,int left,int right,int i,int j){
	if(left >= i && right <= j) return seg[pos];
	int mid = (left+right)/2;
	if(j <= mid) return query(2*pos,left,mid,i,j);
	else if(i >= mid + 1) return query(2*pos+1,mid+1,right,i,j);
	else return query(2*pos,left,mid,i,j) + query(2*pos+1,mid+1,right,i,j);
}
int main(){
	cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
	cin >> N >> Q >> K;
	for(int i = 1;i<=N;i++) cin >> vetor[i];
	build(1,1,N);
	for(int q = 1;q<=Q;q++){
		ll op,u,v;
		cin >> op >> u >> v;
		if(op == 1){
			update_value(1,1,N,u,v);
		}
		else if(op == 2){
			update_division(1,1,N,u,v);
		}
		else{
			cout << query(1,1,N,u,v) << endl;
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 5 ms 536 KB Output is correct
3 Correct 2 ms 644 KB Output is correct
4 Correct 8 ms 684 KB Output is correct
5 Correct 8 ms 928 KB Output is correct
6 Correct 6 ms 1096 KB Output is correct
7 Correct 7 ms 1280 KB Output is correct
8 Correct 7 ms 1352 KB Output is correct
9 Correct 9 ms 1352 KB Output is correct
10 Correct 7 ms 1388 KB Output is correct
11 Correct 7 ms 1456 KB Output is correct
12 Correct 7 ms 1524 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5804 KB Output is correct
2 Correct 23 ms 5884 KB Output is correct
3 Correct 33 ms 6404 KB Output is correct
4 Correct 99 ms 6404 KB Output is correct
5 Correct 125 ms 11616 KB Output is correct
6 Correct 152 ms 13060 KB Output is correct
7 Execution timed out 5041 ms 13820 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 13820 KB Output is correct
2 Correct 153 ms 14652 KB Output is correct
3 Correct 170 ms 15680 KB Output is correct
4 Correct 189 ms 16512 KB Output is correct
5 Correct 239 ms 22456 KB Output is correct
6 Correct 249 ms 25060 KB Output is correct
7 Correct 216 ms 27416 KB Output is correct
8 Correct 290 ms 29880 KB Output is correct
9 Correct 249 ms 32092 KB Output is correct
10 Correct 282 ms 34664 KB Output is correct
11 Correct 228 ms 36804 KB Output is correct
12 Correct 372 ms 39156 KB Output is correct