oj.uz

Submission #124821

# Submission time Handle Problem Language Result Execution time Memory
124821 2019-07-04T03:04:29 Z tuanasanh Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 163 ms 2316 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
const int N=1e5+50;
int q,n,k,type,u,v;
int a[N],sum[N*20];
void build(int id,int l,int r){
	if(l==r) sum[id]=a[l];
	if(l<r){
		int mid=(l+r)/2;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		sum[id]=sum[id*2]+sum[id*2+1];
	}
}
void boost(int id,int l,int r,int u,int v){
	if(l==r){
		sum[id]=v;
		return;
	}
	int mid=(l+r)/2;
	if(u<=mid) boost(id*2,l,mid,u,v);
	else boost(id*2+1,mid+1,r,u,v);
	sum[id]=sum[id*2]+sum[id*2+1];
}
void divide(int id,int l,int r,int u,int v){
	if(sum[id]==0||k==1) return;
	if(l==r){
		sum[id]/=k;
		return;
	}
	int mid=(l+r)/2;
	if(u<=mid) divide(id*2,l,mid,u,v);
	if(v>mid) divide(id*2+1,mid+1,r,u,v);
	sum[id]=sum[id*2]+sum[id*2+1];
}
int get(int id,int l,int r,int u,int v){
	if(l>v||r<u) return 0;
	if(l>=u&&r<=v) return sum[id];
	int mid=(l+r)>>1;
	return get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v);
}
signed main(){
//	freopen(".inp","r",stdin);
//	freopen(".out","w",stdout);
	ios_base::sync_with_stdio(0); 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>>type>>u>>v;
		if(type==1) boost(1,1,n,u,v);
		else if(type==2) divide(1,1,n,u,v);
		else cout<<get(1,1,n,u,v)<<endl;
	}
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 916 KB Output is correct
2 Correct 28 ms 1348 KB Output is correct
3 Correct 43 ms 1404 KB Output is correct
4 Correct 145 ms 1204 KB Output is correct
5 Correct 163 ms 2252 KB Output is correct
6 Correct 160 ms 2168 KB Output is correct
7 Correct 153 ms 2296 KB Output is correct
8 Correct 161 ms 2168 KB Output is correct
9 Correct 154 ms 2316 KB Output is correct
10 Correct 150 ms 2168 KB Output is correct
11 Correct 152 ms 2212 KB Output is correct
12 Correct 152 ms 2292 KB Output is correct

Subtask #4
0 / 75.0

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