oj.uz

Submission #518580

# Submission time Handle Problem Language Result Execution time Memory
518580 2022-01-24T07:40:00 Z akshit Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 4980 KB 
// https://oj.uz/problem/view/JOI15_sterilizing
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll seg[4000003];
ll arr[1000003];
int n,q;ll k;
inline void build(int l,int r,int node){
	
	if(l==r){seg[node]=arr[l];return;}
	int mid=(l+r)>>1;
	int L=node<<1;int R=L|1;
	build(l,mid,L);build(mid+1,r,R);
	seg[node]=seg[L]+seg[R];
	// cout<<l<<" "<<r<<" "<<node<<" "<<seg[node]<<endl;
	
}
inline void fix(int l,int r,int node,int p,ll val){
	if(l==r){seg[node]=arr[l]=val;return;}
	int mid=(l+r)>>1;
	int L=node<<1;int R=L|1;
	if(p<=mid)fix(l,mid,L,p,val);
	else fix(mid+1,r,R,p,val);
	seg[node]=seg[L]+seg[R];
}
inline void upd(int l,int r,int node,int i,int j){
	// cout<<i<<" "<<j<<endl;
	if(l==r){

		arr[l]/=k;
		seg[node]=arr[l];return;
	}
	int L=node<<1;int R=L|1;
	int mid=(l+r)>>1;
	if(mid<i){upd(mid+1,r,R,i,j);}
	else if(mid>=j){upd(l,mid,L,i,j);}
	else {upd(l,mid,L,i,mid);
	upd(mid+1,r,R,mid+1,j);}
	seg[node]=seg[L]+seg[R];
}
inline ll query(int l,int r,int node,int i,int j){

	if(l>=i &&j>=r){return seg[node];}
	if(r<i || l>j)return 0;
	int L=node<<1;int R=L|1;
	int mid=(l+r)>>1;
	if(mid<i){return query(mid+1,r,R,i,j);}
	if(mid>=j){return query(l,mid,L,i,j);}
	return query(l,mid,L,i,mid)+query(mid+1,r,R,mid+1,j);

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
	cin>>n>>q>>k;
	
	

	for(int i=1;i<=n;i++)cin>>arr[i];

	build(1,n,1);
	int t,a;ll b;
	// cout<<query(1,n,1,9,12)<<endl;
	for(int i=0;i<q;i++){
		cin>>t>>a>>b;
		if(t==1){
			fix(1,n,1,a,b);
			// cout<<"f "<<a<<" "<<b<<" "<<query(1,n,1,1,n)<<endl;
		}else if(t==2){
			if(k==1)continue;
			upd(1,n,1,a,b);
			// cout<<"u "<<a<<" "<<b<<" "<<query(1,n,1,1,n)<<endl;
		}else {cout<<query(1,n,1,a,b)<<endl;}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 7 ms 460 KB Output is correct
6 Correct 8 ms 488 KB Output is correct
7 Correct 7 ms 460 KB Output is correct
8 Correct 7 ms 456 KB Output is correct
9 Correct 8 ms 456 KB Output is correct
10 Correct 8 ms 392 KB Output is correct
11 Correct 8 ms 500 KB Output is correct
12 Correct 8 ms 492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 2372 KB Output is correct
2 Correct 74 ms 2452 KB Output is correct
3 Correct 54 ms 3592 KB Output is correct
4 Correct 68 ms 3940 KB Output is correct
5 Correct 83 ms 4908 KB Output is correct
6 Correct 99 ms 4820 KB Output is correct
7 Correct 84 ms 4800 KB Output is correct
8 Correct 91 ms 4840 KB Output is correct
9 Correct 93 ms 4828 KB Output is correct
10 Correct 91 ms 4804 KB Output is correct
11 Correct 82 ms 4924 KB Output is correct
12 Correct 88 ms 4980 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 880 KB Output is correct
2 Correct 370 ms 1860 KB Output is correct
3 Correct 544 ms 2088 KB Output is correct
4 Correct 1227 ms 1564 KB Output is correct
5 Correct 4866 ms 3504 KB Output is correct
6 Execution timed out 5011 ms 4576 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1827 ms 1936 KB Output is correct
2 Correct 2115 ms 2336 KB Output is correct
3 Correct 1138 ms 2360 KB Output is correct
4 Correct 1566 ms 1708 KB Output is correct
5 Execution timed out 5034 ms 3908 KB Time limit exceeded
6 Halted 0 ms 0 KB -