oj.uz

Submission #223868

# Submission time Handle Problem Language Result Execution time Memory
223868 2020-04-16T17:24:02 Z MohamedAhmed04 Cake (CEOI14_cake) C++14
0 / 100
 1329 ms 20576 KB 
#include <bits/stdc++.h>

using namespace std ;

const long long cons = 1e9 ;
const int MAX = 3e5 + 10 ;

long long arr[MAX] , val[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)*1ll * cons , val[i+1] = arr[vp[i].second] + 1ll ;
	build(1 , 1 , n) ;
	int q ;
	cin>>q ;
	while(q--)
	{
		char c ;
		cin>>c ;
		if(c == 'E')
		{
			int x , y ;
			cin>>x>>y ;
			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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 5472 KB Output isn't correct
2 Correct 157 ms 5496 KB Output is correct
3 Incorrect 163 ms 5472 KB Output isn't correct
4 Correct 152 ms 5496 KB Output is correct
5 Incorrect 185 ms 6460 KB Output isn't correct
6 Incorrect 176 ms 6900 KB Output isn't correct
7 Incorrect 175 ms 6772 KB Output isn't correct
8 Correct 170 ms 6900 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 472 ms 7756 KB Output isn't correct
2 Incorrect 327 ms 7512 KB Output isn't correct
3 Incorrect 319 ms 7532 KB Output isn't correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Incorrect 437 ms 15552 KB Output isn't correct
6 Incorrect 557 ms 15724 KB Output isn't correct
7 Incorrect 467 ms 15328 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 1144 KB Output isn't correct
2 Incorrect 73 ms 1272 KB Output isn't correct
3 Incorrect 177 ms 4204 KB Output isn't correct
4 Incorrect 143 ms 4204 KB Output isn't correct
5 Incorrect 129 ms 1912 KB Output isn't correct
6 Incorrect 339 ms 5768 KB Output isn't correct
7 Incorrect 227 ms 3192 KB Output isn't correct
8 Incorrect 101 ms 8168 KB Output isn't correct
9 Incorrect 1086 ms 20452 KB Output isn't correct
10 Incorrect 430 ms 5240 KB Output isn't correct
11 Incorrect 642 ms 7260 KB Output isn't correct
12 Incorrect 1033 ms 18372 KB Output isn't correct
13 Incorrect 1329 ms 20576 KB Output isn't correct