제출 #223942

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
223942		MohamedAhmed04	케이크 (CEOI14_cake)	C++14	83.33 / 100	2063 ms	30376 KiB

cake

#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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 33.333333 / 50