oj.uz

Submission #527820

# Submission time Handle Problem Language Result Execution time Memory
527820 2022-02-18T12:48:01 Z Koosha_mv Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 218 ms 8136 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

const int N=5e5+99;

int n,q,k,a[N],Sum[N],Max[N];

void merge(int id){
	Sum[id]=Sum[id<<1]+Sum[id<<1|1];
	Max[id]=max(Max[id<<1],Max[id<<1|1]);
}
void build(int id=1,int l=1,int r=n+1){
	if(l+1==r){
		Sum[id]=a[l];
		Max[id]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid,r);
	merge(id);
}
void change(int x,int val,int id=1,int l=1,int r=n+1){
	if(r<=x || x<l) return ;
	if(l+1==r){
		Sum[id]=val;
		Max[id]=val;
		return ;
	}
	int mid=(l+r)>>1;
	change(x,val,id<<1,l,mid);
	change(x,val,id<<1|1,mid,r);
	merge(id);
}
int get(int L,int R,int id=1,int l=1,int r=n+1){
	if(r<=L || R<=l) return 0;
	if(L<=l && r<=R){
		return Sum[id];
	}
	int mid=(l+r)>>1;
	return get(L,R,id<<1,l,mid)+get(L,R,id<<1|1,mid,r);
}
void spray(int L,int R,int id=1,int l=1,int r=n+1){
	if(Max[id]==0 || r<=L || R<=l) return ;
	if(l+1==r){
		Sum[id]/=k;
		Max[id]/=k;
		return ;
	}
	int mid=(l+r)>>1;
	spray(L,R,id<<1,l,mid);
	spray(L,R,id<<1|1,mid,r);
	merge(id);
}

main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>q>>k;
	f(i,1,n+1) cin>>a[i];
	build();
	f(i,0,q){
		int type,l,r;
		cin>>type>>l>>r;
		if(type==1){
			change(l,r);
		}
		if(type==2){
			if(k==1) continue ;
			spray(l,r+1);
		}
		if(type==3){
			cout<<get(l,r+1)<<'\n';
		}
	}
}
/*
5 2 3
1 5 8 1 3
2 3 5
3 2 5
*/

Compilation message

sterilizing.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(){
      | ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3612 KB Output is correct
2 Correct 37 ms 4664 KB Output is correct
3 Correct 33 ms 6920 KB Output is correct
4 Correct 50 ms 7588 KB Output is correct
5 Correct 52 ms 8120 KB Output is correct
6 Correct 57 ms 8136 KB Output is correct
7 Correct 54 ms 8132 KB Output is correct
8 Correct 53 ms 8048 KB Output is correct
9 Correct 51 ms 8004 KB Output is correct
10 Correct 51 ms 7908 KB Output is correct
11 Correct 49 ms 7928 KB Output is correct
12 Correct 49 ms 7916 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 648 KB Output is correct
2 Correct 11 ms 2748 KB Output is correct
3 Correct 14 ms 2764 KB Output is correct
4 Correct 39 ms 1600 KB Output is correct
5 Correct 54 ms 5236 KB Output is correct
6 Correct 51 ms 5268 KB Output is correct
7 Correct 47 ms 5788 KB Output is correct
8 Correct 51 ms 6632 KB Output is correct
9 Correct 47 ms 6468 KB Output is correct
10 Correct 46 ms 6448 KB Output is correct
11 Correct 49 ms 6628 KB Output is correct
12 Correct 46 ms 6524 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2912 KB Output is correct
2 Correct 76 ms 2964 KB Output is correct
3 Correct 91 ms 2884 KB Output is correct
4 Correct 100 ms 1856 KB Output is correct
5 Correct 120 ms 5648 KB Output is correct
6 Correct 128 ms 5444 KB Output is correct
7 Correct 110 ms 5376 KB Output is correct
8 Correct 157 ms 5412 KB Output is correct
9 Correct 145 ms 5572 KB Output is correct
10 Correct 167 ms 5484 KB Output is correct
11 Correct 117 ms 5420 KB Output is correct
12 Correct 218 ms 5464 KB Output is correct