oj.uz

Submission #110549

# Submission time Handle Problem Language Result Execution time Memory
110549 2019-05-11T06:53:43 Z ckodser Cake (CEOI14_cake) C++14
73.3333 / 100
 2000 ms 15536 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)
{
	A[i] = val;
	MX[i + MXS] = val;
	for (i += MXS; i; i >>= 1)
		MX[i >> 1] = max(MX[i], MX[i ^ 1]);
}
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]), le ++;
		if (ri & 1) ri --, 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);
			Set(id, a);
			S.insert(S.end(), id);
			for (int i = k - 2; ~ i; i --)
			{
				a ++; Set(vec[i], a);
				S.insert(S.end(), 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 40 ms 1024 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 976 KB Output is correct
2 Correct 284 ms 1144 KB Output is correct
3 Correct 322 ms 1144 KB Output is correct
4 Correct 171 ms 1040 KB Output is correct
5 Correct 578 ms 1912 KB Output is correct
6 Correct 400 ms 1920 KB Output is correct
7 Correct 348 ms 1928 KB Output is correct
8 Correct 229 ms 1920 KB Output is correct

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1810 ms 7000 KB Output is correct
2 Correct 1419 ms 6884 KB Output is correct
3 Correct 1815 ms 6960 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Execution timed out 2041 ms 15372 KB Time limit exceeded
6 Execution timed out 2047 ms 15420 KB Time limit exceeded
7 Execution timed out 2041 ms 15536 KB Time limit exceeded

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 640 KB Output is correct
2 Correct 57 ms 768 KB Output is correct
3 Correct 512 ms 3832 KB Output is correct
4 Correct 447 ms 3636 KB Output is correct
5 Correct 119 ms 888 KB Output is correct
6 Correct 1119 ms 4856 KB Output is correct
7 Correct 296 ms 1528 KB Output is correct
8 Correct 373 ms 6380 KB Output is correct
9 Execution timed out 2041 ms 15456 KB Time limit exceeded
10 Correct 396 ms 1788 KB Output is correct
11 Correct 1524 ms 3100 KB Output is correct
12 Execution timed out 2033 ms 12548 KB Time limit exceeded
13 Execution timed out 2040 ms 15480 KB Time limit exceeded