oj.uz

Submission #40640

# Submission time Handle Problem Language Result Execution time Memory
40640 2018-02-06T12:42:08 Z IvanC Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 350 ms 40528 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){
			if(K != 1) 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 3 ms 488 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 8 ms 544 KB Output is correct
5 Correct 9 ms 700 KB Output is correct
6 Correct 7 ms 768 KB Output is correct
7 Correct 7 ms 788 KB Output is correct
8 Correct 7 ms 788 KB Output is correct
9 Correct 13 ms 856 KB Output is correct
10 Correct 6 ms 856 KB Output is correct
11 Correct 6 ms 856 KB Output is correct
12 Correct 7 ms 856 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 5424 KB Output is correct
2 Correct 95 ms 7016 KB Output is correct
3 Correct 77 ms 10984 KB Output is correct
4 Correct 91 ms 13376 KB Output is correct
5 Correct 118 ms 15912 KB Output is correct
6 Correct 129 ms 18364 KB Output is correct
7 Correct 113 ms 20812 KB Output is correct
8 Correct 111 ms 23212 KB Output is correct
9 Correct 107 ms 25644 KB Output is correct
10 Correct 110 ms 27888 KB Output is correct
11 Correct 117 ms 30204 KB Output is correct
12 Correct 110 ms 32520 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 32520 KB Output is correct
2 Correct 21 ms 32520 KB Output is correct
3 Correct 33 ms 32520 KB Output is correct
4 Correct 120 ms 32520 KB Output is correct
5 Correct 127 ms 32520 KB Output is correct
6 Correct 127 ms 32520 KB Output is correct
7 Correct 110 ms 33660 KB Output is correct
8 Correct 151 ms 34964 KB Output is correct
9 Correct 108 ms 36352 KB Output is correct
10 Correct 133 ms 37584 KB Output is correct
11 Correct 144 ms 38708 KB Output is correct
12 Correct 107 ms 40080 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 40080 KB Output is correct
2 Correct 174 ms 40080 KB Output is correct
3 Correct 191 ms 40080 KB Output is correct
4 Correct 183 ms 40080 KB Output is correct
5 Correct 221 ms 40244 KB Output is correct
6 Correct 264 ms 40508 KB Output is correct
7 Correct 194 ms 40508 KB Output is correct
8 Correct 274 ms 40508 KB Output is correct
9 Correct 258 ms 40508 KB Output is correct
10 Correct 285 ms 40508 KB Output is correct
11 Correct 218 ms 40528 KB Output is correct
12 Correct 350 ms 40528 KB Output is correct