oj.uz

Submission #418025

# Submission time Handle Problem Language Result Execution time Memory
418025 2021-06-04T21:52:41 Z MohamedAhmed04 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 2291 ms 10384 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 7 ms 476 KB Output is correct
4 Correct 22 ms 480 KB Output is correct
5 Correct 23 ms 612 KB Output is correct
6 Correct 16 ms 608 KB Output is correct
7 Correct 21 ms 608 KB Output is correct
8 Correct 27 ms 600 KB Output is correct
9 Correct 28 ms 588 KB Output is correct
10 Correct 20 ms 584 KB Output is correct
11 Correct 19 ms 612 KB Output is correct
12 Correct 23 ms 592 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 6116 KB Output is correct
2 Correct 79 ms 5024 KB Output is correct
3 Correct 96 ms 8220 KB Output is correct
4 Correct 120 ms 9768 KB Output is correct
5 Correct 146 ms 10356 KB Output is correct
6 Correct 167 ms 10384 KB Output is correct
7 Correct 136 ms 10304 KB Output is correct
8 Correct 149 ms 10316 KB Output is correct
9 Correct 156 ms 10160 KB Output is correct
10 Correct 133 ms 10164 KB Output is correct
11 Correct 137 ms 10196 KB Output is correct
12 Correct 176 ms 10240 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 996 KB Output is correct
2 Correct 33 ms 2784 KB Output is correct
3 Correct 39 ms 2884 KB Output is correct
4 Correct 67 ms 2660 KB Output is correct
5 Correct 125 ms 6568 KB Output is correct
6 Correct 119 ms 6596 KB Output is correct
7 Correct 134 ms 6612 KB Output is correct
8 Correct 125 ms 6468 KB Output is correct
9 Correct 119 ms 6516 KB Output is correct
10 Correct 119 ms 6348 KB Output is correct
11 Correct 113 ms 6408 KB Output is correct
12 Correct 115 ms 6420 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 5660 KB Output is correct
2 Correct 420 ms 5828 KB Output is correct
3 Correct 955 ms 4880 KB Output is correct
4 Correct 503 ms 4416 KB Output is correct
5 Correct 817 ms 10116 KB Output is correct
6 Correct 1054 ms 10124 KB Output is correct
7 Correct 767 ms 10140 KB Output is correct
8 Correct 1513 ms 10108 KB Output is correct
9 Correct 1188 ms 9988 KB Output is correct
10 Correct 1470 ms 9992 KB Output is correct
11 Correct 891 ms 10020 KB Output is correct
12 Correct 2291 ms 9988 KB Output is correct