oj.uz

Submission #224232

# Submission time Handle Problem Language Result Execution time Memory
224232 2020-04-17T14:42:36 Z MohamedAhmed04 Cake (CEOI14_cake) C++17
100 / 100
 1135 ms 19176 KB 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#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 11 ms 512 KB Output is correct
5 Correct 23 ms 1152 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1105 ms 1528 KB Output is correct
2 Correct 1000 ms 1528 KB Output is correct
3 Correct 1068 ms 1528 KB Output is correct
4 Correct 973 ms 1544 KB Output is correct
5 Correct 1135 ms 2432 KB Output is correct
6 Correct 1101 ms 2432 KB Output is correct
7 Correct 1097 ms 2432 KB Output is correct
8 Correct 1061 ms 2680 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 8304 KB Output is correct
2 Correct 93 ms 8176 KB Output is correct
3 Correct 92 ms 8048 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 258 ms 18152 KB Output is correct
6 Correct 252 ms 18152 KB Output is correct
7 Correct 175 ms 17896 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1016 KB Output is correct
2 Correct 77 ms 1144 KB Output is correct
3 Correct 151 ms 4464 KB Output is correct
4 Correct 151 ms 4432 KB Output is correct
5 Correct 207 ms 1176 KB Output is correct
6 Correct 275 ms 5608 KB Output is correct
7 Correct 297 ms 2104 KB Output is correct
8 Correct 529 ms 7664 KB Output is correct
9 Correct 1051 ms 19176 KB Output is correct
10 Correct 658 ms 2040 KB Output is correct
11 Correct 744 ms 3576 KB Output is correct
12 Correct 982 ms 16236 KB Output is correct
13 Correct 965 ms 19176 KB Output is correct