oj.uz

Submission #112515

# Submission time Handle Problem Language Result Execution time Memory
112515 2019-05-20T11:31:20 Z Kastanda Cake (CEOI14_cake) C++11
100 / 100
 1092 ms 23288 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 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 15 ms 1152 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 5348 KB Output is correct
2 Correct 264 ms 5384 KB Output is correct
3 Correct 293 ms 5612 KB Output is correct
4 Correct 147 ms 5368 KB Output is correct
5 Correct 475 ms 6664 KB Output is correct
6 Correct 354 ms 6908 KB Output is correct
7 Correct 308 ms 6824 KB Output is correct
8 Correct 160 ms 6904 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 8184 KB Output is correct
2 Correct 70 ms 8056 KB Output is correct
3 Correct 209 ms 8056 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 310 ms 18268 KB Output is correct
6 Correct 281 ms 18168 KB Output is correct
7 Correct 117 ms 17912 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1152 KB Output is correct
2 Correct 33 ms 1280 KB Output is correct
3 Correct 91 ms 4536 KB Output is correct
4 Correct 100 ms 4556 KB Output is correct
5 Correct 100 ms 1912 KB Output is correct
6 Correct 173 ms 6392 KB Output is correct
7 Correct 118 ms 3112 KB Output is correct
8 Correct 245 ms 8880 KB Output is correct
9 Correct 1092 ms 23160 KB Output is correct
10 Correct 344 ms 5312 KB Output is correct
11 Correct 464 ms 7288 KB Output is correct
12 Correct 906 ms 19828 KB Output is correct
13 Correct 725 ms 23288 KB Output is correct