제출 #546092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546092		blue	케이크 (CEOI14_cake)	C++17	100 / 100	1347 ms	27528 KiB

cake

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

int N;
vi d;

struct segtree
{
	int Z;
	vi l, r, mxv;

	void build(int i, int L, int R)
	{
		// cerr << "build " << i << ' ' << L << ' ' << R << '\n';
		l[i] = L;
		r[i] = R;
		if(l[i] == r[i])
		{
			// cerr << "case 1\n";
			mxv[i] = d[l[i]];
		}
		else
		{
			// cerr << "case 2\n";
			build(2*i, L, (L+R)/2);
			build(2*i+1, (L+R)/2+1, R);
			mxv[i] = max(mxv[2*i], mxv[2*i+1]);
		}
		// cerr << i << " -> " <<  l[i] << ' ' << r[i] << " : " << mxv[i] << '\n';
		// cerr << "exit\n";
	}

	segtree()
	{
		Z = 4*(1+N+1);
		l = r = mxv = vi(1 + Z);

		build(1, 0, N+1);
	}

	void update(int i, int p, int v)
	{
		if(l[i] == r[i]) mxv[i] = v;
		else 
		{
			if(p <= (l[i] + r[i])/2) update(2*i, p, v);
			else update(2*i+1, p, v);

			mxv[i] = max(mxv[2*i], mxv[2*i+1]);
		}
	}

	int rangemax(int i, int L, int R)
	{
		// cerr << "rangemax : " << i << ' ' << l[i] << ' ' << r[i] << " <> " << L << ' ' << R << '\n';
		if(R < l[i] || r[i] < L) return -1'000'000'000;
		else if(L <= l[i] && r[i] <= R) return mxv[i];
		else return max(rangemax(2*i, L, R), rangemax(2*i+1, L, R));
	}

	int locatenextgeq(int p, int v)
	{
		int i = 1;
		while(l[i] != r[i])
		{
			if(p <= (l[i] + r[i])/2)
				i = 2*i;
			else
				i = 2*i + 1;
		}

		if(mxv[i] >= v) return l[i];

		int rp = 1;

		while(!(rp && l[i] != r[i] && mxv[2*i+1] >= v))
		{
			if((i & 1) == 0)
				rp = 1;
			else
				rp = 0;
			i /= 2;
		}

		i = 2*i + 1;

		while(l[i] != r[i])
		{
			if(mxv[2*i] >= v)
				i = 2*i;
			else
				i = 2*i + 1;
		}

		return l[i];
	}

	int locateprevgeq(int p, int v) //find the largest i <= p such that S[i] >= v
	{
		int i = 1;
		while(l[i] != r[i])
		{
			if(p <= (l[i] + r[i])/2)
				i = 2*i;
			else
				i = 2*i + 1;
		}

		if(mxv[i] >= v) return l[i];

		// cerr << "positional i = " << i << '\n';
		// cerr << l[i] << ' ' << r[i] << ' ' << mxv[i] << '\n';

		int lp = 0;

		while(!(lp && l[i] != r[i] && mxv[2*i] >= v))
		{
			if(i & 1) lp = 1;
			else lp = 0;
			i /= 2;
			// cerr << i << ' ' << l[i] << ' ' << r[i] << " : " << mxv[2*i] << '\n';

			if(i == 0) 
			{
				cerr << "??????\n";
				while(1);
			
			}
		}

		i = 2*i;
		
		// cerr << "resulting i = " << i << '\n';
		// cerr << l[i] << ' ' << r[i] << '\n';

		while(l[i] != r[i])
		{
			if(mxv[2*i + 1] >= v)
				i = 2*i + 1;
			else
				i = 2*i;
		}

		return l[i];
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	// cerr << "enter cake\n";

	int a;

	cin >> N >> a;

	d = vi(1+N+1);
	for(int i = 1; i <= N; i++) cin >> d[i];
	d[0] = d[N+1] = 1'000'000'000;

	int ld = N+1;

	segtree S;

	// cerr << "done\n";

	set<pii> elements;
	for(int i = 1; i <= N; i++)
		elements.insert({d[i], i});

	int Q;
	cin >> Q;
	// cerr << "\n\n";

	// for(int i = 0; i <= N+1; i++) cerr << S.rangemax(1, i, i) << ' ';
	// 			cerr << '\n';
{
	vector<pii> poslist;
	for(int i = 1; i <= N; i++) poslist.push_back({S.rangemax(1, i, i), i});
		sort(poslist.begin(), poslist.end());

	// for(pii p : poslist) cerr << p.second << ' ';
	// 	cerr << '\n';
}

	for(int j = 1; j <= Q; j++)
	{
		char c;
		cin >> c;

		if(c == 'E')
		{
			// cerr << "enter E\n";
			int i, e;
			cin >> i >> e;

			elements.erase({d[i], i});
			d[i] = ++ld;

			// cerr << "new di = " << 

			vector<pii> new_elements;
			new_elements.push_back({d[i], i});

			int nld = ld + e;

			for(int f = 1; f <= e-1; f++)
			{
				auto x = *elements.rbegin();
				new_elements.push_back({nld - (f-1), x.second});
				elements.erase(x);

			}

			ld = nld + 1;

			// cerr << "\n\n";

			for(auto x : new_elements)
			{
				S.update(1, x.second, x.first);
				// cerr << "score of " << x.second << " = " << x.first << '\n';
				elements.insert(x);
				d[x.second] = x.first;
			}
			// cerr << "new elements size = " << sz(new_elements) << '\n';

			// cerr << "move array index " << i << " to rank = " << e << '\n';

			// for(int i = 0; i <= N+1; i++) cerr << S.rangemax(1, i, i) << ' ';
			// 	cerr << '\n';
			// {
			// 	vector<pii> poslist;
			// 	for(int i = 1; i <= N; i++) poslist.push_back({S.rangemax(1, i, i), i});
			// 		sort(poslist.begin(), poslist.end());

			// 	for(pii p : poslist) cerr << p.second << ' ';
			// 		cerr << '\n';
			// }

			// cerr << "exit E\n";
		}
		else
		{
			// cerr << "enter F\n";

			int b;
			cin >> b;

			if(a == b)
			{
				cout << 0 << '\n';
				continue;
			}

			if(a < b)
			{
				// cerr << "hello " << a << ' ' << b << " \n";
				int rmx = S.rangemax(1, a+1, b);
				// cerr << "rmx = " << rmx << '\n';
				// cerr << "rmx = " << rmx << '\n';
				// cerr << "a-1 = " << a-1 << '\n';
				// cerr << "locate prev geq " << a-1 << ' ' << rmx+1 << '\n';
				int prvp = S.locateprevgeq(a-1, rmx);
				// cerr << "prvp = " << prvp << '\n';

				cout << b - prvp - 1 << '\n';
			}
			else
			{
				// cerr << "!\n";
				int rmx = S.rangemax(1, b, a-1);
				// cerr << "rmx = " << rmx << '\n';
				// cerr << "rmx = " << rmx << '\n';
				int nxtp = S.locatenextgeq(a+1, rmx);
				// cerr << "nxtp = " << nxtp << '\n';

				cout << nxtp - b - 1 << '\n';
			}

			// cerr << "exit F\n";
		}
	}

	// cerr << "exit cake\n";
}

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