oj.uz

Submission #110538

# Submission time Handle Problem Language Result Execution time Memory
110538 2019-05-11T06:41:05 Z ckodser Cake (CEOI14_cake) C++14
16.6667 / 100
 2000 ms 15484 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(id);
			Set(id, A[id]);
			for (int i = k - 2; ~ i; i --)
			{
				a ++; A[vec[i]] = a;
				S.insert(vec[i]);
				Set(vec[i], A[vec[i]]);
			}
          	assert((int)S.size() == n);
			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 2 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 488 ms 896 KB Output isn't correct
2 Incorrect 259 ms 1024 KB Output isn't correct
3 Correct 386 ms 1116 KB Output is correct
4 Correct 179 ms 1024 KB Output is correct
5 Incorrect 586 ms 1920 KB Output isn't correct
6 Incorrect 558 ms 2040 KB Output isn't correct
7 Correct 427 ms 2040 KB Output is correct
8 Correct 221 ms 1960 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1678 ms 6932 KB Output is correct
2 Incorrect 1567 ms 6916 KB Output isn't correct
3 Execution timed out 2054 ms 6904 KB Time limit exceeded
4 Correct 6 ms 384 KB Output is correct
5 Execution timed out 2037 ms 15384 KB Time limit exceeded
6 Execution timed out 2008 ms 15400 KB Time limit exceeded
7 Execution timed out 2044 ms 15484 KB Time limit exceeded

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 736 KB Output is correct
2 Correct 70 ms 860 KB Output is correct
3 Correct 547 ms 3660 KB Output is correct
4 Correct 567 ms 3576 KB Output is correct
5 Incorrect 173 ms 916 KB Output isn't correct
6 Correct 1122 ms 4896 KB Output is correct
7 Correct 378 ms 1584 KB Output is correct
8 Correct 339 ms 6396 KB Output is correct
9 Execution timed out 2025 ms 15312 KB Time limit exceeded
10 Correct 440 ms 1688 KB Output is correct
11 Correct 1456 ms 3196 KB Output is correct
12 Execution timed out 2025 ms 12608 KB Time limit exceeded
13 Execution timed out 2040 ms 15480 KB Time limit exceeded