oj.uz

Submission #224231

# Submission time Handle Problem Language Result Execution time Memory
224231 2020-04-17T14:41:28 Z MohamedAhmed04 Cake (CEOI14_cake) C++14
100 / 100
 1480 ms 25320 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 FirstLeft(int node , int l , int r , int from , int to , int val)
{
	if(from > r || to < l)
		return -1 ;
	if(val > tree[node])
		return -1 ;
	if(l == r)
		return l ;
	int mid = (l + r) >> 1 ;
	int x = FirstLeft(node << 1 , l , mid , from , to , val) ;
	if(x == -1)
		x = FirstLeft(node << 1 | 1 , mid+1 , r , from , to , val) ;
	return x ;
}

int FirstRight(int node , int l , int r , int from , int to , int val)
{
	if(from > r || to < l)
		return -1 ;
	if(val > tree[node])
		return -1 ;
	if(l == r)
		return l ;
	int mid = (l + r) >> 1 ;
	int x = FirstRight(node << 1 | 1 , mid+1 , r , from , to , val) ;
	if(x == -1)
		x = FirstRight(node << 1 , l , mid , from , to , val) ;
	return x ;
}

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}) ;
			}
		}
		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 ;
				ans = FirstLeft(1 , 1 , n , l , r , Max) ;
				if(ans == -1)
					ans = n ;
				else
					ans-- ;
			}
			else
			{
				Max = query(1 , 1 , n , a+1 , x) , l = 1 , r = a-1 ;
				ans = FirstRight(1 , 1 , n , l , r , Max) ;
				if(ans == -1)
					ans = 1 ;
				else
					ans++ ;
			}
			cout<<abs(x-a)+abs(ans-a)<<"\n" ;
		}
	}
	return 0 ;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 12 ms 512 KB Output is correct
5 Correct 26 ms 1280 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1403 ms 5496 KB Output is correct
2 Correct 1291 ms 5460 KB Output is correct
3 Correct 1335 ms 5496 KB Output is correct
4 Correct 1220 ms 5488 KB Output is correct
5 Correct 1480 ms 6776 KB Output is correct
6 Correct 1432 ms 7160 KB Output is correct
7 Correct 1438 ms 6904 KB Output is correct
8 Correct 1307 ms 7160 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 9192 KB Output is correct
2 Correct 99 ms 9084 KB Output is correct
3 Correct 98 ms 9072 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 244 ms 20204 KB Output is correct
6 Correct 242 ms 20328 KB Output is correct
7 Correct 164 ms 20072 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 1020 KB Output is correct
2 Correct 90 ms 1272 KB Output is correct
3 Correct 178 ms 5104 KB Output is correct
4 Correct 169 ms 4980 KB Output is correct
5 Correct 234 ms 1912 KB Output is correct
6 Correct 326 ms 6892 KB Output is correct
7 Correct 327 ms 3192 KB Output is correct
8 Correct 675 ms 9852 KB Output is correct
9 Correct 1170 ms 25192 KB Output is correct
10 Correct 765 ms 5624 KB Output is correct
11 Correct 855 ms 7672 KB Output is correct
12 Correct 1138 ms 21868 KB Output is correct
13 Correct 1178 ms 25320 KB Output is correct