oj.uz

Submission #940546

# Submission time Handle Problem Language Result Execution time Memory
940546 2024-03-07T10:27:21 Z Alexabcde1 Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 5000 ms 4524 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 (cc<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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

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