Submission #333314

#	Time	Username	Problem	Language	Result	Execution time	Memory
333314		GioChkhaidze	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	314 ms	6724 KiB

sterilizing

#include <bits/stdc++.h>

#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define ll long long

using namespace std;

const int N=1e5+5;

int n,q,k;
int a[N],vm[4*N];
ll v[4*N];

void Build(Tree) {
	if (l==r) {
		v[h]=a[l];
		vm[h]=a[l];
		return ;
	}
	
	Build(Left);
	Build(Right);
	v[h]=v[(h<<1)]+v[((h<<1)|1)];
	vm[h]=max(vm[(h<<1)],vm[((h<<1)|1)]);
}

int t,id,vl;
void Up(Tree) {
	if (id<l || r<id) return ;
	if (l==id && r==id) {
		v[h]=a[l];
		vm[h]=a[l];
		return ;
	}
	
	Up(Left);
	Up(Right);
	v[h]=v[(h<<1)]+v[((h<<1)|1)];
	vm[h]=max(vm[(h<<1)],vm[((h<<1)|1)]);
}

int L,R;
void Upd(Tree) {
	if (R<l || r<L) return ;
	if (vm[h]==0) return ;
	
	if (l==r) {
		v[h]/=k;
		vm[h]=v[h];
		return ;
	}
	
	Upd(Left);
	Upd(Right);	
	v[h]=v[(h<<1)]+v[((h<<1)|1)];
	vm[h]=max(vm[(h<<1)],vm[((h<<1)|1)]);
}

ll Get(Tree) {
	if (R<l || r<L) return 0;
	if (L<=l && r<=R) return v[h];
	return Get(Left)+Get(Right);
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	cin>>n>>q>>k;
	for (int i=1; i<=n; i++) {
		cin>>a[i];
	}
	
	Build(1,1,n);
	
	for (int i=1; i<=q; i++) {
		cin>>t;
		if (t==1) {
			cin>>id>>vl;
			a[id]=vl;
			Up(1,1,n);
		}
			else
		if (t==2) {
			cin>>L>>R;
			if (k==1) continue;
			Upd(1,1,n);
		}
			else
		if (t==3) {
			cin>>L>>R;
			cout<<Get(1,1,n)<<"\n";
		}
	}
}

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75