Submission #418025

#	Time	Username	Problem	Language	Result	Execution time	Memory
418025		MohamedAhmed04	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	2291 ms	10384 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] ;
int n , q , k ;

long long tree[4 * MAX] ;

void update(int node , int l , int r , int idx , int val)
{
	if(idx > r || idx < l)
		return ;
	if(l == r)
	{
		tree[node] = val ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(node << 1 , l , mid , idx , val) ;
	update(node << 1 | 1 , mid+1 , r , idx , val) ;
	tree[node] = tree[node << 1] + tree[node << 1 | 1] ;
}

long long query(int node , int l , int r , int from , int to)
{
	if(from > r || to < l)
		return 0 ;
	if(l >= from && r <= to)
		return tree[node] ;
	int mid = (l + r) >> 1 ;
	long long x = query(node << 1 , l , mid , from , to) ;
	long long y = query(node << 1 | 1 , mid+1 , r , from , to) ;
	return (x + y) ;
}

set<int>s ;

void upd(int l , int r)
{
	if(k == 1)
		return ;
	int cur = l-1 ;
	while(s.size())
	{
		auto it = s.upper_bound(cur) ;
		if(it == s.end())
			break ;
		cur = *it ;
		if(cur > r)
			return ;
		s.erase(cur) ;
		arr[cur] /= k ;
		update(1 , 1 , n , cur , arr[cur]) ;
		if(arr[cur])
			s.insert(cur) ;
	}
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>q>>k ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	for(int i = 1 ; i <= n ; ++i)
	{
		update(1 , 1 , n , i , arr[i]) ;
		if(arr[i])
			s.insert(i) ;
	}
	while(q--)
	{
		int t ;
		cin>>t ;
		if(t == 1)
		{
			int idx , x ;
			cin>>idx>>x ;
			if(arr[idx])
				s.erase(idx) ;
			arr[idx] = x ;
			update(1 , 1 , n , idx , arr[idx]) ;
			if(arr[idx])
				s.insert(idx) ;
		}
		else if(t == 2)
		{
			int l , r ;
			cin>>l>>r ;
			upd(l , r) ;
		}
		else if(t == 3)
		{
			int l , r ;
			cin>>l>>r ;
			cout<<query(1 , 1 , n , l , r)<<"\n" ;
		}
	}
	return 0 ;
}		

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