Submission #110724

#	Time	Username	Problem	Language	Result	Execution time	Memory
110724		Mahdi_Jfri	Cake (CEOI14_cake)	C++14	100 / 100	907 ms	7816 KiB

cake

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 2.5e5 + 20;
const int sp = 1e8;

int a[maxn] , pos[maxn] , res[maxn] , id , n;

int Val[maxn * 4];

void shift(int s , int e , int v)
{
	if(e - s >= 2 && Val[v] != -1)
		Val[2 * v] = Val[2 * v + 1] = Val[v];
	Val[v] = -1;
}

void Set(int l , int r , int val , int s = 0 , int e = n , int v = 1)
{
	if(l <= s && e <= r)
	{
		Val[v] = val;
		return;
	}
	if(r <= s || e <= l)
		return;
	shift(s , e , v);

	int m = (s + e) / 2;
	Set(l , r , val , s , m , 2 * v);
	Set(l , r , val , m , e , 2 * v + 1);
}

int get(int p , int s = 0 , int e = n , int v = 1)
{
	if(e - s < 2)
		return Val[v];
	shift(s , e , v);

	int m = (s + e) / 2;
	if(p < m)
		return get(p , s , m , 2 * v);
	else
		return get(p , m , e , 2 * v + 1);
}

int mx[maxn * 4];

int getLeftMost(int l , int r , int val)
{
	int mn = n;
	for(int i = max(1 , n - 9); i <= n; i++)
		if(l <= pos[i] && pos[i] <= r && a[pos[i]] > val)
			mn = min(mn , pos[i]);
	return mn;
}

int getRightMost(int l , int r , int val)
{
	int mx = -1;
	for(int i = max(1 , n - 9); i <= n; i++)
		if(l <= pos[i] && pos[i] <= r && a[pos[i]] > val)
			mx = max(mx , pos[i]);
	return mx;
}

void update_val(int p , int x)
{
	a[p] = x;
}

void prnt(int n)
{
	for(int i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << endl;

	for(int i = max(1 , n - 9); i <= n; i++)
		cout << pos[i] + 1 << " ";
	cout << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	memset(Val , -1 , sizeof Val);

	int p;
	cin >> n >> p;
	p--;

	for(int i = 0; i < n; i++)
	{
		cin >> a[i];

		if(a[i] > n - 10)
			pos[a[i]] = i , a[i] += sp;
	}
	id = n + 1;

	{
		int lp = p - 1 , rp = p + 1;
		while(rp - lp - 1 != n)
		{
			if(lp >= 0 && (rp >= n || a[lp] < a[rp]))
			{
				res[lp] = rp - p - 1;
				lp--;
			}
			else
			{
				res[rp] = p - lp - 1;
				rp++;
			}
		}
	}

	for(int i = 0; i < n; i++)
		Set(i , i + 1 , res[i]);

	int q;
	cin >> q;

	while(q--)
	{
		char ch;
		cin >> ch;

		if(ch == 'F')
		{
			int x;
			cin >> x;
			x--;
			cout << get(x) + abs(p - x) << endl;
		}
		else
		{
			int x , val;
			cin >> x >> val;
			x--;

			for(int i = max(1 , max(a[x] - sp , n - 9)); i <= n - val + 1; i++)
			{
				if(i == n - 9)
					update_val(pos[i] , id++);
				else
					update_val(pos[i] , i + sp - 1);
				pos[i] = pos[i + 1];
			}

			update_val(x , n - val + 1 + sp);
			pos[n - val + 1] = x;

	//		prnt(n);

			if(p == x)
				continue;

		//	cout << "START" << endl;
			int lp , rp;
			if(x < p)
				lp = x , rp = p + 1 + get(x);
			else
				lp = p - 1 - get(x) , rp = x;
			while(rp - lp - 1 != n)
			{
				if(lp >= 0 && (rp >= n || a[lp] > a[rp]))
				{
					int nw = getLeftMost(rp , n , a[lp]);
					Set(rp , nw , p - lp - 1);
					rp = nw;
					if(nw == n)
					{
						Set(0 , lp + 1 , n - p - 1);
						break;
					}
				}
				else
				{
					int nw = getRightMost(0 , lp , a[rp]);
					Set(nw + 1 , lp + 1 , rp - p - 1);
					lp = nw;
					if(nw == -1)
					{
						Set(rp , n , p);	
						break;
					}
				}
			}

		//	cout << "DONE" << endl;
		}
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50