oj.uz

Submission #223944

# Submission time Handle Problem Language Result Execution time Memory
223944 2020-04-16T22:20:18 Z MohamedAhmed04 Cake (CEOI14_cake) C++17
100 / 100
 1897 ms 24292 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 ;
 
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 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 13 ms 384 KB Output is correct
5 Correct 31 ms 1280 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1091 ms 1280 KB Output is correct
2 Correct 1030 ms 1280 KB Output is correct
3 Correct 1056 ms 1280 KB Output is correct
4 Correct 978 ms 1280 KB Output is correct
5 Correct 1164 ms 2556 KB Output is correct
6 Correct 1116 ms 2684 KB Output is correct
7 Correct 1124 ms 2684 KB Output is correct
8 Correct 1045 ms 2808 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 10088 KB Output is correct
2 Correct 292 ms 9964 KB Output is correct
3 Correct 291 ms 9832 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 517 ms 22728 KB Output is correct
6 Correct 672 ms 22884 KB Output is correct
7 Correct 484 ms 22604 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 888 KB Output is correct
2 Correct 118 ms 1016 KB Output is correct
3 Correct 257 ms 5100 KB Output is correct
4 Correct 231 ms 5228 KB Output is correct
5 Correct 265 ms 888 KB Output is correct
6 Correct 511 ms 6504 KB Output is correct
7 Correct 403 ms 1912 KB Output is correct
8 Correct 559 ms 9576 KB Output is correct
9 Correct 1744 ms 23864 KB Output is correct
10 Correct 867 ms 1632 KB Output is correct
11 Correct 1092 ms 3804 KB Output is correct
12 Correct 1645 ms 20580 KB Output is correct
13 Correct 1897 ms 24292 KB Output is correct