oj.uz

Submission #110533

# Submission time Handle Problem Language Result Execution time Memory
110533 2019-05-11T06:37:00 Z ckodser Cake (CEOI14_cake) C++14
16.6667 / 100
 2000 ms 15512 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 250005, MXS = 1 << 18;
int n, q, st, A[N], MX[MXS * 2];
struct CMP {
	inline bool operator () (int i, int j) {
		return (A[i] < A[j]);
	}
};
set < int , CMP > S;
inline set < int > :: iterator GetEnd()
{
	auto it = S.end(); it --;
	return it;
}
inline void Set(int i, int val)
{
	for (i += MXS; i; i >>= 1)
		MX[i] = max(MX[i], val);
}
inline int Get(int le, int ri)
{
	int Mx = 0;
	for (le += MXS, ri += MXS; le < ri; le >>= 1, ri >>= 1)
	{
		if (le & 1) Mx = max(Mx, MX[le ++]);
		if (ri & 1) Mx = max(Mx, MX[-- ri]);
	}
	return (Mx);
}
int GetR(int le, int val, int id = 1, int l = 0, int r = MXS)
{
	/*if (r <= le || MX[id] <= val)
		return n;
	if (r - l < 2)
		return l;
	int res = GetR(le, val, id << 1, l, (l + r) >> 1);
	if (res < n) return (res);
	return (GetR(le, val, id << 1 | 1, (l + r) >> 1, r));*/

	for (int i = le; i < n; i++)
		if (A[i] > val)
			return i;
	return n;
}
int GetL(int ri, int val, int id = 1, int l = 0, int r = MXS)
{
	/*if (ri <= l || MX[id] <= val)
		return -1;
	if (r - l < 2)
		return l;
	int res = GetL(ri, val, id << 1 | 1, (l + r) >> 1, r);
	if (res > -1) return (res);
	return (GetL(ri, val, id << 1, l, (l + r) >> 1));*/

	for (int i = ri - 1; i >= 0; i --)
		if (A[i] > val)
			return i;
	return -1;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> st; st --;
	for (int i = 0; i < n; i++)
	{
		cin >> A[i];
		S.insert(i);
		Set(i, A[i]);
	}
	cin >> q;
	for (; q; q --)
	{
		char ch;
		int id, k;
		cin >> ch >> id;
		id --;
		if (ch == 'E')
		{
			cin >> k;
			vector < int > vec;
			for (int i = 0; i < k - 1; i++)
				vec.push_back(*GetEnd()), S.erase(GetEnd());
			int a = A[*GetEnd()] + 1;
			S.erase(id);
			A[id] = a;
			S.insert(S.end(), id);
			Set(id, A[id]);
			for (int i = k - 2; ~ i; i --)
			{
				A[vec[i]] = ++ a;
				S.insert(S.end(), vec[i]);
				Set(vec[i], A[vec[i]]);
			}
			continue;
		}

		if (id == st)
			printf("0\n");
		else if (id < st)
			printf("%d\n", GetR(st + 1, Get(id, st)) - id - 1);
		else
			printf("%d\n", id - GetL(st, Get(st + 1, id + 1)) - 1);
	}
	return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 3 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 432 ms 1000 KB Output isn't correct
2 Incorrect 248 ms 1068 KB Output isn't correct
3 Correct 308 ms 1144 KB Output is correct
4 Correct 159 ms 1024 KB Output is correct
5 Incorrect 492 ms 1880 KB Output isn't correct
6 Incorrect 400 ms 1920 KB Output isn't correct
7 Correct 355 ms 1920 KB Output is correct
8 Correct 210 ms 1920 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1939 ms 6988 KB Output is correct
2 Incorrect 1787 ms 6904 KB Output isn't correct
3 Execution timed out 2033 ms 6824 KB Time limit exceeded
4 Correct 3 ms 384 KB Output is correct
5 Execution timed out 2052 ms 15512 KB Time limit exceeded
6 Execution timed out 2060 ms 15484 KB Time limit exceeded
7 Execution timed out 2074 ms 15480 KB Time limit exceeded

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 708 KB Output is correct
2 Correct 61 ms 828 KB Output is correct
3 Correct 417 ms 3576 KB Output is correct
4 Correct 458 ms 3612 KB Output is correct
5 Incorrect 123 ms 888 KB Output isn't correct
6 Correct 1178 ms 4856 KB Output is correct
7 Correct 336 ms 1476 KB Output is correct
8 Correct 343 ms 6532 KB Output is correct
9 Execution timed out 2064 ms 15368 KB Time limit exceeded
10 Correct 435 ms 1656 KB Output is correct
11 Correct 1344 ms 3196 KB Output is correct
12 Execution timed out 2047 ms 12572 KB Time limit exceeded
13 Execution timed out 2058 ms 15480 KB Time limit exceeded