oj.uz

Submission #110714

# Submission time Handle Problem Language Result Execution time Memory
110714 2019-05-12T06:37:57 Z Mahdi_Jfri Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 6272 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;
}

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 2087 ms 4352 KB Time limit exceeded
2 Execution timed out 2040 ms 4352 KB Time limit exceeded
3 Execution timed out 2057 ms 4352 KB Time limit exceeded
4 Execution timed out 2051 ms 4352 KB Time limit exceeded
5 Execution timed out 2024 ms 4480 KB Time limit exceeded
6 Execution timed out 2090 ms 4480 KB Time limit exceeded
7 Execution timed out 2011 ms 4480 KB Time limit exceeded
8 Execution timed out 2048 ms 4608 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 5120 KB Time limit exceeded
2 Execution timed out 2029 ms 4984 KB Time limit exceeded
3 Execution timed out 2059 ms 5112 KB Time limit exceeded
4 Execution timed out 2061 ms 4352 KB Time limit exceeded
5 Execution timed out 2070 ms 6264 KB Time limit exceeded
6 Execution timed out 2028 ms 6264 KB Time limit exceeded
7 Execution timed out 2040 ms 6264 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 4352 KB Time limit exceeded
2 Execution timed out 2035 ms 4352 KB Time limit exceeded
3 Execution timed out 2055 ms 4736 KB Time limit exceeded
4 Execution timed out 2058 ms 4608 KB Time limit exceeded
5 Execution timed out 2041 ms 4224 KB Time limit exceeded
6 Execution timed out 2048 ms 4736 KB Time limit exceeded
7 Execution timed out 2037 ms 4352 KB Time limit exceeded
8 Execution timed out 2054 ms 5120 KB Time limit exceeded
9 Execution timed out 2053 ms 6272 KB Time limit exceeded
10 Execution timed out 2045 ms 4352 KB Time limit exceeded
11 Execution timed out 2059 ms 4480 KB Time limit exceeded
12 Execution timed out 2071 ms 5880 KB Time limit exceeded
13 Execution timed out 2047 ms 6264 KB Time limit exceeded