Submission #84043

#	Time	Username	Problem	Language	Result	Execution time	Memory
84043		aminra	Cake (CEOI14_cake)	C++14	0 / 100	1330 ms	6588 KiB

cake

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int infint = 1e9;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)250003;
int n, s, q, a[MAXN], seg[4 * MAXN], pos[MAXN];
void build(int node, int st, int en)
{
	if(en - st < 2)
	{
		seg[node] = a[st];
		return;
	}
	int mid = (st + en) >> 1;
	build(node << 1, st, mid);
	build(node << 1 | 1, mid, en);
	seg[node] = max(seg[node << 1], seg[node << 1 | 1]);
}
void update(int node, int st, int en, int idx, int val)
{
	if(en - st < 2)
	{
		seg[node] = val;
		return;
	}
	int mid = (st + en) >> 1;
	if(idx < mid)
		update(node << 1, st, mid, idx, val);
	else
		update(node << 1 | 1, mid, en, idx, val);
	seg[node] = max(seg[node << 1], seg[node << 1 | 1]);
}
int get(int node, int st, int en, int l, int r)
{
	if(l >= en || st >= r)
		return 0;
	if(l <= st && en <= r)
		return seg[node];
	int mid = (st + en) >> 1;
	return max(get(node << 1, st, mid, l, r), get(node << 1 | 1, mid, en, l, r));
}
set< pair<int, int> > gre;
int main()
{
	//you think I'm wat? coding machine?
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> s;
	s--;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		pos[a[i]] = i;
	}
	build(1, 0, n);
	for (int i = n; i >= max(1, n - 9); i--)
		gre.insert({i, pos[i]});
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		char type;
		cin >> type;
		if(type == 'E')
		{
			int idx, val;
			cin >> idx >> val;
			idx--, val--;
			auto it = gre.rbegin();
			vector<pair<int, int> > lrg;
			for (auto u : gre)
				lrg.push_back(u);
			int cur = lrg[lrg.size() - val - 1].first + 1;
			update(1, 0, n, idx, cur);
			int tmp = cur;
			it--;
			vector< pair<int, int> > changes, del;
			for (int j = lrg.size() - val; j < lrg.size(); j++)
			{
				if(lrg[j].first == cur)
					changes.push_back({++cur, lrg[j].second}), del.push_back({cur - 1, lrg[j].second});
				it--;
			}
			for (auto u : del)
				gre.erase(u);
			for (auto u : changes)
			{
				update(1, 0, n, u.second, u.first);
				gre.insert(u);
			}
			gre.insert({idx, tmp});
			if(gre.size() > 10)
			{
				pair<int, int> beg = *gre.begin();
				gre.erase(beg);
			}
			/*for (int j = 0; j < n; j++)
				cout << get(1, 0, n, j, j + 1) << " ";
			cout << endl;*/
		}
		else
		{
			int idx;
			cin >> idx;
			idx--;
			if(idx == s)
			{
				cout << 0 << "\n";
				continue;
			}
			if(idx < s)
			{
				int mx = get(1, 0, n, idx, s + 1);
				int L = s - 1, R = n;
				while(R - L > 1)
				{
					int mid = (L + R) >> 1;
					if(get(1, 0, n, s, mid + 1) > mx)
						R = mid;
					else
						L = mid;
				}
				cout << R - idx - 1 << "\n";
			}
			else
			{
				int mx = get(1, 0, n, s, idx + 1);
				int L = -1, R = s;
				while(R - L > 1)
				{
					int mid = (L + R) >> 1;
					if(get(1, 0, n, mid, s + 1) > mx)
						L = mid;
					else
						R = mid;
				}
				cout << idx - L - 1 << "\n";
			}
		}
	}
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:79:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = lrg.size() - val; j < lrg.size(); j++)
                                   ~~^~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50