oj.uz

Submission #940551

# Submission time Handle Problem Language Result Execution time Memory
940551 2024-03-07T10:31:22 Z Alexabcde1 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 196 ms 6268 KB 
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
long long n,q,k,a[100005],seg[400005],aa,bb,cc;
void build(long long ind,long long l,long long r){
	if (r<l) return;
	if (l==r){
		seg[ind]=a[l]; return;
	}
	long long mid=(l+r)/2;
	build(ind*2,l,mid);
	build(ind*2+1,mid+1,r);
	seg[ind]=seg[ind*2]+seg[ind*2+1];
	return;
}
void update(long long ind,long long l,long long r){
	if (r<bb) return;
	if (cc<l) return;
	if (r<l)  return;
	if (seg[ind]==0 || k==1) return;
	if ((bb<=l) && (r<=cc)){
		if (l==r){
			seg[ind]/=k;
		}
		else {
			long long mid=(l+r)/2;
			update(ind*2,l,mid);
			update(ind*2+1,mid+1,r);
			seg[ind]=seg[ind*2]+seg[ind*2+1];
		}
	}
	else {
		long long mid=(l+r)/2;
		update(ind*2,l,mid);
		update(ind*2+1,mid+1,r);
		seg[ind]=seg[ind*2]+seg[ind*2+1];
	}
	return;
}

void update2(long long ind,long long l,long long r){
	if (r<bb) return;
	if (bb<l) return;
	if (l==r){
		seg[ind]=cc;
	}
	else {
		long long mid=(l+r)/2;
		update2(ind*2,l,mid);
		update2(ind*2+1,mid+1,r);
		seg[ind]=seg[ind*2]+seg[ind*2+1];
	}
	return;
}

long long sum(long long ind,long long l,long long r){
	if ((r<bb) || (cc<l)) return 0;
	if (bb<=l && r<=cc){
		return seg[ind];
	}
	else {
		long long mid=(l+r)/2;
		return sum(ind*2,l,mid)+sum(ind*2+1,mid+1,r);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>q>>k;
	for (int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	while (q--){
		cin>>aa>>bb>>cc;
		if (aa==1) update2(1,1,n);
		if (aa==2) update(1,1,n);
		if (aa==3) cout<<sum(1,1,n)<<endl;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 4 ms 572 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 4 ms 568 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 3412 KB Output is correct
2 Correct 64 ms 3320 KB Output is correct
3 Correct 49 ms 3516 KB Output is correct
4 Correct 63 ms 3680 KB Output is correct
5 Correct 79 ms 6268 KB Output is correct
6 Correct 82 ms 6228 KB Output is correct
7 Correct 83 ms 6228 KB Output is correct
8 Correct 85 ms 6224 KB Output is correct
9 Correct 79 ms 6084 KB Output is correct
10 Correct 79 ms 6044 KB Output is correct
11 Correct 81 ms 6192 KB Output is correct
12 Correct 99 ms 6132 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 676 KB Output is correct
2 Correct 14 ms 2908 KB Output is correct
3 Correct 23 ms 2916 KB Output is correct
4 Correct 80 ms 2896 KB Output is correct
5 Correct 81 ms 3672 KB Output is correct
6 Correct 89 ms 3416 KB Output is correct
7 Correct 86 ms 3672 KB Output is correct
8 Correct 80 ms 4860 KB Output is correct
9 Correct 76 ms 4688 KB Output is correct
10 Correct 82 ms 4692 KB Output is correct
11 Correct 76 ms 4688 KB Output is correct
12 Correct 74 ms 4636 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 3208 KB Output is correct
2 Correct 93 ms 3160 KB Output is correct
3 Correct 92 ms 3156 KB Output is correct
4 Correct 126 ms 3152 KB Output is correct
5 Correct 127 ms 3668 KB Output is correct
6 Correct 146 ms 3920 KB Output is correct
7 Correct 125 ms 3664 KB Output is correct
8 Correct 164 ms 3768 KB Output is correct
9 Correct 144 ms 3720 KB Output is correct
10 Correct 160 ms 3772 KB Output is correct
11 Correct 139 ms 3672 KB Output is correct
12 Correct 196 ms 3664 KB Output is correct