oj.uz

Submission #518367

# Submission time Handle Problem Language Result Execution time Memory
518367 2022-01-23T14:41:00 Z akshit Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 5000 ms 6544 KB 
// https://oj.uz/problem/view/JOI15_sterilizing
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<ll> seg;
vector<ll> arr;
int n,q;ll k;
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;
	
}
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];
}
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];
}
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);
	
	cin>>n>>q>>k;
	arr.resize(n+1);
	seg.resize(4*n);
	

	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){
			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 2 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 6 ms 428 KB Output is correct
5 Correct 10 ms 504 KB Output is correct
6 Correct 15 ms 508 KB Output is correct
7 Correct 11 ms 504 KB Output is correct
8 Correct 10 ms 452 KB Output is correct
9 Correct 14 ms 504 KB Output is correct
10 Correct 12 ms 488 KB Output is correct
11 Correct 11 ms 504 KB Output is correct
12 Correct 11 ms 464 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4655 ms 2684 KB Output is correct
2 Correct 3042 ms 3756 KB Output is correct
3 Correct 4823 ms 5292 KB Output is correct
4 Execution timed out 5024 ms 6252 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 708 KB Output is correct
2 Correct 579 ms 2348 KB Output is correct
3 Correct 893 ms 2492 KB Output is correct
4 Correct 2131 ms 2576 KB Output is correct
5 Execution timed out 5064 ms 5388 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3035 ms 2484 KB Output is correct
2 Correct 3669 ms 4152 KB Output is correct
3 Correct 1872 ms 3504 KB Output is correct
4 Correct 2527 ms 3644 KB Output is correct
5 Execution timed out 5035 ms 6544 KB Time limit exceeded
6 Halted 0 ms 0 KB -