oj.uz

답안 #518371

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
518371 2022-01-23T14:48:34 Z akshit Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 5000 ms 3612 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);
	
	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){
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 332 KB Output is correct
5 Correct 7 ms 332 KB Output is correct
6 Correct 8 ms 332 KB Output is correct
7 Correct 8 ms 416 KB Output is correct
8 Correct 8 ms 332 KB Output is correct
9 Correct 8 ms 332 KB Output is correct
10 Correct 7 ms 332 KB Output is correct
11 Correct 9 ms 424 KB Output is correct
12 Correct 9 ms 332 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4051 ms 2260 KB Output is correct
2 Correct 2530 ms 2088 KB Output is correct
3 Correct 3986 ms 3404 KB Output is correct
4 Execution timed out 5057 ms 3500 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 460 KB Output is correct
2 Correct 375 ms 1692 KB Output is correct
3 Correct 578 ms 1688 KB Output is correct
4 Correct 1369 ms 1160 KB Output is correct
5 Execution timed out 5048 ms 3312 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1913 ms 2108 KB Output is correct
2 Correct 2245 ms 1992 KB Output is correct
3 Correct 1301 ms 1952 KB Output is correct
4 Correct 1688 ms 1268 KB Output is correct
5 Execution timed out 5034 ms 3612 KB Time limit exceeded
6 Halted 0 ms 0 KB -