oj.uz

Submission #223942

# Submission time Handle Problem Language Result Execution time Memory
223942 2020-04-16T22:17:21 Z MohamedAhmed04 Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 30376 KB 
#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 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 14 ms 512 KB Output is correct
5 Correct 34 ms 1536 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1382 ms 5648 KB Output is correct
2 Correct 1210 ms 5752 KB Output is correct
3 Correct 1291 ms 5884 KB Output is correct
4 Correct 1162 ms 5840 KB Output is correct
5 Correct 1359 ms 7280 KB Output is correct
6 Correct 1290 ms 7668 KB Output is correct
7 Correct 1350 ms 7412 KB Output is correct
8 Correct 1224 ms 7668 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 11368 KB Output is correct
2 Correct 324 ms 11324 KB Output is correct
3 Correct 330 ms 11236 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 525 ms 25188 KB Output is correct
6 Correct 706 ms 25184 KB Output is correct
7 Correct 534 ms 25056 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 1144 KB Output is correct
2 Correct 138 ms 1400 KB Output is correct
3 Correct 296 ms 6036 KB Output is correct
4 Correct 250 ms 5992 KB Output is correct
5 Correct 290 ms 2040 KB Output is correct
6 Correct 540 ms 8168 KB Output is correct
7 Correct 473 ms 3576 KB Output is correct
8 Correct 635 ms 12008 KB Output is correct
9 Correct 1997 ms 30376 KB Output is correct
10 Correct 984 ms 5460 KB Output is correct
11 Correct 1234 ms 8180 KB Output is correct
12 Correct 1835 ms 26336 KB Output is correct
13 Execution timed out 2063 ms 30220 KB Time limit exceeded