oj.uz

Submission #110531

# Submission time Handle Problem Language Result Execution time Memory
110531 2019-05-11T06:25:27 Z ckodser Cake (CEOI14_cake) C++14
33.3333 / 100
 1216 ms 20828 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));
}
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));
}
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(*S.rbegin()), S.erase(GetEnd());
			int a = A[*S.rbegin()] + 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 426 ms 3984 KB Output isn't correct
2 Incorrect 235 ms 1784 KB Output isn't correct
3 Correct 326 ms 4104 KB Output is correct
4 Correct 200 ms 1400 KB Output is correct
5 Incorrect 519 ms 5624 KB Output isn't correct
6 Incorrect 512 ms 5368 KB Output isn't correct
7 Correct 442 ms 5244 KB Output is correct
8 Correct 211 ms 2312 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 7452 KB Output is correct
2 Incorrect 87 ms 7160 KB Output isn't correct
3 Incorrect 72 ms 7144 KB Output isn't correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 422 ms 16204 KB Output is correct
6 Incorrect 335 ms 16120 KB Output isn't correct
7 Correct 124 ms 15864 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1064 KB Output is correct
2 Correct 39 ms 1172 KB Output is correct
3 Correct 127 ms 3960 KB Output is correct
4 Correct 109 ms 3960 KB Output is correct
5 Correct 129 ms 1272 KB Output is correct
6 Correct 231 ms 5244 KB Output is correct
7 Correct 130 ms 1912 KB Output is correct
8 Correct 309 ms 7416 KB Output is correct
9 Correct 1216 ms 20828 KB Output is correct
10 Correct 382 ms 2040 KB Output is correct
11 Correct 497 ms 5752 KB Output is correct
12 Correct 1164 ms 17784 KB Output is correct
13 Incorrect 792 ms 19692 KB Output isn't correct