oj.uz

Submission #110550

# Submission time Handle Problem Language Result Execution time Memory
110550 2019-05-11T06:54:56 Z ckodser Cake (CEOI14_cake) C++14
100 / 100
 1246 ms 17248 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));
}
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(*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 3 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 14 ms 1024 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 1020 KB Output is correct
2 Correct 228 ms 1144 KB Output is correct
3 Correct 278 ms 1032 KB Output is correct
4 Correct 179 ms 1036 KB Output is correct
5 Correct 683 ms 1920 KB Output is correct
6 Correct 443 ms 1920 KB Output is correct
7 Correct 411 ms 2040 KB Output is correct
8 Correct 203 ms 1920 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 6848 KB Output is correct
2 Correct 87 ms 6908 KB Output is correct
3 Correct 76 ms 6776 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 414 ms 15692 KB Output is correct
6 Correct 364 ms 15672 KB Output is correct
7 Correct 123 ms 15484 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 640 KB Output is correct
2 Correct 31 ms 888 KB Output is correct
3 Correct 131 ms 3624 KB Output is correct
4 Correct 118 ms 3688 KB Output is correct
5 Correct 120 ms 888 KB Output is correct
6 Correct 201 ms 4616 KB Output is correct
7 Correct 115 ms 1656 KB Output is correct
8 Correct 277 ms 6344 KB Output is correct
9 Correct 1246 ms 17248 KB Output is correct
10 Correct 378 ms 1628 KB Output is correct
11 Correct 478 ms 3188 KB Output is correct
12 Correct 1002 ms 14456 KB Output is correct
13 Correct 751 ms 17228 KB Output is correct