oj.uz

Submission #223947

# Submission time Handle Problem Language Result Execution time Memory
223947 2020-04-16T22:21:46 Z MohamedAhmed04 Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 19056 KB 
#include <bits/stdc++.h>
 
using namespace std ;
 
const int MAX = 3e5 + 10 ;
 
int arr[MAX] ;
int n , a ;
 
int 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 , 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] = max(tree[node << 1] , tree[node << 1 | 1]) ;
}
 
int 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 ;
	int a = query(node << 1 , l , mid , from , to) ;
	int 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<int , 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 ;
			}
			int 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 ;
				int 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 13 ms 384 KB Output is correct
5 Correct 33 ms 1152 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1288 ms 1144 KB Output is correct
2 Correct 1216 ms 1144 KB Output is correct
3 Correct 1266 ms 1144 KB Output is correct
4 Correct 1162 ms 1120 KB Output is correct
5 Correct 1376 ms 2048 KB Output is correct
6 Correct 1320 ms 2048 KB Output is correct
7 Correct 1348 ms 2048 KB Output is correct
8 Correct 1278 ms 2168 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 7920 KB Output is correct
2 Correct 296 ms 7788 KB Output is correct
3 Correct 315 ms 7664 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 532 ms 17840 KB Output is correct
6 Correct 660 ms 18024 KB Output is correct
7 Correct 499 ms 17640 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 760 KB Output is correct
2 Correct 133 ms 768 KB Output is correct
3 Correct 287 ms 4340 KB Output is correct
4 Correct 243 ms 4084 KB Output is correct
5 Correct 293 ms 760 KB Output is correct
6 Correct 536 ms 5228 KB Output is correct
7 Correct 457 ms 1656 KB Output is correct
8 Correct 640 ms 7280 KB Output is correct
9 Correct 1844 ms 18956 KB Output is correct
10 Correct 962 ms 1656 KB Output is correct
11 Correct 1228 ms 3492 KB Output is correct
12 Correct 1781 ms 16084 KB Output is correct
13 Execution timed out 2070 ms 19056 KB Time limit exceeded