oj.uz

Submission #110724

# Submission time Handle Problem Language Result Execution time Memory
110724 2019-05-12T06:52:19 Z Mahdi_Jfri Cake (CEOI14_cake) C++14
100 / 100
 907 ms 7816 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4352 KB Output is correct
2 Correct 5 ms 4352 KB Output is correct
3 Correct 5 ms 4352 KB Output is correct
4 Correct 10 ms 4224 KB Output is correct
5 Correct 27 ms 4352 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 4352 KB Output is correct
2 Correct 227 ms 4352 KB Output is correct
3 Correct 345 ms 4352 KB Output is correct
4 Correct 172 ms 4352 KB Output is correct
5 Correct 347 ms 4480 KB Output is correct
6 Correct 296 ms 4480 KB Output is correct
7 Correct 402 ms 4480 KB Output is correct
8 Correct 217 ms 4480 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 5608 KB Output is correct
2 Correct 200 ms 5560 KB Output is correct
3 Correct 193 ms 5488 KB Output is correct
4 Correct 5 ms 4224 KB Output is correct
5 Correct 263 ms 7012 KB Output is correct
6 Correct 271 ms 6996 KB Output is correct
7 Correct 255 ms 6788 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4508 KB Output is correct
2 Correct 87 ms 4472 KB Output is correct
3 Correct 131 ms 4916 KB Output is correct
4 Correct 166 ms 4984 KB Output is correct
5 Correct 187 ms 4616 KB Output is correct
6 Correct 224 ms 5156 KB Output is correct
7 Correct 239 ms 4856 KB Output is correct
8 Correct 191 ms 5232 KB Output is correct
9 Correct 829 ms 7776 KB Output is correct
10 Correct 643 ms 5496 KB Output is correct
11 Correct 907 ms 5836 KB Output is correct
12 Correct 825 ms 7440 KB Output is correct
13 Correct 701 ms 7816 KB Output is correct