oj.uz

Submission #518368

# Submission time Handle Problem Language Result Execution time Memory
518368 2022-01-23T14:44:26 Z akshit Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 5000 ms 4804 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;
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);
	
	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 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 8 ms 332 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 8 ms 332 KB Output is correct
7 Correct 12 ms 432 KB Output is correct
8 Correct 8 ms 332 KB Output is correct
9 Correct 9 ms 332 KB Output is correct
10 Correct 9 ms 444 KB Output is correct
11 Correct 9 ms 332 KB Output is correct
12 Correct 9 ms 440 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4062 ms 2972 KB Output is correct
2 Correct 2597 ms 2036 KB Output is correct
3 Correct 4308 ms 3624 KB Output is correct
4 Execution timed out 5093 ms 4588 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 596 KB Output is correct
2 Correct 503 ms 1996 KB Output is correct
3 Correct 702 ms 2092 KB Output is correct
4 Correct 1682 ms 1440 KB Output is correct
5 Execution timed out 5012 ms 4536 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2385 ms 2604 KB Output is correct
2 Correct 2747 ms 2664 KB Output is correct
3 Correct 1398 ms 2528 KB Output is correct
4 Correct 1967 ms 1860 KB Output is correct
5 Execution timed out 5065 ms 4804 KB Time limit exceeded
6 Halted 0 ms 0 KB -