oj.uz

Submission #124822

# Submission time Handle Problem Language Result Execution time Memory
124822 2019-07-04T03:06:14 Z tuanasanh Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 256 ms 4284 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define int long long
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)<<"\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 6 ms 504 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 6 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2360 KB Output is correct
2 Correct 52 ms 2424 KB Output is correct
3 Correct 49 ms 3636 KB Output is correct
4 Correct 60 ms 3960 KB Output is correct
5 Correct 73 ms 4092 KB Output is correct
6 Correct 73 ms 4088 KB Output is correct
7 Correct 73 ms 4012 KB Output is correct
8 Correct 74 ms 4060 KB Output is correct
9 Correct 69 ms 4132 KB Output is correct
10 Correct 68 ms 4088 KB Output is correct
11 Correct 67 ms 4088 KB Output is correct
12 Correct 74 ms 4088 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 632 KB Output is correct
2 Correct 15 ms 1656 KB Output is correct
3 Correct 20 ms 1784 KB Output is correct
4 Correct 55 ms 1168 KB Output is correct
5 Correct 73 ms 3192 KB Output is correct
6 Correct 70 ms 3288 KB Output is correct
7 Correct 61 ms 3320 KB Output is correct
8 Correct 69 ms 3220 KB Output is correct
9 Correct 62 ms 3320 KB Output is correct
10 Correct 62 ms 3396 KB Output is correct
11 Correct 63 ms 3648 KB Output is correct
12 Correct 64 ms 3668 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 2536 KB Output is correct
2 Correct 99 ms 2800 KB Output is correct
3 Correct 120 ms 2676 KB Output is correct
4 Correct 123 ms 2128 KB Output is correct
5 Correct 147 ms 4188 KB Output is correct
6 Correct 168 ms 4256 KB Output is correct
7 Correct 145 ms 4216 KB Output is correct
8 Correct 202 ms 4284 KB Output is correct
9 Correct 171 ms 4216 KB Output is correct
10 Correct 195 ms 4228 KB Output is correct
11 Correct 147 ms 4216 KB Output is correct
12 Correct 256 ms 4272 KB Output is correct