oj.uz

Submission #940549

# Submission time Handle Problem Language Result Execution time Memory
940549 2024-03-07T10:30:04 Z Alexabcde1 Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 5204 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) 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 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 4 ms 488 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 5 ms 552 KB Output is correct
9 Correct 4 ms 600 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 3984 ms 3648 KB Output is correct
2 Correct 2449 ms 4712 KB Output is correct
3 Correct 4075 ms 5048 KB Output is correct
4 Execution timed out 5057 ms 5084 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 600 KB Output is correct
2 Correct 14 ms 3160 KB Output is correct
3 Correct 21 ms 3420 KB Output is correct
4 Correct 71 ms 3684 KB Output is correct
5 Correct 78 ms 4544 KB Output is correct
6 Correct 78 ms 4524 KB Output is correct
7 Execution timed out 5056 ms 4824 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3156 KB Output is correct
2 Correct 92 ms 4180 KB Output is correct
3 Correct 87 ms 3908 KB Output is correct
4 Correct 115 ms 4204 KB Output is correct
5 Correct 125 ms 5040 KB Output is correct
6 Correct 137 ms 5200 KB Output is correct
7 Correct 125 ms 5204 KB Output is correct
8 Correct 162 ms 5120 KB Output is correct
9 Correct 142 ms 4864 KB Output is correct
10 Correct 172 ms 4968 KB Output is correct
11 Correct 126 ms 4944 KB Output is correct
12 Correct 193 ms 4972 KB Output is correct