oj.uz

Submission #223943

# Submission time Handle Problem Language Result Execution time Memory
223943 2020-04-16T22:19:24 Z MohamedAhmed04 Cake (CEOI14_cake) C++17
83.3333 / 100
 2000 ms 23952 KB 
#include <bits/stdc++.h>
 
using namespace std ;
 
const int MAX = 3e5 + 10 ;
 
long long arr[MAX] ;
int n , a ;
 
long long tree[4 * MAX] ;
 
void build(int node , int l , int r)
{
	if(l == r)
	{
		tree[node] = arr[l] ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	build(node << 1 , l , mid) ;
	build(node << 1 | 1 , mid+1 , r) ;
	tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
}
 
void update(int node , int l , int r , int idx , long long 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] = max(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 0ll ;
	if(l >= from && r <= to)
		return tree[node] ;
	int mid = (l + r) >> 1 ;
	long long a = query(node << 1 , l , mid , from , to) ;
	long long b = query(node << 1 | 1, mid+1 , r , from , to) ;
	return max(a , b) ;
}
 
int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>a ;
	vector< pair<long long , int> >vp ;
	for(int i = 1 ; i <= n ; ++i)
	{
		cin>>arr[i] ;
		vp.emplace_back(arr[i] , i) ;
	}
	sort(vp.begin() , vp.end()) ;
	for(int i = 0 ; i < n ; ++i)
		arr[vp[i].second] = i+1ll ;
	build(1 , 1 , n) ;
	set< pair<int , int> >s ;
	for(int i = 1 ; i <= n ; ++i)
		s.insert({arr[i] , i}) ;
	while(s.size() > 10)
		s.erase(s.begin()) ;
	int q ;
	cin>>q ;
	while(q--)
	{
		char c ;
		cin>>c ;
		if(c == 'E')
		{
			int x , y ;
			cin>>x>>y ;
			s.insert({arr[x] , x}) ;
			if(s.size() > 10)
			{
				s.erase({arr[x] , x}) ;
				s.erase(s.begin()) ;
			}
			else
				s.erase({arr[x] , x}) ;
			pair<int , int>p = *s.rbegin() ;
			int val = p.first ;
			for(int i = min(n , 10) ; i >= 1 ; --i)
			{
				val++ ;
				if(i == y)
				{
					arr[x] = val ;
					s.insert({arr[x] , x}) ;
					update(1 , 1 , n , x , arr[x]) ;
					continue ;
				}
				p = *s.begin() ;
				s.erase(p) ;
				arr[p.second] = val ;
				update(1 , 1 , n , p.second , arr[p.second]) ;
				s.insert({arr[p.second] , p.second}) ;
			}
			//arr[x] = val[n-y+1] ;
			//val[n-y+1]++ ;
			//update(1 , 1 , n , x , arr[x]) ;
		}
		else
		{
			int x ;
			cin>>x ;
			if(x == a)
			{
				cout<<0<<"\n" ;
				continue ;
			}
			long long Max ;
			int l , r , ans = a ;
			if(x < a)
				Max = query(1 , 1 , n , x , a-1) , l = a+1 , r = n ;
			else
				Max = query(1 , 1 , n , a+1 , x) , l = 1 , r = a-1 ;
			while(l <= r)
			{
				int mid = (l + r) >> 1 ;
				long long y ;
				if(mid > a)
					y = query(1 , 1 , n , a+1 , mid) ;
				else
					y = query(1 , 1 , n , mid , a-1) ;
				if(y < Max)
				{
					ans = mid ;
					if(mid > a)
						l = mid+1 ;
					else
						r = mid-1 ;
				}
				else
				{
					if(mid > a)
						r = mid-1 ;
					else
						l = mid+1 ;
				}
			}
			cout<<abs(x-a)+abs(ans-a)<<"\n" ;
		}
	}
	return 0 ;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 14 ms 512 KB Output is correct
5 Correct 34 ms 1280 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1305 ms 1280 KB Output is correct
2 Correct 1212 ms 1280 KB Output is correct
3 Correct 1268 ms 1408 KB Output is correct
4 Correct 1182 ms 1280 KB Output is correct
5 Correct 1388 ms 2556 KB Output is correct
6 Correct 1299 ms 2684 KB Output is correct
7 Correct 1323 ms 2684 KB Output is correct
8 Correct 1246 ms 2804 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 10088 KB Output is correct
2 Correct 319 ms 9964 KB Output is correct
3 Correct 335 ms 9832 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 585 ms 22856 KB Output is correct
6 Correct 653 ms 23060 KB Output is correct
7 Correct 536 ms 22624 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 760 KB Output is correct
2 Correct 137 ms 896 KB Output is correct
3 Correct 312 ms 5100 KB Output is correct
4 Correct 251 ms 5100 KB Output is correct
5 Correct 292 ms 888 KB Output is correct
6 Correct 571 ms 6520 KB Output is correct
7 Correct 472 ms 1912 KB Output is correct
8 Correct 647 ms 9580 KB Output is correct
9 Correct 1982 ms 23952 KB Output is correct
10 Correct 970 ms 1856 KB Output is correct
11 Correct 1269 ms 3700 KB Output is correct
12 Correct 1879 ms 20552 KB Output is correct
13 Execution timed out 2091 ms 23776 KB Time limit exceeded