oj.uz

Submission #110709

# Submission time Handle Problem Language Result Execution time Memory
110709 2019-05-12T06:36:09 Z Mahdi_Jfri Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 6268 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 = n;
	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;

			if(p == x)
				continue;

			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 = getRightMost(0 , lp , a[rp]);
					Set(nw + 1 , lp , rp - p - 1);
					lp = nw;
					if(nw == -1)
					{
						Set(rp , n , p);	
						break;
					}
				}
				else
				{
					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;
					}
				}
			}
		}
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 4352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2100 ms 4352 KB Time limit exceeded
2 Execution timed out 2033 ms 4324 KB Time limit exceeded
3 Execution timed out 2041 ms 4352 KB Time limit exceeded
4 Execution timed out 2047 ms 4352 KB Time limit exceeded
5 Execution timed out 2017 ms 4480 KB Time limit exceeded
6 Execution timed out 2051 ms 4480 KB Time limit exceeded
7 Execution timed out 2035 ms 4480 KB Time limit exceeded
8 Execution timed out 2009 ms 4480 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2021 ms 5120 KB Time limit exceeded
2 Execution timed out 2033 ms 5092 KB Time limit exceeded
3 Execution timed out 2045 ms 4992 KB Time limit exceeded
4 Execution timed out 2033 ms 4224 KB Time limit exceeded
5 Execution timed out 2033 ms 6136 KB Time limit exceeded
6 Execution timed out 2023 ms 6236 KB Time limit exceeded
7 Execution timed out 2050 ms 6236 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2012 ms 4352 KB Time limit exceeded
2 Execution timed out 2048 ms 4352 KB Time limit exceeded
3 Execution timed out 2031 ms 4736 KB Time limit exceeded
4 Execution timed out 2013 ms 4708 KB Time limit exceeded
5 Execution timed out 2009 ms 4224 KB Time limit exceeded
6 Execution timed out 2099 ms 4736 KB Time limit exceeded
7 Execution timed out 2043 ms 4352 KB Time limit exceeded
8 Execution timed out 2063 ms 5120 KB Time limit exceeded
9 Execution timed out 2073 ms 6192 KB Time limit exceeded
10 Execution timed out 2043 ms 4224 KB Time limit exceeded
11 Execution timed out 2053 ms 4476 KB Time limit exceeded
12 Execution timed out 2040 ms 5752 KB Time limit exceeded
13 Execution timed out 2036 ms 6268 KB Time limit exceeded