oj.uz

Submission #940542

# Submission time Handle Problem Language Result Execution time Memory
940542 2024-03-07T10:24:32 Z Alexabcde1 Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 6168 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 (seg[ind]==0) 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];
	}
}

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];
	}
}

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 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 4 ms 484 KB Output is correct
8 Correct 4 ms 604 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 4 ms 636 KB Output is correct
12 Correct 4 ms 604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3883 ms 5648 KB Output is correct
2 Correct 2435 ms 4984 KB Output is correct
3 Correct 4154 ms 5420 KB Output is correct
4 Execution timed out 5080 ms 5524 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1116 KB Output is correct
2 Correct 16 ms 3416 KB Output is correct
3 Correct 22 ms 3420 KB Output is correct
4 Correct 69 ms 4064 KB Output is correct
5 Correct 85 ms 4948 KB Output is correct
6 Correct 92 ms 4884 KB Output is correct
7 Execution timed out 5050 ms 4708 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 4704 KB Output is correct
2 Correct 95 ms 4780 KB Output is correct
3 Correct 94 ms 4344 KB Output is correct
4 Correct 120 ms 4668 KB Output is correct
5 Correct 122 ms 6132 KB Output is correct
6 Correct 144 ms 6168 KB Output is correct
7 Correct 136 ms 6164 KB Output is correct
8 Correct 153 ms 5968 KB Output is correct
9 Correct 134 ms 5968 KB Output is correct
10 Correct 149 ms 5964 KB Output is correct
11 Correct 130 ms 5972 KB Output is correct
12 Correct 181 ms 5976 KB Output is correct