oj.uz

Submission #110536

# Submission time Handle Problem Language Result Execution time Memory
110536 2019-05-11T06:39:03 Z ckodser Cake (CEOI14_cake) C++14
16.6667 / 100
 2000 ms 15480 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 ++; A[vec[i]] = a;
				S.insert(S.end(), 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 429 ms 1012 KB Output isn't correct
2 Incorrect 241 ms 1024 KB Output isn't correct
3 Correct 302 ms 1144 KB Output is correct
4 Correct 162 ms 1144 KB Output is correct
5 Incorrect 509 ms 1900 KB Output isn't correct
6 Incorrect 411 ms 1792 KB Output isn't correct
7 Correct 366 ms 1956 KB Output is correct
8 Correct 188 ms 1912 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1724 ms 6952 KB Output is correct
2 Incorrect 1515 ms 6876 KB Output isn't correct
3 Incorrect 1897 ms 6780 KB Output isn't correct
4 Correct 2 ms 384 KB Output is correct
5 Execution timed out 2048 ms 15404 KB Time limit exceeded
6 Execution timed out 2057 ms 15384 KB Time limit exceeded
7 Execution timed out 2058 ms 15440 KB Time limit exceeded

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 640 KB Output is correct
2 Correct 57 ms 768 KB Output is correct
3 Correct 475 ms 3784 KB Output is correct
4 Correct 495 ms 3616 KB Output is correct
5 Incorrect 130 ms 1016 KB Output isn't correct
6 Correct 1219 ms 4972 KB Output is correct
7 Correct 361 ms 1528 KB Output is correct
8 Correct 318 ms 6264 KB Output is correct
9 Execution timed out 2052 ms 15428 KB Time limit exceeded
10 Correct 440 ms 1656 KB Output is correct
11 Correct 1538 ms 3044 KB Output is correct
12 Execution timed out 2051 ms 12612 KB Time limit exceeded
13 Execution timed out 2063 ms 15480 KB Time limit exceeded