oj.uz

Submission #110540

# Submission time Handle Problem Language Result Execution time Memory
110540 2019-05-11T06:42:11 Z ckodser Cake (CEOI14_cake) C++14
46.6667 / 100
 2000 ms 15496 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 (int i = le; i < ri; i++)
      	Mx = max(Mx, A[i]);
  	return (Mx);
  	
	/*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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 37 ms 1152 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 1016 KB Output is correct
2 Correct 277 ms 1116 KB Output is correct
3 Correct 318 ms 1024 KB Output is correct
4 Correct 151 ms 1152 KB Output is correct
5 Correct 524 ms 1920 KB Output is correct
6 Correct 537 ms 1940 KB Output is correct
7 Correct 390 ms 1912 KB Output is correct
8 Correct 202 ms 1920 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 6764 KB Time limit exceeded
2 Execution timed out 2031 ms 6716 KB Time limit exceeded
3 Correct 1966 ms 6804 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Execution timed out 2059 ms 15336 KB Time limit exceeded
6 Execution timed out 2054 ms 15224 KB Time limit exceeded
7 Execution timed out 2066 ms 15496 KB Time limit exceeded

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 768 KB Output is correct
2 Correct 72 ms 824 KB Output is correct
3 Correct 906 ms 3576 KB Output is correct
4 Correct 861 ms 3704 KB Output is correct
5 Correct 156 ms 988 KB Output is correct
6 Execution timed out 2036 ms 4812 KB Time limit exceeded
7 Correct 485 ms 1532 KB Output is correct
8 Correct 342 ms 6416 KB Output is correct
9 Execution timed out 2036 ms 15348 KB Time limit exceeded
10 Correct 567 ms 1656 KB Output is correct
11 Execution timed out 2036 ms 2788 KB Time limit exceeded
12 Execution timed out 2049 ms 12560 KB Time limit exceeded
13 Execution timed out 2040 ms 15264 KB Time limit exceeded