oj.uz

Submission #527818

# Submission time Handle Problem Language Result Execution time Memory
527818 2022-02-18T12:46:58 Z Koosha_mv Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 8020 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){
			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 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 456 KB Output is correct
5 Correct 3 ms 464 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 3 ms 452 KB Output is correct
9 Correct 4 ms 456 KB Output is correct
10 Correct 3 ms 536 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 4 ms 460 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5057 ms 3228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 588 KB Output is correct
2 Correct 15 ms 2748 KB Output is correct
3 Correct 18 ms 2648 KB Output is correct
4 Correct 40 ms 1604 KB Output is correct
5 Correct 50 ms 5276 KB Output is correct
6 Correct 50 ms 5252 KB Output is correct
7 Execution timed out 5058 ms 5352 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 2884 KB Output is correct
2 Correct 86 ms 4716 KB Output is correct
3 Correct 120 ms 3924 KB Output is correct
4 Correct 105 ms 3480 KB Output is correct
5 Correct 115 ms 7932 KB Output is correct
6 Correct 141 ms 8020 KB Output is correct
7 Correct 109 ms 7832 KB Output is correct
8 Correct 164 ms 7896 KB Output is correct
9 Correct 150 ms 7776 KB Output is correct
10 Correct 169 ms 7748 KB Output is correct
11 Correct 121 ms 7752 KB Output is correct
12 Correct 247 ms 7752 KB Output is correct