oj.uz

Submission #546092

# Submission time Handle Problem Language Result Execution time Memory
546092 2022-04-06T10:29:35 Z blue Cake (CEOI14_cake) C++17
100 / 100
 1347 ms 27528 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 19 ms 1664 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 1844 KB Output is correct
2 Correct 331 ms 1944 KB Output is correct
3 Correct 390 ms 1940 KB Output is correct
4 Correct 196 ms 1944 KB Output is correct
5 Correct 631 ms 3364 KB Output is correct
6 Correct 533 ms 3460 KB Output is correct
7 Correct 415 ms 3388 KB Output is correct
8 Correct 254 ms 3408 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 11736 KB Output is correct
2 Correct 102 ms 11668 KB Output is correct
3 Correct 87 ms 11704 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 268 ms 27440 KB Output is correct
6 Correct 256 ms 27420 KB Output is correct
7 Correct 161 ms 27528 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 968 KB Output is correct
2 Correct 42 ms 1268 KB Output is correct
3 Correct 115 ms 5996 KB Output is correct
4 Correct 145 ms 6096 KB Output is correct
5 Correct 163 ms 1332 KB Output is correct
6 Correct 197 ms 8132 KB Output is correct
7 Correct 161 ms 2348 KB Output is correct
8 Correct 276 ms 11740 KB Output is correct
9 Correct 1347 ms 27480 KB Output is correct
10 Correct 553 ms 2228 KB Output is correct
11 Correct 737 ms 4272 KB Output is correct
12 Correct 1279 ms 22592 KB Output is correct
13 Correct 868 ms 27448 KB Output is correct